图的两种遍历算法——BFS和DFS

一、BFS，也称广度优先搜索，和二叉树的层次遍历算法类似

//BFS
bool visited[MaxVertexNum];
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(G,i);
}
void BFS(Graph G,int v){
    visit(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]){
            visit(w);
            visited[w]=TRUE;
            EnQueue(Q,w);
        }
    }
}

二、DFS，也称深度优先搜索，类似于二叉树的先序遍历

//DFS
bool visited[MaxVertexNum];
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){
    visit(v);
    visited[v]=TRUE;
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        if(!visited[w]){
            DFS(G,w);
        }
}