如何计算图上任意两点之间的所有可能路径？

本文共计1739个文字，预计阅读时间需要7分钟。

基于连通图，实现邻接矩阵的图，非递归实现。

算法思想：+ 设置两个标志位，位0判断该点是否入栈，位1判断该点与入栈点是否相邻。+ 将起始点标志位设置为1，入栈。+ 查看栈顶元素，判断其相邻点是否入栈。+ 若未入栈，则设置其标志位并入栈。+ 重复上述步骤，直至栈为空。

基于连通图，邻接矩阵实现的图，非递归实现。

算法思想：

设置两个标志位，①该顶点是否入栈，②与该顶点相邻的顶点是否已经访问。

A 将始点标志位①置1，将其入栈

B 查看栈顶节点V在图中，有没有可以到达、且没有入栈、且没有从这个节点V出发访问过的节点

C 如果有，则将找到的这个节点入栈，这个顶点的标志位①置1，V的对应的此顶点的标志位②置1

D 如果没有，V出栈，并且将与v相邻的全部结点设为未访问，即全部的标志位②置0

E 当栈顶元素为终点时，设置终点没有被访问过，即①置0，打印栈中元素，弹出栈顶节点

F 重复执行B – E,直到栈中元素为空

先举一个例子吧

假设简单连通图如图1所示。假设我们要找出结点3到结点6的所有路径，那么，我们就设结点3为起点，结点6为终点。