有向图如何找出所有探索方法
我正在学习C++，想到一个问题。现在有一个有向图，如何找出从给定节点出发的所有探索方法？探索过的节点不需要重复探索，但是可以作为去往其他节点的通路重复访问。
数据保证一定能探索每个节点。
例如这个图，从0开始探索。
https://s21.ax1x.com/2024/11/17/pARiCcj.png
我的想法是，有
0 -> 1 -> 2 -> 1 -> 3
0 -> 1 -> 3 -> 1 -> 2
这两种探索方式。
想问，如果像DFS一样探索的话，如何避免循环的问题呢？ 数据结构与算法不是有图的遍历吗？ linnimei 发表于 2024-11-17 11:11
数据结构与算法不是有图的遍历吗？
但是图的遍历不是不会访问已经访问过的节点了吗，我希望它可以访问访问过的节点，但是不要死循环，像我举的例子那样的。 那你可以在 DFS 的时候判断一下，如果本结点已经 visit 过，并且会从本结点再进入下一个 DFS，就再输出一次，如果本结点的相邻结点全部访问完，就不再输出。 本帖最后由 ganbey 于 2024-11-17 13:47 编辑
DFS和BFS为了避免重复访问，都有一个辅助数组visited呀，在访问V_i前判断一下visited是否为1就好了~
编辑：噢对不起看错了，我再想一下。。。把DFS的判断条件改为visted是否为V_i的出度个数行不行？然后规定每次访问同一结点要走不同的出边？ zixiangcode 发表于 2024-11-17 13:03
那你可以在 DFS 的时候判断一下，如果本结点已经 visit 过，并且会从本结点再进入下一个 DFS，就再输出一次 ...
我本来也是这样想的，但是这样不够周全。
如图。
https://s21.ax1x.com/2024/11/17/pARepdA.png
访问路径为0 -> 1 -> 2 -> 4时，4的出边只有指向1，但是1的出边已经走过了，按照这种判断方法的话就会当成已经结束了，但3节点还没有访问。 ganbey 发表于 2024-11-17 13:38
DFS和BFS为了避免重复访问，都有一个辅助数组visited呀，在访问V_i前判断一下visited是否为1就好了~
编 ...
似乎也是不行的，举例看6楼。 明确一下概念，“探索”指的是“从一个点出发，每次可以沿以这个点为始点的任意一条有向边走到这条边的终点，最终所有点都被经过过，而每条有向边最多只被经过一次”吗？ Kuukyaku 发表于 2024-11-17 15:03
明确一下概念，“探索”指的是“从一个点出发，每次可以沿以这个点为始点的任意一条有向边走到这条边的终点 ...
不是的，边也可以重复走，只要不陷入死循环或者每个点都访问过可以任意走 miaopan 发表于 2024-11-17 13:41
我本来也是这样想的，但是这样不够周全。
如图。
那你这样是没有办法避免死循环的。以你这张图为例，事实上 1-2-4 形成了一个死循环，如果你通过 4 回到 1，又运行重复访问结点，那么 1 再走到 2 的时候它仍然可以选择走到 4 重复这个循环。除非你愿意加一个随机数种子让他 50% 概率选择从 2 到 3。
就是说，如果一个图的结点运行重复访问的话，那么就不可避免回到相同的路口做出相同的判断，除非你控制栈深，但是这对于较大数据的图也会失去效果。
页:
[1]
2