如何搜索鏈接列表中兩個節點之間的所有路徑圖

Question

我使用基於鄰接的多變量列表的列表製作圖。我銷售了所有創建數據結構的特定函數，但我無法實現在兩點之間搜索所有可能的路線（（我想了很多，但無法弄清楚如何獲得所有方法，而不僅僅是一個。我知道我必須使用BFS，但我不能想出什麼（

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

是BFS我tryed作出（（我知道它不是那麼好:(

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

如果你的圖確實包含沒有任何邊連接的局部頂點組，那麼這個算法將無法訪問所有的邊，在這種情況下，而不是Pick any start node您應該遍歷所有節點並致電search。無論如何，已經訪問過的根節點都將被跳過。搜索後，不要忘記重置所有頂點的visited標誌！

編輯：

由於Михаил指出，這隻能找到一條路徑。要查找所有可能的路徑：你達到目標頂點可以保存路徑每次（你可以保持這種大幹快上的每個遞歸調用通過一個棧和頂點（或邊緣）加入，彈出這樣的：

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