广度优先搜索BFS

bool visited[MAX_VERTEX_NUM];     //访问标记数组
void BFSTraverse(Graph G){
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE;
    InitQueue(Q);
    for(i=0;i<G.vexnum;++i)
        if(!visited[i])    //对每个连通分量调用一次BFS
             BFS(G, i);
}

//先访问再入队，出队的时候再把未被访问过的邻接点都访问并入队
void BFS(Graph G, int v){
    visited(v);
    visited[v]=TRUE;
    EnQueue(Q, v);
    while(!isEmpty(Q)){
        DeQueue(Q, v);
        for(w=FirstNeighbor(G, v);w>=0;w=NextNeighbor(G, v, w))
            if(!visited[w]){
                visited(w);
                visited[w]=TRUE;
                EnQueue(Q, w);
            }
    }
}

空间复杂度 O（|V|）
时间复杂度 邻接表O（|V|+|E|）
邻接矩阵O（|V|^2）

BFS求单源最短路径

void BFS_MIN_Distance(Graph G, int u)
{
    for(i=0;i<G.vexnum;++i)
        d[i]=∞;
    visited[u]=TRUE;
    d[u]=0;
    EnQueue(Q, u);
    while(!isEmpty(Q)){
        DeQueue(Q, u);
        for(w=FirstNeighbor(G, u);w>=0;w=NextNeighbor(G, u, w))
            if(!visited[w]){
                visited[w]=TRUE;
                d[w]=d[u]+1;
                EnQueue(Q, w)
            }
    }
}

深度优先搜索DFS

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G, v);
}

void DFS(Graph G, int v)
{
    visited(v);
    visited[v]=TRUE;
    for(w=FirstNeighbor(G, v);w>=0;w=NextNeighbor(G, v, w))
        if(!visited[w]){
            DFS(G, w);
        }
}

空间复杂度 O（|V|）
时间复杂度 邻接表O（|V|+|E|）
邻接矩阵O（|V|^2）

注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列唯一，但基于邻接表的不唯一。（生成树也不唯一）
连通图可得到广度/深度优先生成树，否则产生生成森林。