Algoritmo de gráfico para encontrar todas as conexões entre dois vértices arbitrários

117

Estou tentando determinar o algoritmo com melhor eficiência de tempo para realizar a tarefa descrita abaixo.

Eu tenho um conjunto de registros. Para este conjunto de registros, tenho dados de conexão que indicam como os pares de registros desse conjunto se conectam entre si. Isso basicamente representa um gráfico não direcionado, com os registros sendo os vértices e os dados de conexão as arestas.

Todos os registros no conjunto têm informações de conexão (ou seja, nenhum registro órfão está presente; cada registro no conjunto se conecta a um ou mais outros registros no conjunto).

Quero escolher dois registros quaisquer do conjunto e ser capaz de mostrar todos os caminhos simples entre os registros escolhidos. Por "caminhos simples", quero dizer os caminhos que não têm registros repetidos no caminho (ou seja, apenas caminhos finitos).

Nota: Os dois registros escolhidos sempre serão diferentes (ou seja, o vértice inicial e final nunca serão os mesmos; sem ciclos).

Por exemplo:

    Se eu tiver os seguintes registros:
        A, B, C, D, E

    e o seguinte representa as conexões: 
        (A, B), (A, C), (B, A), (B, D), (B, E), (B, F), (C, A), (C, E),
        (C, F), (D, B), (E, C), (E, F), (F, B), (F, C), (F, E)

        [onde (A, B) significa que o registro A se conecta ao registro B]

Se eu escolher B como meu registro inicial e E como meu registro final, gostaria de encontrar todos os caminhos simples através das conexões de registro que conectariam o registro B ao registro E.

   Todos os caminhos que conectam B a E:
      B-> E
      B-> F-> E
      B-> F-> C-> E
      B-> A-> C-> E
      B-> A-> C-> F-> E

Este é um exemplo, na prática posso ter conjuntos contendo centenas de milhares de registros.

Robert Groves
fonte
As conexões são chamadas de ciclos , e essa resposta traz muitas informações para você.
elhoim,
3
Por favor, diga se você deseja uma lista finita de conexões sem loop ou um fluxo infinito de conexões com todos os loops possíveis. Cf. Resposta de Blorgbeard.
Charles Stewart
Alguém pode ajudar com isso ??? stackoverflow.com/questions/32516706/…
tejas3006

Respostas:

116

Parece que isso pode ser feito com uma pesquisa em profundidade no gráfico. A pesquisa em profundidade encontrará todos os caminhos não cíclicos entre dois nós. Este algoritmo deve ser muito rápido e escalar para gráficos grandes (a estrutura de dados do gráfico é esparsa, por isso usa apenas a quantidade de memória necessária).

Percebi que o gráfico que você especificou acima tem apenas uma aresta que é direcional (B, E). Foi um erro de digitação ou é realmente um gráfico direcionado? Esta solução funciona independentemente. Desculpe não ter conseguido fazer em C, sou um pouco fraco nessa área. Espero que você seja capaz de traduzir este código Java sem muitos problemas.

Graph.java:

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

public class Graph {
    private Map<String, LinkedHashSet<String>> map = new HashMap();

    public void addEdge(String node1, String node2) {
        LinkedHashSet<String> adjacent = map.get(node1);
        if(adjacent==null) {
            adjacent = new LinkedHashSet();
            map.put(node1, adjacent);
        }
        adjacent.add(node2);
    }

    public void addTwoWayVertex(String node1, String node2) {
        addEdge(node1, node2);
        addEdge(node2, node1);
    }

    public boolean isConnected(String node1, String node2) {
        Set adjacent = map.get(node1);
        if(adjacent==null) {
            return false;
        }
        return adjacent.contains(node2);
    }

    public LinkedList<String> adjacentNodes(String last) {
        LinkedHashSet<String> adjacent = map.get(last);
        if(adjacent==null) {
            return new LinkedList();
        }
        return new LinkedList<String>(adjacent);
    }
}

Search.java:

import java.util.LinkedList;

public class Search {

    private static final String START = "B";
    private static final String END = "E";

    public static void main(String[] args) {
        // this graph is directional
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "A");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E"); // this is the only one-way connection
        graph.addEdge("B", "F");
        graph.addEdge("C", "A");
        graph.addEdge("C", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "B");
        graph.addEdge("E", "C");
        graph.addEdge("E", "F");
        graph.addEdge("F", "B");
        graph.addEdge("F", "C");
        graph.addEdge("F", "E");
        LinkedList<String> visited = new LinkedList();
        visited.add(START);
        new Search().depthFirst(graph, visited);
    }

    private void depthFirst(Graph graph, LinkedList<String> visited) {
        LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
        // examine adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            if (node.equals(END)) {
                visited.add(node);
                printPath(visited);
                visited.removeLast();
                break;
            }
        }
        for (String node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            depthFirst(graph, visited);
            visited.removeLast();
        }
    }

    private void printPath(LinkedList<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

Resultado do programa:

B E 
B A C E 
B A C F E 
B F E 
B F C E 
Casey Watson
fonte
5
Observe que esta não é uma travessia abrangente. Com amplitude, primeiro você visita todos os nós com distância 0 até a raiz, depois aqueles com distância 1, depois 2, etc.
mweerden
14
Correto, este é um DFS. Um BFS precisaria usar uma fila, enfileirando nós de nível (N + 1) para serem processados após todos os nós de nível N. No entanto, para os objetivos do OP, o BFS ou o DFS funcionarão, já que nenhuma ordem de classificação preferencial de caminhos é especificada.
Matt J
1
Casey, há muito tempo procuro uma solução para este problema. Implementei recentemente este DFS em C ++ e funciona muito bem.
AndyUK
6
A desvantagem da recursão é que se você tiver um gráfico profundo (A-> B-> C -> ...-> N), você pode ter StackOverflowError em java.
Rrr
1
Eu adicionei uma versão iterativa em C # abaixo.
batta de
23

O Dicionário online de Algoritmos e Estruturas de Dados do Instituto Nacional de Padrões e Tecnologia (NIST) lista esse problema como " todos os caminhos simples" e recomenda uma pesquisa em profundidade . CLRS fornece os algoritmos relevantes.

Uma técnica inteligente usando Redes de Petri é encontrada aqui

Michael Dorfman
fonte
2
Você poderia me ajudar com uma solução melhor? um DFS leva uma eternidade para ser executado: stackoverflow.com/q/8342101/632951
Pacerier
Observe que é fácil criar gráficos para os quais o DFS é muito ineficiente, embora o conjunto de todos os caminhos simples entre os dois nós seja pequeno e fácil de encontrar. Por exemplo, considere um grafo não direcionado onde o nó inicial A tem dois vizinhos: o nó objetivo B (que não tem vizinhos além de A) e um nó C que é parte de um clique totalmente conectado de n + 1 nós. Mesmo que haja claramente apenas um caminho simples de A para B, um DFS ingênuo perderá O ( n !) Tempo explorando inutilmente o clique. Exemplos semelhantes (uma solução, DFS leva tempo exponencial) também podem ser encontrados entre os DAGs.
Ilmari Karonen de
O NIST diz: "Os caminhos podem ser enumerados com uma pesquisa em profundidade."
chomp
13

Aqui está o pseudocódigo que criei. Este não é um dialeto de pseudocódigo particular, mas deve ser simples o suficiente para seguir.

Alguém quer escolher isso separadamente.

  • [p] é uma lista de vértices que representam o caminho atual.

  • [x] é uma lista de caminhos onde atendem aos critérios

  • [s] é o vértice de origem

  • [d] é o vértice de destino

  • [c] é o vértice atual (argumento para a rotina PathFind)

Suponha que haja uma maneira eficiente de pesquisar os vértices adjacentes (linha 6).

     1 PathList [p]
     2 ListOfPathLists [x]
     3 Vértices [s], [d]

     4 PathFind (Vertex [c])
     5 Adicione [c] ao final da lista [p]
     6 Para cada vértice [v] adjacente a [c]
     7 Se [v] for igual a [d], então
     8 Salvar lista [p] em [x]
     9 Caso contrário, se [v] não estiver na lista [p]
    10 PathFind ([v])
    11 Próximo Para
    12 Remova a cauda de [p]
    13 Retorno
Robert Groves
fonte
Você pode, por favor, esclarecer as etapas 11 e 12
usuário bozo
A linha 11 apenas denota o bloco final que vai com o loop For que começa na linha 6. A linha 12 significa remover o último elemento da lista de caminhos antes de retornar ao chamador.
Robert Groves
Qual é a chamada inicial para PathFind - você passa o vértice [s] de origem?
usuário bozo
Neste exemplo, sim, mas lembre-se de que você pode não querer escrever um código real que mapeie um a um com este pseudocódigo. Significa mais para ilustrar um processo de pensamento do que um código bem projetado.
Robert Groves
8

Como a implementação de DFS não recursiva existente fornecida nesta resposta parece estar quebrada, deixe-me fornecer uma que realmente funcione.

Eu escrevi isso em Python, porque acho que é bastante legível e organizado por detalhes de implementação (e porque tem a yieldpalavra-chave útil para implementar geradores ), mas deve ser bastante fácil de portar para outras linguagens.

# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
    visited = set()
    visited.add(start)

    nodestack = list()
    indexstack = list()
    current = start
    i = 0

    while True:
        # get a list of the neighbors of the current node
        neighbors = graph[current]

        # find the next unvisited neighbor of this node, if any
        while i < len(neighbors) and neighbors[i] in visited: i += 1

        if i >= len(neighbors):
            # we've reached the last neighbor of this node, backtrack
            visited.remove(current)
            if len(nodestack) < 1: break  # can't backtrack, stop!
            current = nodestack.pop()
            i = indexstack.pop()
        elif neighbors[i] == end:
            # yay, we found the target node! let the caller process the path
            yield nodestack + [current, end]
            i += 1
        else:
            # push current node and index onto stacks, switch to neighbor
            nodestack.append(current)
            indexstack.append(i+1)
            visited.add(neighbors[i])
            current = neighbors[i]
            i = 0

Este código mantém duas pilhas paralelas: uma contendo os nós anteriores no caminho atual e outra contendo o índice vizinho atual para cada nó na pilha de nós (para que possamos retomar a iteração através dos vizinhos de um nó quando o retirarmos a pilha). Eu poderia também ter usado uma única pilha de pares (nó, índice), mas imaginei que o método de duas pilhas seria mais legível e talvez mais fácil de implementar para usuários de outras linguagens.

Este código também usa um visitedconjunto separado , que sempre contém o nó atual e quaisquer nós na pilha, para me permitir verificar com eficiência se um nó já faz parte do caminho atual. Se a sua linguagem tiver uma estrutura de dados de "conjunto ordenado" que fornece operações push / pop semelhantes a pilha e consultas de associação eficientes, você pode usar isso para a pilha de nós e se livrar do visitedconjunto separado .

Alternativamente, se você estiver usando uma classe / estrutura mutável personalizada para seus nós, você pode simplesmente armazenar um sinalizador booleano em cada nó para indicar se ele foi visitado como parte do caminho de pesquisa atual. É claro que esse método não permite que você execute duas pesquisas no mesmo gráfico em paralelo, caso você queira fazer isso por algum motivo.

Aqui estão alguns códigos de teste que demonstram como a função fornecida acima funciona:

# test graph:
#     ,---B---.
#     A   |   D
#     `---C---'
graph = {
    "A": ("B", "C"),
    "B": ("A", "C", "D"),
    "C": ("A", "B", "D"),
    "D": ("B", "C"),
}

# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)

Executar este código no gráfico de exemplo fornecido produz a seguinte saída:

A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D

Observe que, embora este gráfico de exemplo não seja direcionado (ou seja, todas as suas arestas vão para os dois lados), o algoritmo também funciona para gráficos direcionados arbitrários. Por exemplo, remover a C -> Bborda (removendo Bda lista de vizinhos de C) produz a mesma saída, exceto para o terceiro caminho ( A -> C -> B -> D), que não é mais possível.


Ps. É fácil construir gráficos para os quais algoritmos de pesquisa simples como este (e os outros fornecidos neste tópico) têm um desempenho muito fraco.

Por exemplo, considere a tarefa de encontrar todos os caminhos de A a B em um grafo não direcionado onde o nó inicial A tem dois vizinhos: o nó alvo B (que não tem outros vizinhos além de A) e um nó C que faz parte de um clique de n +1 nós, como este:

graph = {
    "A": ("B", "C"),
    "B": ("A"),
    "C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
    "H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
    "I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
    "J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
    "K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
    "L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
    "M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
    "N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
    "O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}

É fácil ver que o único caminho entre A e B é o direto, mas um DFS ingênuo iniciado no nó A perderá O ( n !) Tempo explorando inutilmente os caminhos dentro do clique, mesmo que seja óbvio (para um humano) que nenhum desses caminhos pode levar a B.

Também é possível construir DAGs com propriedades semelhantes, por exemplo, fazendo com que o nó inicial A conecte o nó de destino B e a dois outros nós C 1 e C 2 , ambos os quais se conectam aos nós D 1 e D 2 , ambos os quais se conectam a E 1 e E 2 e assim por diante. Para n camadas de nós organizados dessa forma, uma busca ingênua por todos os caminhos de A a B acabará perdendo O (2 n ) tempo examinando todos os possíveis becos sem saída antes de desistir.

É claro, a adição de um bordo para o nó de destino B a partir de um dos nós no bando (diferente de C), ou a partir da última camada do DAG, iria criar um exponencialmente grande número de possíveis caminhos de A a B, e um o algoritmo de busca puramente local não pode realmente dizer com antecedência se encontrará ou não tal borda. Assim, em certo sentido, a baixa sensibilidade de saída dessas pesquisas ingênuas se deve à falta de consciência da estrutura global do gráfico.

Embora existam vários métodos de pré-processamento (como a eliminação iterativa de nós folha, a procura de separadores de vértice de nó único, etc.) que poderiam ser usados ​​para evitar alguns desses "becos sem saída em tempo exponencial", não conheço nenhum geral truque de pré-processamento que poderia eliminá-los em todos os casos. Uma solução geral seria verificar em cada etapa da pesquisa se o nó de destino ainda pode ser alcançado (usando uma subprocura) e retroceder mais cedo se não for - mas, infelizmente, isso tornaria a pesquisa significativamente mais lenta (na pior das hipóteses , proporcionalmente ao tamanho do gráfico) para muitos gráficos que não contêm esses becos sem saída patológicos.

Ilmari Karonen
fonte
1
Isso é o que estou procurando, obrigado :)
arslan
Obrigado por sua solução DFS não recursiva. Basta notar a última linha de imprimir o resultado tem um erro de sintaxe, deve ser for path in find_simple_paths(graph, "A", "D"): print(" -> ".join(path)), o printque faltava o parêntese.
David Oliván Ubieto
1
@ DavidOlivánUbieto: É o código Python 2, por isso não há parênteses. :)
Ilmari Karonen
5

Aqui está uma versão recursiva logicamente melhor em comparação com o segundo andar.

public class Search {

private static final String START = "B";
private static final String END = "E";

public static void main(String[] args) {
    // this graph is directional
    Graph graph = new Graph();
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("B", "A");
    graph.addEdge("B", "D");
    graph.addEdge("B", "E"); // this is the only one-way connection
    graph.addEdge("B", "F");
    graph.addEdge("C", "A");
    graph.addEdge("C", "E");
    graph.addEdge("C", "F");
    graph.addEdge("D", "B");
    graph.addEdge("E", "C");
    graph.addEdge("E", "F");
    graph.addEdge("F", "B");
    graph.addEdge("F", "C");
    graph.addEdge("F", "E");
    List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
    String currentNode = START;
    List<String> visited = new ArrayList<String>();
    visited.add(START);
    new Search().findAllPaths(graph, seen, paths, currentNode);
    for(ArrayList<String> path : paths){
        for (String node : path) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }   
}

private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {        
    if (currentNode.equals(END)) { 
        paths.add(new ArrayList(Arrays.asList(visited.toArray())));
        return;
    }
    else {
        LinkedList<String> nodes = graph.adjacentNodes(currentNode);    
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            } 
            List<String> temp = new ArrayList<String>();
            temp.addAll(visited);
            temp.add(node);          
            findAllPaths(graph, temp, paths, node);
        }
    }
}
}

Resultado do programa

B A C E 

B A C F E 

B E

B F C E

B F E 
Haibin Liu
fonte
4

Solução em código C. É baseado em DFS que usa memória mínima.

#include <stdio.h>
#include <stdbool.h>

#define maxN    20  

struct  nodeLink
{

    char node1;
    char node2;

};

struct  stack
{   
    int sp;
    char    node[maxN];
};   

void    initStk(stk)
struct  stack   *stk;
{
    int i;
    for (i = 0; i < maxN; i++)
        stk->node[i] = ' ';
    stk->sp = -1;   
}

void    pushIn(stk, node)
struct  stack   *stk;
char    node;
{

    stk->sp++;
    stk->node[stk->sp] = node;

}    

void    popOutAll(stk)
struct  stack   *stk;
{

    char    node;
    int i, stkN = stk->sp;

    for (i = 0; i <= stkN; i++)
    {
        node = stk->node[i];
        if (i == 0)
            printf("src node : %c", node);
        else if (i == stkN)
            printf(" => %c : dst node.\n", node);
        else
            printf(" => %c ", node);
    }

}


/* Test whether the node already exists in the stack    */
bool    InStack(stk, InterN)
struct  stack   *stk;
char    InterN;
{

    int i, stkN = stk->sp;  /* 0-based  */
    bool    rtn = false;    

    for (i = 0; i <= stkN; i++)
    {
        if (stk->node[i] == InterN)
        {
            rtn = true;
            break;
        }
    }

    return     rtn;

}

char    otherNode(targetNode, lnkNode)
char    targetNode;
struct  nodeLink    *lnkNode;
{

    return  (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;

}

int entries = 8;
struct  nodeLink    topo[maxN]    =       
    {
        {'b', 'a'}, 
        {'b', 'e'}, 
        {'b', 'd'}, 
        {'f', 'b'}, 
        {'a', 'c'},
        {'c', 'f'}, 
        {'c', 'e'},
        {'f', 'e'},               
    };

char    srcNode = 'b', dstN = 'e';      

int reachTime;  

void    InterNode(interN, stk)
char    interN;
struct  stack   *stk;
{

    char    otherInterN;
    int i, numInterN = 0;
    static  int entryTime   =   0;

    entryTime++;

    for (i = 0; i < entries; i++)
    {

        if (topo[i].node1 != interN  && topo[i].node2 != interN) 
        {
            continue;   
        }

        otherInterN = otherNode(interN, &topo[i]);

        numInterN++;

        if (otherInterN == stk->node[stk->sp - 1])
        {
            continue;   
        }

        /*  Loop avoidance: abandon the route   */
        if (InStack(stk, otherInterN) == true)
        {
            continue;   
        }

        pushIn(stk, otherInterN);

        if (otherInterN == dstN)
        {
            popOutAll(stk);
            reachTime++;
            stk->sp --;   /*    back trace one node  */
            continue;
        }
        else
            InterNode(otherInterN, stk);

    }

        stk->sp --;

}


int    main()

{

    struct  stack   stk;

    initStk(&stk);
    pushIn(&stk, srcNode);  

    reachTime = 0;
    InterNode(srcNode, &stk);

    printf("\nNumber of all possible and unique routes = %d\n", reachTime);

}
Leon Chang
fonte
2

Isso pode ser tarde, mas aqui está a mesma versão C # do algoritmo DFS em Java de Casey para percorrer todos os caminhos entre dois nós usando uma pilha. A legibilidade é melhor com recursiva como sempre.

    void DepthFirstIterative(T start, T endNode)
    {
        var visited = new LinkedList<T>();
        var stack = new Stack<T>();

        stack.Push(start);

        while (stack.Count != 0)
        {
            var current = stack.Pop();

            if (visited.Contains(current))
                continue;

            visited.AddLast(current);

            var neighbours = AdjacentNodes(current);

            foreach (var neighbour in neighbours)
            {
                if (visited.Contains(neighbour))
                    continue;

                if (neighbour.Equals(endNode))
                {
                    visited.AddLast(neighbour);
                    printPath(visited));
                    visited.RemoveLast();
                    break;
                }
            }

            bool isPushed = false;
            foreach (var neighbour in neighbours.Reverse())
            {
                if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
                {
                    continue;
                }

                isPushed = true;
                stack.Push(neighbour);
            }

            if (!isPushed)
                visited.RemoveLast();
        }
    }
Este é um gráfico de amostra para testar:

    // Gráfico de amostra. Números são ids de borda
    // 1 3       
    // A --- B --- C ----
    // | | 2 |
    // | 4 ----- D |
    // ------------------
Batta
fonte
1
excelente - sobre como você substituiu a recursão pela iteração baseada em pilha.
Siddhartha Ghosh
Ainda não entendo, o que é neighbours.Reverse()? É isso List<T>.Reverse ?
Verifiquei esta versão não recursiva, mas parece incorreta. a versão recursiva está bem. talvez quando alterado para não recursivo, um pequeno erro tenha acontecido
arslan
@alim: Concordo, este código está simplesmente quebrado. (Ele não remove corretamente os nós do conjunto visitado ao retroceder, e o manuseio da pilha também parece confuso. Tentei ver se poderia ser consertado, mas isso basicamente exigiria uma reescrita completa.) Acabei de adicionou uma resposta com uma solução não recursiva correta e funcional (em Python, mas deve ser relativamente fácil de portar para outras linguagens).
Ilmari Karonen
@llmari Karonen, Legal, vou verificar, ótimo trabalho.
arslan
1

Resolvi um problema semelhante a este recentemente, em vez de todas as soluções que estava interessado apenas na mais curta.

Eu usei uma pesquisa iterativa 'largura primeiro' que usou uma fila de status 'cada uma das quais continha um registro contendo um ponto atual no gráfico e o caminho percorrido para chegar lá.

você começa com um único registro na fila, que possui o nó inicial e um caminho vazio.

Cada iteração através do código tira o item do topo da lista e verifica se é uma solução (o nó que você chegou é aquele que você deseja, se for, estamos prontos), caso contrário, ele constrói um novo item de fila com os nós conectando-se ao nó atual e caminhos corrigidos que são baseados no caminho do nó anterior, com o novo salto anexado no final.

Agora, você poderia usar algo semelhante, mas quando encontrar uma solução, em vez de parar, adicione essa solução à sua 'lista de encontrados' e continue.

Você precisa manter o controle de uma lista de nós visitados, para que você nunca volte atrás em si mesmo, caso contrário, você terá um loop infinito.

se você quiser um pouco mais de pseudocódigo poste um comentário ou algo assim, e irei elaborar.


fonte
6
Acredito que se você estiver interessado apenas no caminho mais curto, o Algoritmo de Dijkstra é "a solução" :).
vicatcu
1

Acho que você deve descrever o seu verdadeiro problema por trás disso. Digo isso porque você pede algo eficiente em termos de tempo, mas o conjunto de respostas para o problema parece crescer exponencialmente!

Portanto, eu não esperaria um algoritmo melhor do que algo exponencial.

Eu voltaria atrás e examinaria todo o gráfico. Para evitar ciclos, salve todos os nós visitados ao longo do caminho. Quando você voltar, desmarque o nó.

Usando recursão:

static bool[] visited;//all false
Stack<int> currentway; initialize empty

function findnodes(int nextnode)
{
if (nextnode==destnode)
{
  print currentway 
  return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
  findnodes(n);
visited[nextnode]=false; 
pop from currenteay
}

Ou isso está errado?

editar: Ah, e eu esqueci: você deve eliminar as chamadas recursivas utilizando aquela pilha de nós

Jason Plank
fonte
Meu verdadeiro problema é exatamente como descrevi, apenas com conjuntos muito maiores. Eu concordo que isso parece crescer exponencialmente com o tamanho do conjunto.
Robert Groves
1

O princípio básico é que você não precisa se preocupar com gráficos. Esse é um problema padrão conhecido como problema de conectividade dinâmica. Existem seguintes tipos de métodos a partir dos quais você pode fazer com que os nós estejam conectados ou não:

  1. Busca rápida
  2. União Rápida
  3. Algoritmo aprimorado (combinação de ambos)

Aqui está o código C que tentei com complexidade de tempo mínima O (log * n) Isso significa que para 65536 lista de arestas, é necessário 4 pesquisas e 2 ^ 65536, 5 pesquisas. Estou compartilhando minha implementação do algoritmo: Curso de Algoritmo da Universidade de Princeton

DICA: Você pode encontrar a solução Java no link compartilhado acima com as explicações adequadas.

/* Checking Connection Between Two Edges */

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

/*
  Data structure used

vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/

/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);

int main() //Main Function
{ 
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;


printf("Enter the filename - "); //Accept File Name
scanf("%s", filename);
fp = fopen(filename, "r");
if (fp == NULL)
{
    printf("File does not exist");
    exit(1);
}
while (1)
{
    if (first == 0) //getting no. of vertices
    {
        ch = getc(fp);
        if (temp == 0)
        {
            fseek(fp, -1, 1);
            fscanf(fp, "%s", &ch1);
            fseek(fp, 1, 1);
            temp = 1;
        }
        if (isdigit(ch))
        {
            size = atoi(ch1);
            vertex = (int*) malloc(size * sizeof(int));     //dynamically allocate size  
            sz = (int*) malloc(size * sizeof(int));
            initalize(vertex, sz, size);        //initialization of vertex[] and sz[]
        }
        if (ch == '\n')
        {
            first = 1;
            temp = 0;
        }
    }
    else
    {
        ch = fgetc(fp);
        if (isdigit(ch))
            temp = temp * 10 + (ch - 48);   //calculating value from ch
        else
        {
            /* Validating the file  */

            if (ch != ',' && ch != '\n' && ch != EOF)
            {
                printf("\n\nUnkwown Character Detected.. Exiting..!");

                exit(1);
            }
            if (ch == ',')
                node1 = temp;
            else
            {
                node2 = temp;
                printf("\n\n%d\t%d", node1, node2);
                if (node1 > node2)
                {
                    temp = node1;
                    node1 = node2;
                    node2 = temp;
                }

                /* Adding the input nodes */

                if (!connected(vertex, node1, node2))
                    add(vertex, sz, node1, node2);
            }
            temp = 0;
        }

        if (ch == EOF)
        {
            fclose(fp);
            break;
        }
    }
}

do
{
    printf("\n\n==== check if connected ===");
    printf("\nEnter First Vertex:");
    scanf("%d", &node1);
    printf("\nEnter Second Vertex:");
    scanf("%d", &node2);

    /* Validating The Input */

    if( node1 > size || node2 > size )
    {
        printf("\n\n Invalid Node Value..");
        break;
    }

    /* Checking the connectivity of nodes */

    if (connected(vertex, node1, node2))
        printf("Vertex %d and %d are Connected..!", node1, node2);
    else
        printf("Vertex %d and %d are Not Connected..!", node1, node2);


    printf("\n 0/1:  ");

    scanf("%d", &temp);

} while (temp != 0);

free((void*) vertex);
free((void*) sz);


return 0;
}

void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
    vertex[i] = i;
    sz[i] = 0;
}
}
int root(int *vertex, int i)    //obtaining the root
{
while (i != vertex[i])
{
    vertex[i] = vertex[vertex[i]];
    i = vertex[i];
}
return i;
}

/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);

/* Adding small subtree in large subtree  */

if (sz[i] < sz[j])
{
    vertex[i] = j;
    sz[j] += sz[i];
}
else
{
    vertex[j] = i;
    sz[i] += sz[j];
}

}

/* Time Complexity for Search -->lg* n */

int connected(int *vertex, int p, int q) //Checking of  connectivity of nodes
{
/* Checking if root is same  */

if (root(vertex, p) == root(vertex, q))
    return 1;

return 0;
}
Avinash
fonte
Isso não parece resolver o problema conforme solicitado. O OP deseja encontrar todos os caminhos simples entre os dois nós, não apenas verificar se existe um caminho.
Ilmari Karonen
1

find_paths [s, t, d, k]

Esta pergunta é antiga e já foi respondida. No entanto, nenhum mostra talvez um algoritmo mais flexível para realizar a mesma coisa. Então, vou jogar meu chapéu no ringue.

Eu pessoalmente acho find_paths[s, t, d, k]útil um algoritmo do formulário , onde:

  • s é o nó inicial
  • t é o nó alvo
  • d é a profundidade máxima para pesquisar
  • k é o número de caminhos para encontrar

Usando a forma infinita de sua linguagem de programação para dek lhe dará todos os caminhos§.

§ obviamente, se você estiver usando um grafo dirigido e você quer todos sem direção caminhos entre se tvocê terá que executar este em ambos os sentidos:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

Função Auxiliar

Eu pessoalmente gosto de recursão, embora possa ser difícil algumas vezes, de qualquer forma, primeiro vamos definir nossa função auxiliar:

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

Função principal

Com isso fora do caminho, a função central é trivial:

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

Primeiro, vamos notar algumas coisas:

  • o pseudo-código acima é um mash-up de linguagens - mas muito parecido com o python (já que eu estava apenas codificando nele). Uma cópia e colagem estrita não funcionará.
  • [] é uma lista não inicializada, substitua-a pelo equivalente para sua linguagem de programação de escolha
  • paths_foundé passado por referência . É claro que a função de recursão não retorna nada. Lide com isso de forma adequada.
  • aqui graphestá assumindo alguma forma de hashedestrutura. Existem várias maneiras de implementar um gráfico. De qualquer forma, graph[vertex]obtém uma lista de vértices adjacentes em um gráfico direcionado - ajuste de acordo.
  • isso pressupõe que você pré-processou para remover "fivelas" (auto-loops), ciclos e arestas múltiplas
SumNeuron
fonte
0

Aqui está um pensamento que surgiu na minha cabeça:

  1. Encontre uma conexão. (Pesquisa em profundidade é provavelmente um bom algoritmo para isso, já que o comprimento do caminho não importa.)
  2. Desative o último segmento.
  3. Tente encontrar outra conexão do último nó antes da conexão desativada anteriormente.
  4. Vá para 2 até que não haja mais conexões.
Ryan Fox
fonte
Isso não funcionará em geral: é bem possível que dois ou mais caminhos entre os vértices tenham a mesma última aresta. Seu método encontraria apenas um desses caminhos.
Ilmari Karonen
0

Pelo que eu posso dizer, as soluções fornecidas por Ryan Fox ( 58343 , Christian ( 58444 ) e você ( 58461 ) são as melhores possíveis . Não acredito que a travessia em largura ajude neste caso, como você irá não obter todos os caminhos. Por exemplo, com bordas (A,B), (A,C), (B,C), (B,D)e (C,D)você vai ter caminhos ABDe ACD, mas não ABCD.

Mweerden
fonte
mweerden, A travessia em largura que enviei encontrará TODOS os caminhos, evitando todos os ciclos. Para o gráfico que você especificou, a implementação encontra corretamente todos os três caminhos.
Casey Watson,
Não li seu código completamente e presumi que você usou uma travessia de largura (porque você disse isso). No entanto, em uma inspeção mais detalhada após seu comentário, percebi que de fato não é. Na verdade, é uma travessia sem memória em primeiro lugar, como as de Ryan, Christian e Robert.
mweerden
0

Encontrei uma maneira de enumerar todos os caminhos, incluindo os infinitos que contêm loops.

http://blog.vjeux.com/2009/project/project-shortest-path.html

Encontrando Caminhos Atômicos e Ciclos

Definition

O que queremos fazer é encontrar todos os caminhos possíveis que vão do ponto A ao ponto B. Uma vez que existem ciclos envolvidos, você não pode simplesmente percorrer e enumerar todos eles. Em vez disso, você terá que encontrar o caminho atômico que não faça loop e os menores ciclos possíveis (você não quer que seu ciclo se repita).

A primeira definição que fiz de um caminho atômico é um caminho que não passa pelo mesmo nó duas vezes. Porém, descobri que não estava aproveitando todas as possibilidades. Após alguma reflexão, descobri que os nós não são importantes, mas as bordas são! Portanto, um caminho atômico é um caminho que não passa pela mesma borda duas vezes.

Esta definição é útil, ela também funciona para ciclos: um ciclo atômico do ponto A é um caminho atômico que vai do ponto A e termina no ponto A.

Implementação

Atomic Paths A -> B

Para obter todo o caminho a partir do ponto A, vamos percorrer o gráfico recursivamente a partir do ponto A. Ao passar por um filho, faremos um link filho -> pai para conhecer todas as arestas que já cruzou. Antes de irmos para aquela criança, devemos percorrer essa lista vinculada e ter certeza de que a borda especificada ainda não foi percorrida.

Quando chegamos ao ponto de destino, podemos armazenar o caminho que encontramos.

Freeing the list

Um problema ocorre quando você deseja liberar a lista vinculada. É basicamente uma árvore encadeada na ordem inversa. Uma solução seria fazer um duplo link dessa lista e, quando todos os caminhos atômicos forem encontrados, liberar a árvore do ponto de partida.

Mas uma solução inteligente é usar uma contagem de referência (inspirada na Garbage Collection). Cada vez que você adiciona um link para um dos pais, você adiciona um à sua contagem de referência. Então, ao chegar ao final de um caminho, você retrocede e fica livre enquanto a contagem de referência é igual a 1. Se for maior, basta remover um e parar.

Atomic Cycle A

Procurar o ciclo atômico de A é o mesmo que procurar o caminho atômico de A para A. No entanto, existem várias otimizações que podemos fazer. Em primeiro lugar, ao chegarmos ao ponto de destino, queremos salvar o caminho apenas se a soma dos custos das arestas for negativa: queremos apenas passar por ciclos absorventes.

Como você viu anteriormente, todo o gráfico está sendo percorrido ao procurar um caminho atômico. Em vez disso, podemos limitar a área de pesquisa ao componente fortemente conectado que contém A. Encontrar esses componentes requer uma simples travessia do gráfico com o algoritmo de Tarjan.

Combinando Caminhos Atômicos e Ciclos

Neste ponto, temos todos os caminhos atômicos que vão de A a B e todos os ciclos atômicos de cada nó, que nos resta organizar tudo para obter o caminho mais curto. A partir de agora vamos estudar como encontrar a melhor combinação de ciclos atômicos em um caminho atômico.

Vjeux
fonte
Isso não parece responder à pergunta feita.
Ilmari Karonen
0

Conforme habilmente descrito por alguns dos outros cartazes, o problema em poucas palavras é o de usar um algoritmo de pesquisa em profundidade para pesquisar recursivamente no gráfico todas as combinações de caminhos entre os nós finais em comunicação.

O algoritmo em si começa com o nó inicial que você fornece, examina todos os seus links de saída e progride expandindo o primeiro nó filho da árvore de pesquisa que aparece, pesquisando cada vez mais profundamente até que um nó de destino seja encontrado ou até encontrar um nó que não tem filhos.

A pesquisa então retrocede, retornando ao nó mais recente que ainda não terminou de explorar.

Eu fiz um blog sobre esse assunto recentemente, postando um exemplo de implementação C ++ no processo.

AndyUK
fonte
0

Somando-se à resposta de Casey Watson, aqui está outra implementação Java. Inicializando o nó visitado com o nó inicial.

private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
                LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
                for(String node : adjacent){
                    if(visitedNodes.contains(node)){
                        continue;
                    }
                    if(node.equals(END)){
                        visitedNodes.add(node);
                        printPath(visitedNodes);
                        visitedNodes.removeLast();
                    }
                    visitedNodes.add(node);
                    getPaths(graph, visitedNodes);
                    visitedNodes.removeLast();  
                }
            }
Jamshed Katta
fonte