图 - 邻接表 C++ - 从源到目标的所有路径

Question

我正在尝试查找图中从源节点到目标节点的所有路径。该图是有向的。我正在使用一个相当简单的邻接表表示法来表示 C++ 图形。这是我用于节点的内容：

struct node
    {
        int id;
        std::vector <int> neighbours;
    };

邻居是您可以从一个节点到达的节点。

这是我用来存储整个图的：

std::vector < node > graph;

示例：

对于上图，使用代码：

for(int i=0;i<graph.size();i++)
    {
        std::cout<<graph[i].id<<"->";
        for(int j=0;j<graph[i].neighbours.size();j++)
        {
            std::cout<<graph[i].neighbours[j].id;
            if(j!=graph[i].neighbours.size()-1)
                std::cout<<",";
        }
        std::cout<<std::endl;
    }

正确地为我提供了所有邻接关系：

0->1,4,3

1->2

2->3

3->

4->2

现在，我想写这样一个函数：

void find_paths(int start, int end)

当你给出起点和终点时，它会打印出从起点到终点的所有可能路径。

示例：当我运行、

find_paths(0,3) :

0->1->2->3

0->4>2>3

0->3

我想要这样的输出。性能在这里并不是真正的问题。任何工作算法都可以。我可以使用什么样的算法来解决这样的问题？另外，如果没有可能的路径，我怎样才能让函数识别这个？

Answer 1

看看Breadth first search and Depth first search。这两种方法都旨在以不同的顺序遍历图形以找到某个节点。

要获得所有解决方案而不仅仅是最短的解决方案，您可以保留一份在遍历过程中导致成功的所有路径的列表。

图 - 邻接表 C++ - 从源到目标的所有路径

Graph - Adjacency List C++ - All Paths from source to destination

c++

algorithm

graph-theory

graph

adjacency-list