图的遍历
图的遍历
深度优先遍历DFS
很想走迷宫，我们为了不重复的走，可以约定一个右手原则：
在没有碰到顶点的情况下，分叉路口始终是向右手边走，每路过一个顶点就做一个标记。
很像是递归，也很像是树的前序遍历。
遍历顺序如下图：
蓝色是遵循右手原则走出来的，红色是已经走过重复了，不会再走的。只看蓝色的路线，ABCDEFGH(GFED)I,括号为发现ED已经重复而返回退到D直到出现I。
蓝色的树是前序遍历。
递归就是给一个条件，让程序自己向深处探索。
马踏棋盘问题
哈密尔顿路径
广度优先遍历BFS
和深度优先不一样，广度优先是从最明显到次明显，而不是深度排查一个地方，再深度排查另一个。
这样的排序和深度的那个图一个样子，但是整齐了很多。
很像层序遍历
可以用队列来实现，遍历的顺序是出队列的顺序。
最小生成树
通信网路和电路板
普利姆算法
克鲁斯卡尔算法