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.

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 

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

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

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 ₁ e C ₂ , ambos os quais se conectam aos nós D ₁ e D ₂ , ambos os quais se conectam a E ₁ e E ₂ 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 ⁿ ) 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.

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 

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);

}

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 |
    // ------------------

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.

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

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;
}

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

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.

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.

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.

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.

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();  
                }
            }