有向图寻找环路python_有向图的深度优先搜索 —— 找出环路

一、目标

找出下图(有向图)中的回路

二、策略

1，深度优先搜索：顾名思义，就是从某个顶点开始探索，会一直探索到某个可能路径的尽头才会停止探索，并原路返回(下面的例子，

并不会一直原路返回到原点，而是每次原路返回一个顶点，就会探索从该点向下的所有路径情况，以此类推)；

2，按道理需要从1~7个点都探索一下，看有没有某个回路包含自己；为了简化，我们只从顶点1探索；

3，假设我手中有个笔记本，分别记录3件事情，如下：

我准备从房间1(如下图)开始探索如下图所示的区域，看能不能发现其中的某个回路(就像鬼打墙那样的回路，会一直路过相同的地方)；

三，实施

1，我进入房间1，发现有一把钥匙，可以打开房间1中的那两扇门；

A，然后房间1中还有一个柜子localCycles，我撕了一张空白的纸放进柜子中，准备记录一些东西：

B，我在我随身携带的本子上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

我使用房间1中的钥匙打开了东边的门，至于为什么选择东边的门而不是南边的门，我想可能是因为我没有强迫症吧，哪扇门都可以，哈哈；

D，我站在两个房间连接的过道上(其实还是在房间1中的)，发现下一个是房间3；

我得先拿出我随身携带的本子，看看有没有这个房间3的相关信息：

2，由于本子上并没有房间3的任何信息，所以我走进了房间3；

并且房间3看起来和房间1是一模一样，只是我并没有发现任何钥匙；

A，同样的，我会撕下一张空白的纸放进柜子localCycles中：

B，我在我随身携带的本子上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

因为我没有任何房间3的钥匙，所以即使房间3有门，我也是打不开的，何况，房间3也没有门；没得办法，没有更深的房间可以去了，这条路算是走到了尽头；

E，所以我在我的本子上记录如下内容：

F，我要原路返回(我用脑子记下了我来时的路，也可以记在本子上)了，我得带上房间3柜子里的纸片，因为回到房间1后，还需要用到它；

3，我使用房间1的钥匙又回到了房间1中，我看看上个房间也就是房间3带回来的纸片，发现上面一片空白：

我早就想好了，如果这张纸片是空白的，我就在我随身携带的本子上记录如下内容：

然后上个房间带回来的那张之前就没用了，扔了、吃了都随便；

回到房间1之后，我不能闲着，当务之急就是：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；使用房间1的钥匙打开房间1南边的门，因为我必须探索完这个房间向下的所有的路径；

D，我站在两个房间连接的过道上，发现下一个是房间2；

我拿出我的本子，看看有没有这个房间2的相关信息：

4，由于本子上并没有房间2的任何信息，所以我走进了房间2，并且房间2看起来和之前的房间是一模一样，并且有1把钥匙；

A，同样的，我会撕下一张空白的纸放进柜子localCycles中；

B，我在我的本子上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；我使用房间2中的钥匙打开了东边的门

D，我站在两个房间连接的过道上，发现下一个是房间5；

我拿出我的本子，看看有没有这个房间5的相关信息：

5，由于本子上并没有房间5的任何信息，所以我走进了房间5，并且房间5看起来和之前的房间是一模一样，看来每个房间都是差不多的，而且房间5中也有一把钥匙；

A，同样的，我会撕下一张空白的纸放进柜子localCycles中；

B，我在我的本子上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；我使用房间5中的钥匙打开了东边的门

D，我站在两个房间连接的过道上，发现下一个是房间6；

我拿出我的本子，看看有没有这个房间6的相关信息：

6，由于本子上并没有房间6的任何信息，所以我走进了房间6，并且房间6看起来和之前的房间是一模一样，并且有1把钥匙；

A，同样的，我会撕下一张空白的纸放进柜子localCycles中；

B，我在我的本子上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；我使用房间6中的钥匙打开了南边的门，因为房间6只有南边一扇门；

D，我站在两个房间连接的过道上，发现下一个是房间7；

我拿出我的本子，看看有没有这个房间7的相关信息：

7，由于本子上并没有房间7的任何信息，所以我走进了房间7，并且房间7看起来和之前的房间是一模一样，并且有1把钥匙；

A，同样的，我会撕下一张空白的纸放进柜子localCycles中；

B，我在我的本子上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；我使用房间7中的钥匙打开了北边的门，因为房间7只有北边一扇门；

D，我站在两个房间连接的过道上，发现下一个是房间5；

我拿出我的本子，看看有没有这个房间5的相关信息：

8，我发现本子上有房间5的信息；并且，房间5的状态还是在探索中的；

这不就说明，在这条路线上出现了环路了吗；这个时候我就不能犯傻，一直开门、开门、开门往下走了，那必然会陷入无限的循环；

如果觉得这个节点很重要可以这么记录：

当然我的纸不够了，所以我记在脑子里，这个环路的起始节点是：房间5！

我得赶紧原路返回(可以记在本子上，也可以记在脑子里，原路是什么顺序)了，于是我用房间7的钥匙打开了房间7，并在柜子localCycles记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

发现并没有这样的门了，这种情况下我就：

E，我又在我的笔记本上记录如下两项内容：(下图第二张图的最新内容来源于本房间柜子里的记录)

F，我要原路返回了，我得带上房间7柜子里的纸片；

9，我使用房间6的钥匙，回到了房间6中；

我看看上个房间也就是房间7带回来的纸片，发现上面是这样的：

；

我早就想好了，如果这张纸片不是空白的，我就会在当前房间的柜子里的纸片上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

发现并没有这样的门了，这种情况下我就：

E，我又在我的笔记本上记录如下两项内容：(下图第二张图的最新内容来源于本房间柜子里的记录)

F，我要原路返回了，我得带上房间6柜子里的纸片；

10，返回房间5；

我看看上个房间也就是房间6带回来的纸片，发现上面是这样的：

；

同样的道理，如果这张纸片不是空白的，我就会在当前房间的柜子里的纸片上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

发现并没有这样的门了，这种情况下我就：

E，我又在我的笔记本上记录如下两项内容：(下图第二张图的最新内容来源于本房间柜子里的记录)

F，我要原路返回了，我得带上房间5柜子里的纸片；

11，我用房间2的钥匙返回房间2；

我看看上个房间也就是房间5带回来的纸片，发现上面是这样的：

；

同样的道理，如果这张纸片不是空白的，我就会在当前房间的柜子里的纸片上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

我使用房间2的钥匙，打开了房间北边的门；

D，我站在两个房间连接的过道上，发现下一个是房间4；

我拿出我的本子，看看有没有这个房间4的相关信息：

12，由于本子上并没有房间4的任何信息，所以我走进了房间4，并且房间4看起来和之前的房间是一模一样；

A，同样的，我会撕下一张空白的纸放进柜子localCycles中；

B， 我在我的本子上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

发现并没有这样的门了，这种情况下我就：

E，我在我在我的本子上记录如下内容：

F，我要原路返回了，我得带上房间4柜子里的纸片；

13，我使用房间2的钥匙又回到了房间2中，我看看上个房间也就是房间4带回来的纸片，发现上面一片空白；

同样的道理，如果这张纸片是空白的，我就在我随身携带的本子上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

发现并没有这样的门了，这种情况下我就：

E，我又在我的笔记本上记录如下两项内容：(下图第二张图的最新内容来源于本房间柜子里的记录)；

我得先在本房间，也就是房间2，看下柜子里的纸片：

所以两项内容是这样的：

F，我要原路返回了，我得带上房间2柜子里的纸片；

14，使用房间1的钥匙返回房间1

我看看上个房间也就是房间2带回来的纸片，发现上面是这样的：

;

同样的道理，如果这张纸片不是空白的，我就会在当前房间的柜子里的纸片上记录如下内容：

C，使用这个房间的钥匙去打开一扇未曾打开过的门；

发现并没有这样的门了，这种情况下我就：

E，我又在我的笔记本上记录如下两项内容：(下图第二张图的最新内容来源于本房间柜子里的记录)；

F，我要原路返回了，我得带上房间1柜子里的纸片；

额，已经在原点了....

四，总结

至此，从房间1的所有探所路径都已经探索结束了；是时候总结一下了：

这个图说明了一条含有环路的路径；

这个图好像被我搞砸了，只能说明某个没有环路的路径中包含这个表中的某个点。。。。。

五，拓展

其实以上内容只是简单的模拟了：java程序中，虚拟机中栈帧的变化情况，以及栈帧之间的关系；

涉及到栈帧的局部变量、堆的变量(是所有虚拟机栈(包括栈帧)共享的)、返回值的情况；最重要的就是虚拟机如何递归的过程。

六，未完待续

下回有时间，可以将虚拟机栈(某个线程)、堆的示意图画出来。