代码之家 › 专栏 › 技术社区 › ÐÐ¸ÑÐ°Ð¸Ð» Ð¥Ð°Ð¼ÑÐ¾ÐµÐ²

如何搜索链表图中两个节点之间的所有路径

c++

ÐÐ¸ÑÐ°Ð¸Ð» Ð¥Ð°Ð¼ÑÐ¾ÐµÐ² · 技术社区 · 9 年前

我使用一个基于邻接的多变量列表来绘制一个图。我已经销售了创建数据结构的所有特定功能,但我无法实现两点之间所有可能路线的搜索(。我想了很多,但不知道如何获得所有路线,而不仅仅是一条。我知道我必须使用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(。我知道它不太好:(

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

1 回复 | 直到 9 年前

Steeve 9 年前

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