有向图如何找出所有探索方法

miaopan

我正在学习C++，想到一个问题。现在有一个有向图，如何找出从给定节点出发的所有探索方法？
探索过的节点不需要重复探索，但是可以作为去往其他节点的通路重复访问。
数据保证一定能探索每个节点。
例如这个图，从0开始探索。

我的想法是，有
0 -> 1 -> 2 -> 1 -> 3
0 -> 1 -> 3 -> 1 -> 2
这两种探索方式。
想问，如果像DFS一样探索的话，如何避免循环的问题呢？

linnimei

数据结构与算法不是有图的遍历吗？

miaopan

linnimei 发表于 2024-11-17 11:11
数据结构与算法不是有图的遍历吗？

但是图的遍历不是不会访问已经访问过的节点了吗，我希望它可以访问访问过的节点，但是不要死循环，像我举的例子那样的。

zixiangcode

那你可以在 DFS 的时候判断一下，如果本结点已经 visit 过，并且会从本结点再进入下一个 DFS，就再输出一次，如果本结点的相邻结点全部访问完，就不再输出。

ganbey

DFS和BFS为了避免重复访问，都有一个辅助数组visited[n]呀，在访问V_i前判断一下visited是否为1就好了~
编辑：噢对不起看错了，我再想一下。。。把DFS的判断条件改为visted是否为V_i的出度个数行不行？然后规定每次访问同一结点要走不同的出边？

miaopan

zixiangcode 发表于 2024-11-17 13:03
那你可以在 DFS 的时候判断一下，如果本结点已经 visit 过，并且会从本结点再进入下一个 DFS，就再输出一次 ...

我本来也是这样想的，但是这样不够周全。
如图。

访问路径为0 -> 1 -> 2 -> 4时，4的出边只有指向1，但是1的出边已经走过了，按照这种判断方法的话就会当成已经结束了，但3节点还没有访问。

miaopan

ganbey 发表于 2024-11-17 13:38
DFS和BFS为了避免重复访问，都有一个辅助数组visited[n]呀，在访问V_i前判断一下visited是否为1就好了~
编 ...

似乎也是不行的，举例看6楼。

Kuukyaku

明确一下概念，“探索”指的是“从一个点出发，每次可以沿以这个点为始点的任意一条有向边走到这条边的终点，最终所有点都被经过过，而每条有向边最多只被经过一次”吗？

miaopan

Kuukyaku 发表于 2024-11-17 15:03
明确一下概念，“探索”指的是“从一个点出发，每次可以沿以这个点为始点的任意一条有向边走到这条边的终点 ...

不是的，边也可以重复走，只要不陷入死循环或者每个点都访问过可以任意走

zixiangcode

miaopan 发表于 2024-11-17 13:41
我本来也是这样想的，但是这样不够周全。
如图。

那你这样是没有办法避免死循环的。以你这张图为例，事实上 1-2-4 形成了一个死循环，如果你通过 4 回到 1，又运行重复访问结点，那么 1 再走到 2 的时候它仍然可以选择走到 4 重复这个循环。除非你愿意加一个随机数种子让他 50% 概率选择从 2 到 3。
就是说，如果一个图的结点运行重复访问的话，那么就不可避免回到相同的路口做出相同的判断，除非你控制栈深，但是这对于较大数据的图也会失去效果。