Algorithme de graphe pour rechercher toutes les connexions entre deux sommets arbitraires

Question

Je suis en train de déterminer le meilleur moment algorithme efficace pour accomplir la tâche décrite ci-dessous.

J'ai un ensemble d'enregistrements. Pour cet ensemble de documents que j'ai données de connexion qui indique comment les paires de documents à partir de cet ensemble se connecter l'un à l'autre. En fait cela représente un graphe non-dirigé, avec les dossiers, les sommets et les données de connexion des bords.

Tous les enregistrements dans l'ensemble disposer des informations de connexion (c'est à dire pas des enregistrements orphelins sont présents; chaque enregistrement dans le jeu se connecte à un ou plusieurs autres enregistrements dans le jeu).

Je veux choisir deux enregistrements de l'ensemble et être en mesure de montrer tous les chemins entre les dossiers choisis. Par "chemins", je veux dire les chemins qui n'ont pas répété les dossiers dans le chemin d'accès (c'est à dire fini les chemins d'accès uniquement).

Remarque: Les deux dossiers choisi sera toujours différent (c'est à dire de début et de fin de sommet ne sera jamais la même; pas de cycles).

Par exemple:

 Si j'ai les documents suivants:
 A, B, C, D, E

 et le suivant représente les connexions: 
(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)

 [si (A,B) les moyens d'enregistrer Un se connecte à enregistrer B]

Si j'ai choisi B comme mon enregistrement de début et E comme mon enregistrement de fin, je voudrais trouver tous les chemins à travers le record de connexions permettant la connexion de dossier B dossier E.

 Tous les chemins reliant B à E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E

Ceci est un exemple, dans la pratique, j'ai peut-être des ensembles contenant des centaines de milliers d'enregistrements.

Answer 1

Robert,

Il semble que cela peut être accompli avec une largeur tout d'abord la recherche de la graphique. La largeur de la première recherche permettra de trouver tous les non-cyclique des chemins entre deux nœuds. Cet algorithme doit être très rapide et à l'échelle de grands graphes (La structure de données de graphe est peu dense, donc il n'utilise plus de mémoire que nécessaire).

J'ai remarqué que le graphique que vous avez spécifié ci-dessus n'a qu'un bord qui est directionnelle (B,E). Était-ce une faute de frappe ou est-il vraiment un graphe orienté? Cette solution fonctionne indépendamment. Désolé, j'étais incapable de le faire en C, je suis un peu faible dans ce domaine. J'espère que vous serez en mesure de traduire ce code Java sans trop de difficultés.

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().breadthFirst(graph, visited);
    }

    private void breadthFirst(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;
            }
        }
        // in breadth-first, recursion needs to come after visiting adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            breadthFirst(graph, visited);
            visited.removeLast();
        }
    }

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

Programme De La Sortie

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

Answer 2

Le dictionnaire en ligne des algorithmes et des structures de données du NIST (Institut national des normes et de la technologie) répertorie ce problème en tant que " chemins simples" et recommande une recherche approfondie en premier . CLRS fournit les algorithmes pertinents.

Une technique intelligente utilisant les réseaux de Petri se trouve ici

Answer 3

Voici le pseudo-code, je suis venu avec. Ce n'est pas tout particulier pseudocode dialecte, mais devrait être assez simple à suivre.

Quelqu'un veut-il prendre cette part.

• [p] est une liste de sommets représentant le chemin d'accès actuel.

• [x] est une liste de chemins d'accès là où se rencontrent les critères

• [s] est la source de vertex

• [d] est la destination de vertex

• [c] l'actuel sommet (argument de la Trouver routine)

Supposons qu'il existe un moyen efficace pour rechercher les sommets adjacents (ligne 6).

 1 PathList [p]
 2 ListOfPathLists [x]
 3 Vertex [s], [d]

 4 Trouver ( Vertex [c] )
 5 Ajouter [c] à l'extrémité de la queue de la liste [p]
 6 Pour chaque Vertex [v] adjacente à [c]
 7 Si [v] est égal à [d] puis
 8 Enregistrer la liste [p] [x]
 9 Sinon Si [v] n'est pas dans la liste [p]
 10 Trouver([v])
 11 Côté Pour
 12 Retirez la queue de [p]
 13 Retour

Answer 4

Solution en code C Il est basé sur DFS qui utilise une mémoire minimale.

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

}