图与图的遍历
深度优先与广度优先遍历
从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组vis[i]，未访问时值为false，访问一次后就改为true。 图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是O(n*n)。
1. 深度优先遍历
深度优先遍历与深搜DFS相似，从一个点A出发，将这个点标为已访问vis[i]=true;，然后再访问所有与之相连，且未被访问过的点。当A的所有邻接点都被访问过后，再退回到A的上一个点（假设是B），再从B的另一个未被访问的邻接点出发，继续遍历。
例如对上图进行遍历：
我们约定，在没有碰到重复顶点的情况下，优先选择右手边
那么按深度优先遍历就是：A -> B -> C -> D -> E -> F -> G -> H (此时这条线路已经走到尽头，可是还有一个I顶点没有遍历，所以回到G，发现G的邻接点都遍历过了，再回到F，发现F的邻接点也都遍历过了。。。直到D顶点，发现I这个顶点没有遍历，所以把I再遍历，继续回溯，最终回到起点A)
void dfs(int i) { //图用数组模拟邻接表存储，访问点i
vis[i] = true; //标记为已经访问过
for (int j = hd[i]; j; j = eg[j].nx) //遍历与i相关联的所有未访问过的顶点
if (!vis[eg[j].to])
dfs(eg[j].to);
}2. 广度优先遍历
广度优先遍历并不常用，从编程复杂度的角度考虑，通常采用的是深度优先遍历。
广度优先遍历和广搜BFS相似，因此使用广度优先遍历一张图并不需要掌握什么新的知识，在原有的广度优先搜索的基础上，做一点小小的修改，就成了广度优先遍历算法。