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

图的遍历即为从图G中某一顶点v出发，顺序访问各顶点一次。

为克服顶点的重复访问，设立辅助数组visited[]，若visited[i]为1，代表顶点已被访问过，若为0，代表顶点i未被访问过。

深度优先搜索法（DFS）

从图G(V,E)中任一顶点Vi开始，首先访问Vi，然后访问Vi的任一未访问过的邻接点Vj，再以Vj为新的出发点继续进行深度优先搜索，直到所有顶点都被访问过。

搜索到达某个顶点时(图中仍有顶点未被访问)，如果这个顶点的所有邻接点都被访问过，那么搜索就要回到前一 个被访问过的顶点，再从该顶点的下一未被访问的邻接 点开始深度优先搜索。

深度搜索的顶点的访问序列不是唯一的。

DFS算法分析：

1. 为克服顶点的重复访问，设立一标志向量visited [n]；

2. 图可用邻接矩阵或邻接表表示；

3. DFS规则具有递归性，故需用到栈。

DFS算法实现（邻接表）：

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 ; 
    }
}

DFS算法实现（邻接矩阵）：

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) ; 
        }
    }
}

DFS邻接表的实例：

 

广度优先搜索法（BFS）

从图G(V,E)中某一点Vi出发，首先访问Vi的所有邻接点（W1，W2，…，Wt），然后再顺序访问W1，W2， …，Wt的所有未被访问过的邻接点， 此过程直到所有顶点都被访问过。

BFS算法分析：

1. 为克服顶点的重复访问，设立一标志向量 visited[n]；

2. 图可用邻接矩阵或邻接表表示；

3. 顶点的处理次序先进先出，故需用到队列。

BFS算法实现（邻接表）：

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算法实现（邻接矩阵）：

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);
            }
        }
    }
}

BFS邻接表的实例：

 

求图的连通分量

1. 判断图的连通性

对图G调用一次DFS或BFS，得到一顶点集合，然后将之与V(G)比较，若两集合相等，则图G是连通图，否则就说明有未访问过的顶点，因此图不连通。

2. 求图的连通分量

从无向图的每个连通分量的一个顶点出发遍历， 则可求得无向图的所有连通分量。

算法实现：

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);
}

连通分量计算实例：