数据结构与算法－图的遍历

void Dfs ( Graph g , int v ) {
    ArcNode *p ;
    printf ( "%d",v );
    // 置"已访问"标记
    visited [v] = 1; 
    // 取顶点表中v的边表头指针
    p = g.adjlist[v].firstarc ; 
    // 依次搜索v的邻接点
    while ( p != NULL ) { 
        // v的一个邻接点未被访问
        if ( ! visited[p->adjvex] ){
            // 沿此邻接点出发继续DFS
            Dfs ( g,p->adjvex ); 
        };
        // 取v的下一个邻接点
        p = p->nextarc ; 
    }
}

void Dfs ( Graph g , int v ) {
    int j ;
    printf ("%d",v ); 
    // 置"已访问"标记
    visited [v] = 1; 
    // n为顶点数，j为顶点编号
    for (j=0;j<n;j++){ 
        // 顺序访问矩阵的第v行结点
        m=g->arcs[v][j];
        // 如果v与j邻接，且j未被访问
        if(m&&!visited[j]){
            // 递归访问j
            Dfs (g,j) ; 
        }
    }
}

Bfs(Graph g,int v){ 
    // Q为链队列
    LkQue Q;
    ArcNode *p;
    InitQueue(&Q); 
    printf("%d",v); 
    // 置已访问标志 
    visited[v]=1;
    // 访问过的顶点入队列
    EnQueue(&Q,v); 

    while(!EmptyQueue(Q)){ 
        v=Gethead(&Q);
        // 顶点出队列 
        OutQueue(&Q); 
        // 找到v的第一个邻接点 
        p = g.adjlist[v].firstarc; 
        // 判断邻接点是否存在 
        while(p!=NULL){ 
            // 邻接点存在未被i方问
            if (visited[p->adjvex]){ 
                printf ("%d",p->adjvex); 
                // 置已访问标志 
                visited[p->adjvex]=1; 
                // 邻接点入队列
                EnQueue(&Q,p->adjvex);
            }
            //沿着v的邻接点链表顺序搜索
            p=p->nextarc
        }
    }
}

Bfs (Graph g, int v){
    // Q为链队列
    LkQue Q; 
    int j;
    InitQueue(&Q);
    // v为访问的起始结点
    printf("%d",v); 
    // 访问过的标志
    visited[v]=1; 
    EnQueue(&Q,v);
    // 判队列是否为空
    while ( !EmptyQueue(Q)) { 
        v=Gethead(&Q);
        // 出队列
        OutQueue(&Q); 
        // n为顶点数，变化j依次尝试v的可能邻接点
        for (j=0;j<n;j++) { 
            m=g->arcs[v][j];
            // 判断是否邻接点，且未被访问
            if (m && !visited[j]) { 
                printf("%d",j);
                // 置被访问标志
                visited[j]=1; 
                // 邻接点入队列
                EnQueue(&Q,j);
            }
        }
    }
}

int visited[vnum];
Count_Component(Graph g){
    int count ,v;
    // 初始化visted数组
    for(v=0;v<g.exnum;v++){
        visted[v]=0;
    };
    count = 0;
    for(v=0;v<g.vexnum;v++){
        if(!visited[v]){
            count++;
            printf("连通分量%d包含以下顶点：",count);
            Dfs(g,v);
            printf("\n");
        };
    };
    printf("共有%d个连通分量\n",count);
}