Estoy tratando de determinar el mejor algoritmo de tiempo eficiente para realizar la tarea que se describe a continuación.

Tengo un conjunto de registros. Para este conjunto de registros tengo datos de conexión que indican cómo los pares de registros de este conjunto se conectan entre sí. Básicamente, esto representa un gráfico no dirigido, en el que los registros son los vértices y los datos de conexión los bordes.

Todos los registros del conjunto tienen información de conexión (es decir, no hay registros huérfanos; cada registro del conjunto se conecta a uno o más registros del conjunto).

Quiero elegir dos registros del conjunto y poder mostrar todas las rutas simples entre los registros elegidos. Por "rutas simples" me refiero a las rutas que no tienen registros repetidos en la ruta (es decir, solo rutas finitas).

Nota: Los dos registros elegidos siempre serán diferentes (es decir, el vértice inicial y final nunca serán el mismo; no habrá ciclos).

Por ejemplo:

    Si tengo los siguientes registros:
        A B C D E

    y lo siguiente representa las conexiones: 
        (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)

        [donde (A, B) significa que el registro A se conecta al registro B]

Si elijo B como mi registro inicial y E como mi registro final, me gustaría encontrar todas las rutas simples a través de las conexiones de registro que conectarían el registro B con el registro E.

   Todos los caminos que conectan B con E:
      B-> E
      B-> F-> E
      B-> F-> C-> E
      B-> A-> C-> E
      B-> A-> C-> F-> E

Este es un ejemplo, en la práctica puedo tener conjuntos que contengan cientos de miles de registros.

Parece que esto se puede lograr con una búsqueda en profundidad del gráfico. La búsqueda en profundidad encontrará todas las rutas no cíclicas entre dos nodos. Este algoritmo debe ser muy rápido y escalar a gráficos grandes (la estructura de datos del gráfico es escasa, por lo que solo usa tanta memoria como necesita).

Noté que el gráfico que especificó arriba solo tiene un borde que es direccional (B, E). ¿Fue un error tipográfico o es realmente un gráfico dirigido? Esta solución funciona independientemente. Lo siento, no pude hacerlo en C, soy un poco débil en esa área. Sin embargo, espero que puedas traducir este código Java sin demasiados 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();
    }
}

Salida del programa:

B E 
B A C E 
B A C F E 
B F E 
B F C E 

El Diccionario en línea de Algoritmos y Estructuras de Datos del Instituto Nacional de Estándares y Tecnología (NIST) enumera este problema como " todos los caminos simples" y recomienda una búsqueda en profundidad . CLRS proporciona los algoritmos relevantes.

Aquí encontrará una técnica inteligente que utiliza redes de Petri.

Aquí está el pseudocódigo que se me ocurrió. Este no es un dialecto de pseudocódigo en particular, pero debería ser lo suficientemente simple de seguir.

Cualquiera quiere diferenciar esto.

• [p] es una lista de vértices que representan la ruta actual.

• [x] es una lista de rutas que cumplen los criterios

• [s] es el vértice fuente

• [d] es el vértice de destino

• [c] es el vértice actual (argumento de la rutina PathFind)

Suponga que hay una forma eficiente de buscar los vértices adyacentes (línea 6).

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

     4 PathFind (vértice [c])
     5 Agregue [c] al final de la lista [p]
     6 Para cada vértice [v] adyacente a [c]
     7 Si [v] es igual a [d] entonces
     8 Guardar lista [p] en [x]
     9 De lo contrario, si [v] no está en la lista [p]
    10 PathFind ([v])
    11 Siguiente para
    12 Quite la cola de [p]
    13 Regreso

Dado que la implementación de DFS no recursiva existente que se proporciona en esta respuesta parece estar rota, permítanme proporcionar una que realmente funcione.

Escribí esto en Python, porque lo encuentro bastante legible y ordenado por los detalles de implementación (y porque tiene la yieldpalabra clave útil para implementar generadores ), pero debería ser bastante fácil de migrar a otros lenguajes.

# 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 mantiene dos pilas paralelas: una que contiene los nodos anteriores en la ruta actual y otra que contiene el índice vecino actual para cada nodo en la pila de nodos (para que podamos reanudar la iteración a través de los vecinos de un nodo cuando lo sacamos la pila). Podría haber usado igualmente una sola pila de pares (nodo, índice), pero pensé que el método de dos pilas sería más legible y quizás más fácil de implementar para los usuarios de otros idiomas.

Este código también usa un visitedconjunto separado , que siempre contiene el nodo actual y cualquier nodo en la pila, para permitirme verificar de manera eficiente si un nodo ya es parte de la ruta actual. Si su lenguaje tiene una estructura de datos de "conjunto ordenado" que proporciona tanto operaciones push / pop eficientes como una pila y consultas de membresía eficientes, puede usar eso para la pila de nodos y deshacerse del visitedconjunto separado .

Alternativamente, si está utilizando una clase / estructura mutable personalizada para sus nodos, puede simplemente almacenar una marca booleana en cada nodo para indicar si se ha visitado como parte de la ruta de búsqueda actual. Por supuesto, este método no le permitirá ejecutar dos búsquedas en el mismo gráfico en paralelo, si por alguna razón desea hacerlo.

Aquí hay un código de prueba que demuestra cómo funciona la función dada anteriormente:

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

Ejecutar este código en el gráfico de ejemplo dado produce el siguiente resultado:

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

Tenga en cuenta que, si bien este gráfico de ejemplo no está dirigido (es decir, todos sus bordes van en ambos sentidos), el algoritmo también funciona para gráficos dirigidos arbitrarios. Por ejemplo, eliminar el C -> Bborde (eliminando Bde la lista de vecinos de C) produce el mismo resultado excepto por la tercera ruta ( A -> C -> B -> D), que ya no es posible.

PD. Es fácil construir gráficos para los cuales algoritmos de búsqueda simples como este (y los otros que se dan en este hilo) funcionan muy mal.

Por ejemplo, considere la tarea de encontrar todas las rutas de A a B en un gráfico no dirigido donde el nodo inicial A tiene dos vecinos: el nodo objetivo B (que no tiene otros vecinos que A) y un nodo C que es parte de una camarilla. de n +1 nodos, así:

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"),
}

Es fácil ver que el único camino entre A y B es el directo, pero un DFS ingenuo iniciado desde el nodo A desperdiciará O ( ¡ n !) Tiempo explorando inútilmente caminos dentro de la camarilla, aunque es obvio (para un humano) que ninguno de esos caminos puede conducir posiblemente a B.

También se pueden construir DAG con propiedades similares, por ejemplo, haciendo que el nodo inicial A conecte el nodo objetivo B y a otros dos nodos C ₁ y C ₂ , los cuales se conectan a los nodos D ₁ y D ₂ , los cuales se conectan a E ₁ y E ₂ , y así sucesivamente. Para n capas de nodos organizados así, una búsqueda ingenua de todos los caminos de A a B terminará perdiendo O (2 ⁿ ) tiempo examinando todos los posibles callejones sin salida antes de darse por vencido.

Por supuesto, la adición de un borde para el nodo de destino B a partir de uno de los nodos en la camarilla (distinto de C), o desde la última capa de la DAG, sería crear un exponencialmente gran número de posibles caminos de la A a B, y una El algoritmo de búsqueda puramente local no puede decir de antemano si encontrará tal ventaja o no. Por lo tanto, en cierto sentido, la baja sensibilidad de salida de estas búsquedas ingenuas se debe a su falta de conocimiento de la estructura global del gráfico.

Si bien hay varios métodos de preprocesamiento (como la eliminación iterativa de nodos de hoja, la búsqueda de separadores de vértices de un solo nodo, etc.) que podrían usarse para evitar algunos de estos "callejones sin salida de tiempo exponencial", no conozco ningún general Truco de preprocesamiento que podría eliminarlos en todos los casos. Una solución general sería verificar en cada paso de la búsqueda si el nodo de destino aún es accesible (usando una subbúsqueda) y retroceder temprano si no lo es, pero lamentablemente, eso ralentizaría significativamente la búsqueda (en el peor de los casos) , proporcionalmente al tamaño del gráfico) para muchos gráficos que no contienen esos callejones sin salida patológicos.

Aquí hay una versión recursiva lógicamente más atractiva en comparación con el segundo piso.

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

Salida del programa

B A C E 

B A C F E 

B E

B F C E

B F E 

Solución en código C. Se basa en DFS que utiliza un mínimo de memoria.

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

}

Esto puede ser tarde, pero aquí está la misma versión C # del algoritmo DFS en Java de Casey para recorrer todas las rutas entre dos nodos usando una pila. La legibilidad es mejor con recursivo como siempre.

    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 es un gráfico de muestra para probar:

    // Gráfico de muestra. Los números son ID de borde
    // 1 3       
    // A B C ----
    // | | 2 |
    // | 4 ----- D |
    // ------------------

He resuelto un problema similar a este recientemente, en lugar de todas las soluciones, solo me interesaba la más corta.

Usé una búsqueda iterativa de 'amplitud primero' que usaba una cola de estado, cada una de las cuales contenía un registro que contenía un punto actual en el gráfico y la ruta tomada para llegar allí.

comienza con un solo registro en la cola, que tiene el nodo inicial y una ruta vacía.

Cada iteración a través del código quita el elemento del encabezado de la lista y verifica si es una solución (el nodo al que llegó es el que desea, si lo es, hemos terminado), de lo contrario, construye un nuevo elemento de cola con los nodos que se conectan al nodo actual y rutas modificadas que se basan en la ruta del nodo anterior, con el nuevo salto adjunto al final.

Ahora, podría usar algo similar, pero cuando encuentre una solución, en lugar de detenerse, agregue esa solución a su 'lista encontrada' y continúe.

Debe realizar un seguimiento de una lista de nodos visitados, de modo que nunca retroceda sobre sí mismo, de lo contrario, tendrá un bucle infinito.

si quieres un poco más de pseudocódigo, publica un comentario o algo así, y te daré más detalles.

Creo que deberías describir tu problema real detrás de esto. Digo esto porque pides algo que ahorre tiempo, ¡pero el conjunto de respuestas al problema parece crecer exponencialmente!

Por lo tanto, no esperaría un algoritmo mejor que algo exponencial.

Haría retroceder y revisar todo el gráfico. Para evitar ciclos, guarde todos los nodos visitados a lo largo del camino. Cuando regrese, desmarque el nodo.

Usando recursividad:

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
}

¿O está mal eso?

editar: Ah, y lo olvidé: debes eliminar las llamadas recursivas utilizando esa pila de nodos

El principio básico es que no necesita preocuparse por los gráficos. Este es un problema estándar conocido como problema de conectividad dinámica. Existen los siguientes tipos de métodos desde los cuales puede lograr que los nodos estén conectados o no:

1. Búsqueda rápida
2. Unión rápida
3. Algoritmo mejorado (combinación de ambos)

Aquí está el código C que probé con una complejidad de tiempo mínima O (log * n) Eso significa que para la lista de bordes 65536, requiere 4 búsquedas y para 2 ^ 65536, requiere 5 búsquedas. Estoy compartiendo mi implementación del algoritmo: Curso de algoritmo de la Universidad de Princeton

SUGERENCIA: Puede encontrar la solución Java en el enlace compartido anteriormente con las explicaciones adecuadas.

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

buscar_rutas [s, t, d, k]

Esta pregunta es antigua y ya está respondida. Sin embargo, ninguno muestra quizás un algoritmo más flexible para lograr lo mismo. Así que arrojaré mi sombrero al ring.

Personalmente, encuentro find_paths[s, t, d, k]útil un algoritmo de la forma , donde:

• s es el nodo inicial
• t es el nodo objetivo
• d es la profundidad máxima para buscar
• k es el número de caminos para encontrar

Usando la forma de infinito de su lenguaje de programación para dy kle dará todas las rutas§.

§ obviamente, si está utilizando un grafo dirigido y desea que todos los no dirigidos caminos entre sy ttendrá que ejecutar este en ambos sentidos:

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

Función auxiliar

Personalmente, me gusta la recursividad, aunque a veces puede ser difícil, de todos modos primero definamos nuestra función de ayuda:

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

Función principal

Con eso fuera del camino, la función principal es trivial:

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

Primero, observemos algunas cosas:

• el pseudocódigo anterior es una combinación de lenguajes, pero se parece mucho a Python (ya que solo estaba codificando en él). Una copia y pegado estricta no funcionará.
• [] es una lista no inicializada, reemplácela con el equivalente para el lenguaje de programación de su elección
• paths_foundse pasa por referencia . Está claro que la función de recursividad no devuelve nada. Maneje esto apropiadamente.
• aquí graphestá asumiendo alguna forma de hashedestructura. Hay una gran cantidad de formas de implementar un gráfico. De cualquier manera, graph[vertex]obtiene una lista de vértices adyacentes en una dirección gráfico ; ajuste en consecuencia.
• esto supone que ha procesado previamente para eliminar "hebillas" (bucles automáticos), ciclos y bordes múltiples

Aquí hay un pensamiento que se me viene a la cabeza:

1. Encuentra una conexión. (La búsqueda en profundidad es probablemente un buen algoritmo para esto, ya que la longitud de la ruta no importa).
2. Desactive el último segmento.
3. Intente encontrar otra conexión desde el último nodo antes de la conexión previamente deshabilitada.
4. Vaya a 2 hasta que no haya más conexiones.

Por lo que puedo decir, las soluciones dadas por Ryan Fox ( 58343 , Christian ( 58444 ) y usted mismo ( 58461 ) son tan buenas como parece. No creo que el recorrido primero en amplitud ayude en este caso, como no obtener todos los caminos. Por ejemplo, con los bordes (A,B), (A,C), (B,C), (B,D)y (C,D)obtendrá caminos ABDy ACD, pero no ABCD.

Encontré una manera de enumerar todas las rutas, incluidas las infinitas que contienen bucles.

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

Encontrar trayectorias y ciclos atómicos

Definition

Lo que queremos hacer es encontrar todos los caminos posibles que van del punto A al punto B. Dado que hay ciclos involucrados, no puede simplemente pasar y enumerarlos todos. En cambio, tendrá que encontrar una ruta atómica que no se repita y los ciclos más pequeños posibles (no desea que su ciclo se repita).

La primera definición que tomé de una ruta atómica es una ruta que no pasa por el mismo nodo dos veces. Sin embargo, descubrí que no estaba aprovechando todas las posibilidades. Después de un poco de reflexión, descubrí que los nodos no son importantes, ¡sin embargo los bordes sí lo son! Entonces, un camino atómico es un camino que no pasa por el mismo borde dos veces.

Esta definición es útil, también funciona para ciclos: un ciclo atómico del punto A es una trayectoria atómica que va desde el punto A y termina en el punto A.

Implementación

Atomic Paths A -> B

Para obtener toda la ruta comenzando desde el punto A, vamos a recorrer el gráfico de forma recursiva desde el punto A. Mientras pasamos por un niño, vamos a hacer un vínculo niño -> padre para conocer todas las aristas que ya han cruzado. Antes de ir a ese hijo, debemos recorrer esa lista vinculada y asegurarnos de que no se haya recorrido el borde especificado.

Cuando llegamos al punto de destino, podemos almacenar el camino que encontramos.

Freeing the list

Ocurre un problema cuando desea liberar la lista vinculada. Básicamente es un árbol encadenado en orden inverso. Una solución sería vincular dos veces esa lista y, cuando se hayan encontrado todas las rutas atómicas, liberar el árbol del punto de partida.

Pero una solución inteligente es utilizar un recuento de referencias (inspirado en Garbage Collection). Cada vez que agrega un enlace a un padre, agrega uno a su recuento de referencias. Luego, cuando llega al final de un camino, retrocede y se libera mientras el recuento de referencia es igual a 1. Si es mayor, simplemente elimine uno y pare.

Atomic Cycle A

Buscar el ciclo atómico de A es lo mismo que buscar la ruta atómica de A a A. Sin embargo, hay varias optimizaciones que podemos hacer. Primero, cuando llegamos al punto de destino, queremos guardar la ruta solo si la suma del costo de los bordes es negativa: solo queremos pasar por ciclos de absorción.

Como ha visto anteriormente, todo el gráfico se recorre cuando se busca una ruta atómica. En cambio, podemos limitar el área de búsqueda al componente fuertemente conectado que contiene A. Encontrar estos componentes requiere un simple recorrido del gráfico con el algoritmo de Tarjan.

Combinando caminos y ciclos atómicos

En este punto, tenemos todos los caminos atómicos que van de A a B y todos los ciclos atómicos de cada nodo, nos queda organizar todo para obtener el camino más corto. A partir de ahora vamos a estudiar cómo encontrar la mejor combinación de ciclos atómicos en una trayectoria atómica.

Como lo describen hábilmente algunos de los otros carteles, el problema en pocas palabras es el de utilizar un algoritmo de búsqueda en profundidad para buscar de forma recursiva en el gráfico todas las combinaciones de rutas entre los nodos finales comunicantes.

El algoritmo en sí comienza con el nodo de inicio que le da, examina todos sus enlaces salientes y avanza expandiendo el primer nodo hijo del árbol de búsqueda que aparece, buscando progresivamente más y más profundamente hasta que se encuentra un nodo de destino, o hasta que encuentra un nodo. que no tiene hijos.

Luego, la búsqueda retrocede y regresa al nodo más reciente que aún no ha terminado de explorar.

Me escribió en su blog sobre este tema muy muy recientemente, la publicación de un ejemplo C ++ aplicación en el proceso.

Agregando a la respuesta de Casey Watson, aquí hay otra implementación de Java. Inicializando el nodo visitado con el nodo de inicio.

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