图结构是数据结构中最复杂的一种结构，而“图”又可以描述日常应用中的绝大多数关系，所以有必要对图结构的一些基本算法有所了解。

广度优先算法 BFS

核心是一个队列这个数据结构，依据FIFO规则.

下面是一个非递归版本的伪代码：

Algorithm: BFS()
Input: A graph and a start vertex
output: Depend on problem

Function BFS(graph G, vertex node)
    init an empty queue Q
    mark node as visted
    Q.enqueue(node)
    while(Q is not empty):
        current=Q.dequeue()
        for each vertex u in G.adj[current]:
            if(u is unvisited):
                mark u as visited
                Q.enqueue(u)
            endif
        endfor
    endwhile

深度优先算法 DFS

核心其实就是将队列换成了栈：

Algorithm: DFS
Input: An undirected graph G and a starting vertex
Output: depends on problem

Fn DFS(graph G, vertex s)
    init an empty stack Q
    mark node as visted
    Q.push(node)
    while(Q is not empty):
        current=Q.pop()
        for each vertex u in G.adj[current]:
            if(u is unvisited):
                mark u as visited
                Q.push(u)
            endif
        endfor
    endwhile

当然很多时候我们其实也会写递归版本，逻辑上看起来更加清晰。下面是一个C++实现的遍历输出：

Algorithm: DFS(G, s)
Input: Graph G, current vertex s
Output: Traversal of the graph in depth-first order

Fn DFS(graph G, vertex s)
    mark s as visited
    for each vertex v in G.adj[s]:
        if (v is unvisited):
            DFS(G, v)
        endif
    endfor

NOTE:一个需要注意的点是，当我们讨论递归时，都是指深度遍历，这是递归的属性天然决定的，不断深入。BFS要体现的是一种“层级感”。

应用：检查(u,v)之间是否存在路径

可以直接以 u 作为顶点遍历，遍历过程中遇到 v 则意味着存在路径，否则不存在。

应用：检查连通分量的数量

选取任何一种遍历算法，每次遍历都可以获得一个连通分量。只需要在循环外设置一个计数器即可：

Algorithm: Connected_Components
Input: An undirected graph G
Output: the number of connected components

Fn Connected_Component(graph G)
    set count=0
    mark all vertex as unvisited
    for each vertex u in G:
        if (u is unvisited):
            count++
            DFS(G, u) // or you can use BFS(G, u)
                      // This would label all the node in same connected components
        endif
    endfor

    return count