广度优先遍历
对于广度优先遍历，在每次遍历时，都试图把同一个级别的所有节点先遍历， 再遍历下一个级别的节点。它的实现方式是通过一个队列保存需要去遍历的节点， 在每次遍历到一个节点时，都把它的邻接节点放入队列（如果这个节点没有被遍历过的话）等待着被遍历， 这样能保证更深层次的节点会遍历在它的任何邻接节点的后面，因为它的邻接节点更先进入队列。
广度优先遍历可以用来求解无权图中的单源最短路径问题， 对于节点s，在它上面执行一次广度优先遍历就能求出各个节点和s相距的节点数， 这也就是它们到达节点s所需的距离。对于广度优先遍历， 算法首先会发现和s距离为k的所有节点，然后再去发现和s距离为k+1的节点。 这其实和Dijkstra算法是采用同样的思想，先找出和s距离更近的节点， 在这基础上再找出更远的节点，因为这样的话当确定好了更远节点的路径时， 就不需要反过来再去修改更近节点的路径，因为通过更远节点的路径肯定没有先前的那条路径好。
深度优先遍历
深度优先遍历与广度优先遍历不一样，在遍历到每一个节点时，尽量往更深节点去遍历， 遍历完之后再考虑同一个级别的节点。它的实现方式不需要队列， 直接通过递归函数就可以完成这个步骤。每次遍历到一个节点时，先把当前的节点设为已经遍历过， 然后在它的邻接节点上执行递归遍历的函数（没有遍历过的邻接节点）。如果对整个图进行深度优先遍历， 首先会选定一个节点，然后在它上面执行深度优先遍历，如果遍历到了所有节点就停止， 否则选择另一个没有遍历到的节点重复这个过程直至所有的节点都遍历完。在深度优先搜索的过程中， 会形成一棵棵以挑选出的节点为根的深度优先树组成的深度优先搜索森林。
在深度优先遍历遍历到每一个节点时，可以利用一个计数器记录遍历节点开始时的时间和结束时的时间， 依据这个时间来确定节点遍历的相对顺序。设节点v遍历的开始时间为d[v]，结束时间为f[v]， 那么时间区间[d[v], f[v]]就代表了这个节点处在遍历过程中的时间，更具体的说， 是节点处在递归函数的栈中的时间。因此对于任何节点u, v， [d[v], f[v]]和[d[u]， f[u]]只能是不相交或者是一个包含另一个。 （通过栈可能更好理解一点）
利用这样的计数器，可以完成对图的很多操作，比如说拓扑排序和有向图的连通性检查。
拓扑排序
拓扑排序是对于有向无环图的节点进行一次排序，使得对于任意的节点u, v，如果u有一条边到v， 那么u一定出现在v的前面。
利用深度优先遍历得到的f值，可以很容易地对节点进行拓扑排序：按f值的大小进行排序， 具有较大f值的节点排在前面。
可以利用f值进行排序是通过如下性质保证的：
如果f[u] > f[v]，那么一定没有从v到u的边。
要证明这个性质，可以考虑f[u] > f[v]的两种情况：
-
[d[u], f[u]]与[d[v], f[v]]不相交且在其之后，那么此时遍历完v之后， u还没开始遍历，此时不可能有v到u的边，因为如果有的话那么遍历v完成之前就会遍历u，矛盾。
-
[d[u], f[u]]包含[d[v], f[v]]，那么说明在遍历u结束之前遍历到了v，这样就存在一条从u到v的路径， 如果有v到u的边，就会形成一个环，与无环图矛盾。
有向图的强连通分量
对于处于有向图的同一个强连通分量的任意节点u, v，存在一条路径从u到v， 同时也存在一条路径从v到u。显然任意两个连通分量不能相交，目的是找出有向图中的所有强连通分量， 注意单个节点可以作为一个强连通分量。
利用深度优先遍历，可以确定有向图的所有强连通分量，方法如下：
- 首先通过一次深度优先遍历确定所有节点的f值
- 按f值倒序深度优先遍历原图的反图，在得到的深度优先搜索森林中， 处于同一棵深度优先搜索树中的节点组成一个强连通分量。
这个算法的正确性由下面的性质保证：
对于任意节点u,v，u,v处于同一强连通分量当且仅当它们在第2步中处于同一棵深度优先搜索树。
证明这个性质，不妨设f[u] > f[v]:
- 左边到右边, 如果u，v处于同一强连通分量，那么在反图中一定存在从u到v的路径， 那么遍历到u时一定会沿着这条路径遍历到v，保证了u，v在同一棵深度优先搜索树中。
-
右边到左边，如果u, v在同一棵深度优先搜索树中，说明在反图中有一条u到v的路径， 也就是原图有一条从v到u的路径，只需要证明原图有一条从u到v的路径即可。 和证明拓扑排序一样，f[u] > f[v]只有两种情况：
-
[d[u], f[u]]与[d[v], f[v]]不相交且在其之后，那么此时遍历完v之后， u还没开始遍历，由于存在从v到u的路径，那么遍历v完成之前就会遍历u，所以这种情况不可能。
-
[d[u], f[u]]包含[d[v], f[v]]，这种情况是唯一可能的情况，此时存在一条从u到v的路径
-
因此证明结束。
最小生成树
在最小生成树问题中，给定一个无向连通图G = (V, E)，从E中挑出权值和最小的|V| - 1条边， 使得这些节点依旧连通。
有两种算法求解最小生成树问题，而且两种算法都是贪心算法，都满足贪心算法的贪心选择性质。
Kruskal算法
在Kruskal算法中，每次都试图挑选权值最小的一条边， 但要保证添加这条边不会导致存在回路，如果会导致回路，则不考虑这条边。
可以很简单的通过修改最优解的方式证明这个算法的贪心选择性质，从而证明算法的正确性。
Prim算法
在Prim算法中，利用一个不断增长的集合S，这个集合原来只包含一个元素， 然后每次往集合S中添加一个节点，这个节点是V-S中距离S中任意节点最近的节点， 在把这个节点添加到S的同时，把这个节点和S中与这个节点最近的节点组成的边添加为最小生成树的边。 显然，Prim算法能够保证每次添加一条边时，都不会导致回路。
同样可以很简单的通过修改最优解的方式证明这个算法的贪心选择性质，从而证明算法的正确性。