图的遍历

深度优先搜索（DFS, Depth First Search）

深度优先搜索是一种一头扎到底的遍历方法，选择一条路，尽可能不断地深入，遇到死路就回退，回退过程中如果遇到没探索的支路，就进入该支路继续深入。

例如一个小镇的每个地点都藏有可以实现愿望的光玉，现在要从0号出生点出发去收集所有的光玉。

二叉树的先序遍历本质上也可以认为是图的深度优先遍历。要想实现回溯，可以利用栈的先进后出的特性，也可以采用递归的方式，因为递归本身就是基于方法调用栈来实现的。

深度优先搜索

dfs(Vertex V)
    isVisited[V] = true
    for v in neighbors(V)
        if !isVisited[v]
            DFS(v)

广度优先搜索（BFS, Breadth First Search）

除了深度优先搜索一头扎到底的方法以外，还有一种方法就是首先把从源点相邻的顶点遍历，然后再遍历稍微远一点的顶点，再去遍历更远一点的顶点。

二叉树的层次遍历本质上也可以认为是图的广度优先遍历，需要借助队列来实现遍历。

广度优先搜索

bfs(Vertex V)
    isVisited[V] = true
    enqueue(Q, V)
    while !isEmpty(Q)
        V = dequeue(Q)
        for v in neighbors(V)
            if !isVisited[v]
                isVisited[v] = true
                enqueue(Q, v)