So suchen Sie alle Pfade zwischen zwei Knoten in der verknüpften Liste Graph

Question

Ich mache ein Diagramm mit einer Liste von Adjazenz-basierte multivariable Liste. Ich habe alle bestimmten Funktionen verkauft, die eine Datenstruktur erstellen, aber ich kann die Suche nach allen möglichen Routen zwischen zwei Punkten nicht realisieren (. Ich dachte viel nach, aber konnte nicht herausfinden, wie man alle Wege bekommt, nicht nur einen. ich weiß, ich BFS verwenden müssen, aber ich kann nichts (

#include <iostream> 
    #include <string> 


using namespace::std; 

typedef string graphElement; 

typedef struct vertexTag { 
    graphElement data; 
    int visited; 

    struct edgeTag* edges; 

    struct vertexTag* next; 
    struct vertexTag* prev; 
} vertexT; 

typedef struct edgeTag { 
    struct vertexTag* connectsTo; 
    struct edgeTag* next; 
} edgeT; 

class graph { 
private: 
    vertexT* head; 
    vertexT* tail; 
    vertexT curr; 
    int count_vertex; 
    queue<vertexT*> queue; 

    void BFS(graphElement destenetion, vertexT* startP); 
    vertexT* FindVertex(graphElement data); 

public: 
    graph(); 
    ~graph(); 

    vertexT* AddVertex(graphElement data); 
    void DeleteVertex(graphElement data); 
    edgeT* AddEdge(graphElement source, graphElement destination); 
    void DeleteEdge(graphElement source, graphElement destination); 

    void PrintGraph(); 
    void DiskIn(); 
    void DiskOut(); 

    void FindAllPaths(graphElement source, graphElement destenetion); 
}; 

kommen ist es BFS i zu machen tryed zu ((. ich weiß, es ist nicht so gut :(

void graph::FindAllPaths(graphElement source, graphElement destenetion) { 
    vertexT *vertP; 
    vertexT *startP = NULL; 

    for (vertP = head; vertP != NULL; vertP = vertP->next) { 
     vertP->visited = 0; 
     if (vertP->data == source) 
      startP = vertP; 
    } 
    if (startP == NULL) 
    { 
     cout << "No such vertex"; 
     return; 
    } 
    else 
    { 
     BFS(destenetion, startP); 
    } 

} 

void graph::BFS(graphElement destenetion, vertexT* startP) { 
    vertexT* current; 
    edgeT* edgeP; 
    vector<string>path; 


    queue.push(startP); 
    //startP->visited = true; 

    while (!queue.empty()) { 
     current = queue.front(); 
     queue.pop(); 
     if (current->data == destenetion) 
      copy(path.begin(), path.end(), ostream_iterator<string>(cout, " ")); 
     for (edgeP = startP->edges; edgeP != NULL; edgeP = edgeP->next) { 
      //if (!edgeP->connectsTo->visited) { 
       queue.push(edgeP->connectsTo); 
       edgeP->connectsTo->visited = true; 
       path.push_back(edgeP->connectsTo->data); 
     // } 
     } 
    } 
} 

Answer 1

start = Pick any start node 
search(start) 

function search(node) { 
    node.visited = yes 
    for each vertex that has an edge to node (call it b): { 
    if (b not visited) { 
     search(b) // recursive call to search 
    } 
    } 
} 

Wenn Ihr Diagramm lokale Gruppen von Scheitelpunkten enthält, die nicht durch eine Kante verbunden sind, kann dieser Algorithmus nicht alle aufrufen, in diesem Fall anstelle von Pick any start node sollten Sie über alle Knoten iterieren und search aufrufen. Bereits besuchte Wurzelknoten werden sowieso übersprungen. Vergessen Sie nach der Suche nicht, das Flag visited für alle Scheitelpunkte zurückzusetzen!

EDIT:

Als Михаил, das nur einen Weg finden, wird hingewiesen. Um alle möglichen Pfade: Jedes Mal, wenn Sie das Ziel erreichen Vertex Sie die Route speichern können (Sie können einen Stapel halten, die auf jedem rekursiven Aufruf übergeben werden, und Ecken (oder Kanten) hinzugefügt, tauchten wie folgt aus:

start = pick your start vertex 
target = pick your target vertex 
stack = empty stack 
search(start, start, target, stack) 
resultingPaths = vector of stacks // here go all possible routes 

function search(node, start, target, stack) { 
    for each vertex that has an edge to node (call it b): { 
    stack.push(b) 
    if (b == target) { 
     // we have found a path 
     resultingPaths.add(a copy of stack) 
    } else if (b != start) { 
     // keep looking 
     search(b, start, target, stack) // recursive call to search 
    } 
    stack.pop() 
    } 
}