图的遍历

1）广度优先遍历

void BFSTraverse(Graph G,Status(*visit)(int v)){
    //按广度优先搜索遍历非递归遍历图G，使用辅助队列和访问标志数组visited
    for(v=0;v<G.vexnum;v++)     visited[v]=FALSE;
    InitQueue(Q);
    for(v=0;v<G.vexnum;++v)
        if(!visited[v]){
            visited[v]=True;
            visit(v);
            EnQueue(Q,v);
            while(!QueueEmpty(Q)){
                DeQueue(Q,u);
                for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
                      if(!visited[w]){
                          visited[w]=True;
                        visit(w);
                        EnQueue(Q,w);
                      } //if
                } //while
        } //if
} //BFSTraverse

2）深度优先遍历

void DFSTraverse(Graph G,Statues(* Visit)(int v)){
    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){
    if(!visited[v]) {
        visit(G,v);
        visted[v]=TRUE;
    } //if
    while(w=FirstAdjVetex(G,v);w>=0;w=NextAdjVetex(G,v,w)){
        if(!visited[w]){
            DFS(G,w);
        } //if 
    } //while
} //DFSTraverse