Como determinar se dois nós são conectados?

votos
13

Eu estou preocupado que esta pode estar trabalhando em um problema NP-Completo. Eu estou esperando que alguém pode me dar uma resposta sobre se é ou não. E eu estou procurando por mais de uma resposta que apenas sim ou não. Eu gostaria de saber por quê. Se você pode dizer: Este é basicamente este problema 'x' que é / não é NP-Completo. (Ligação wikipedia)

(Sem isso não é lição de casa)

Existe uma maneira de determinar se dois pontos são conectados em um grafo não-dirigido arbitrária. por exemplo, o seguinte

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

Os pontos A que M (sem 'I') são pontos de controlo (como uma válvula de um tubo de gás natural) que pode ser aberto ou fechado. Os '+' s são nós (como tubo T 's), e eu acho que o Bem e da Câmara também são os nós também.

Eu gostaria de saber se eu fechar um ponto arbitrário de controle (por exemplo, C) se o Bem e Casa ainda está conectado (outros pontos de controle também pode ser fechado). Por exemplo, se B, K e D estão fechados, ainda temos um caminho através AEJFCGLM, e fechamento C irá desconectar o Bem eo House. Claro; se apenas D foi fechada, fechando somente C não desligue o House.

Outra forma de colocar este, é uma ponte de C / corte borda / istmo?

I pode tratar cada ponto de controlo como um peso no gráfico (quer 0 para aberta ou fechada para 1); e depois encontrar o caminho mais curto entre Bem e Casa (resultado> = 1 indica que eles foram desligados. Há várias maneiras que eu posso curto-circuito o algoritmo para encontrar o caminho mais curto demais (por exemplo, descartar um caminho uma vez que atinge 1, pare searching uma vez que temos qualquer caminho que liga o Bem e da Casa, etc.). e, claro, eu posso também colocar em algum limite artificial sobre quantos saltos para verificar antes de desistir.

Alguém deve ter classificado esse tipo de problema antes, eu só estou perdendo o nome.

Publicado 09/12/2008 em 22:41
fonte usuário
Em outras línguas...                            


11 respostas

votos
31

A sua descrição parece indicar que você está apenas interessado em saber se dois nós são conectados, não encontrando o caminho mais curto.

Encontrar se dois nós são conectados é relativamente fácil:

Create two sets of nodes:  toDoSet and doneSet
Add the source node to the toDoSet 
while (toDoSet is not empty) {
  Remove the first element from toDoList
  Add it to doneList
  foreach (node reachable from the removed node) {
    if (the node equals the destination node) {
       return success
    }
    if (the node is not in doneSet) {
       add it to toDoSet 
    }
  }
}

return failure.

Se você usar uma tabela hash ou algo semelhante para toDoSet e doneSet, eu acredito que este é um algoritmo linear.

Note-se que este algoritmo é basicamente a parte de marca da coleta de lixo mark-and-sweep.

Respondeu 09/12/2008 em 22:52
fonte usuário

votos
6

Veja http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , o seu balcão único para todos os problemas gráfico relacionado. Eu acredito que o problema é de fato resolvidos em tempo quadrática.

Respondeu 09/12/2008 em 22:45
fonte usuário

votos
5

Você não precisa o algoritmo de Dijkstra para este problema, uma vez que utiliza uma pilha que não é necessário e introduz um fator de log (N) à sua complexidade. Este é apenas em largura primeira pesquisa - não incluem as bordas fechadas como bordas.

Respondeu 09/12/2008 em 23:08
fonte usuário

votos
3

O problema de encontrar o caminho mais curto não é NP-completo. É o chamado Shortest Path Problem (originalmente o suficiente) e existem algoritmos para resolver muitas variações diferentes do mesmo.

O problema de determinar se dois nós são conectados não é NP-completo também. Você pode usar uma busca em profundidade a partir de qualquer nó para determinar se ele está conectado a outro nó.

Respondeu 09/12/2008 em 22:51
fonte usuário

votos
2

Supondo que você tenha uma matriz de adjacência:

bool[,] adj = new bool[n, n];

Onde bool [i, j] = true se há um caminho aberto entre i e j e bool [i, i] = false.

public bool pathExists(int[,] adj, int start, int end)
{
  List<int> visited = new List<int>();
  List<int> inprocess = new List<int>();
  inprocess.Add(start);

  while(inprocess.Count > 0)
  {
    int cur = inprocess[0];
    inprocess.RemoveAt(0);
    if(cur == end)
      return true;
    if(visited.Contains(cur))
      continue;
    visited.Add(cur);
    for(int i = 0; i < adj.Length; i++)
      if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i))
        inprocess.Add(i);
  }
  return false;
}

Aqui está uma versão recursiva do algoritmo acima (escrito em Ruby):

def connected? from, to, edges
  return true if from == to
  return true if edges.include?([from, to])
  return true if edges.include?([to, from])

  adjacent = edges.find_all { |e| e.include? from }
                  .flatten
                  .reject { |e| e == from }

  return adjacent.map do |a|
    connected? a, to, edges.reject { |e| e.include? from }
  end.any?
end
Respondeu 09/12/2008 em 23:23
fonte usuário

votos
2

Para mim parece que você está em para uma solução, mas é possível que eu mal o problema. Se você fizer como você diz, e dar as bordas fechadas 1 como peso, você pode simplesmente aplicar o algoritmo de Dijkstra, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . Isso deve resolver o seu problema em O (E * lg (V))

Respondeu 09/12/2008 em 22:49
fonte usuário

votos
2

não NP-completos, resolvido com uma solução bem conhecida - Algoritmo de Dijkstra

Respondeu 09/12/2008 em 22:43
fonte usuário

votos
0

Eu vejo que você tem a sua resposta que definitivamente não é NP-completa e esta é uma questão muito antiga também.

No entanto, vou propor uma outra abordagem para olhar para o problema. Você pode usar conjuntos disjuntos para isso. Na maioria dos casos, para o cenário determinado, a abordagem resultará em melhor momento do que fazer um percurso gráfico (que inclui constante de tempo para um grande pedaço de testes). No entanto, a construção do gráfico pode levar boa quantidade de tempo, se a união por classificação ou caminho de compressão é usado.

Você pode ler sobre a Estrutura de dados aqui .

Respondeu 03/09/2018 em 13:36
fonte usuário

votos
0

Se tudo que você precisa é determinar se 2 nós estão ligados você pode usar conjuntos em vez disso, que é mais rápido do que algoritmos de grafos.

  1. Dividir seu gráfico inteiro em bordas. Adicionar cada aresta a um conjunto.
  2. Em iteração seguinte, desenhar arestas entre os 2 nós exteriores da borda feitas na etapa 2. Isto significa que a adição de novos nós (com os seus conjuntos correspondentes) com o conjunto do bordo original da. (Fusão basicamente definido)
  3. Repita 2 até os 2 nós que você está procurando estão no mesmo conjunto. Você também vai precisar de fazer uma verificação após o passo 1 (apenas no caso de os 2 nós são adjacentes).

No início seus nós será cada um no seu conjunto,

o   o1   o   o   o   o   o   o2
 \ /     \ /     \ /     \ /
 o o     o o     o o     o o
   \     /         \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

Como o algoritmo progride e funde os conjuntos, relativamente metades de entrada.

No exemplo acima, eu estava olhando para ver se havia um caminho entre O1 e O2. Eu encontrei este caminho somente no final após a fusão de todas as bordas. Alguns gráficos podem ter componentes separados (desconectado), o que implica que você não vai ser capaz de ter um conjunto no final. Nesse caso você pode usar este algoritmo para testar a conectividade e até mesmo contar o número de componentes em um gráfico. O número de componentes é o número de conjuntos que são capazes de obter quando o algoritmo termina.

Uma possível gráfico (para a árvore acima):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
Respondeu 17/12/2011 em 04:14
fonte usuário

votos
0

Dijkstra é um exagero !! Basta usar amplitude primeira pesquisa de A para procurar o nó que você deseja alcançar. Se você não consegue encontrá-lo, ele não está conectado. A complexidade é O (nm) para cada pesquisa, que é menos de Dijkstra.

Algo relacionado é o / problema de corte min de fluxo máximo. Procurá-lo, pode ser relevante para o seu problema.

Respondeu 12/12/2008 em 15:11
fonte usuário

votos
-1

Qualquer algoritmo de caminho mais curto gráfico vai ser um exagero se tudo que você precisa é encontrar se um nó está conectado a outro. Uma biblioteca bom Java que realiza que é JGraphT . É o uso é bastante simples, aqui está um exemplo de um gráfico Integer:

public void loadGraph() {
    // first we create a new undirected graph of Integers
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);

    // then we add some nodes
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addVertex(4);
    graph.addVertex(5);
    graph.addVertex(6);
    graph.addVertex(7);
    graph.addVertex(8);
    graph.addVertex(9);
    graph.addVertex(10);
    graph.addVertex(11);
    graph.addVertex(12);
    graph.addVertex(13);
    graph.addVertex(14);
    graph.addVertex(15);
    graph.addVertex(16);

    // then we connect the nodes
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(5, 6);
    graph.addEdge(6, 7);
    graph.addEdge(7, 8);
    graph.addEdge(8, 9);
    graph.addEdge(9, 10);
    graph.addEdge(10, 11);
    graph.addEdge(11, 12);
    graph.addEdge(13, 14);
    graph.addEdge(14, 15);
    graph.addEdge(15, 16);

    // finally we use ConnectivityInspector to check nodes connectivity
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph);

    debug(inspector, 1, 2);
    debug(inspector, 1, 4);
    debug(inspector, 1, 3);
    debug(inspector, 1, 12);
    debug(inspector, 16, 5);
}

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) {
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}

Este lib também oferece todos os caminhos mais curtos algoritmos bem.

Respondeu 14/11/2016 em 06:34
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more