[已解决]非连通无向图深度优先遍历

sususususu

算法设计题：假设一个无向图是非连通的，采用邻接表作为存储结构。设计一个算法，利用深度优先遍历方法求出该图连通分量个数。（用C语言解决）

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-12 00:24:39

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *next;
} ArcNode;

typedef struct VNode {
    int data;
    ArcNode *first;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int visited[MAX_VERTEX_NUM];

void DFS(ALGraph G, int v) {
    visited[v] = 1;
    ArcNode *p = G.vertices[v].first;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->next;
    }
}

int CountConnectedComponents(ALGraph G) {
    int count = 0;
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[ i]) {
            count++;
            DFS(G, i);
        }
    }
    return count;
}

int main() {
    // 初始化图 G
    ALGraph G;
    // 调用CountConnectedComponents函数求出连通分量个数
    int result = CountConnectedComponents(G);
    printf("连通分量个数为：%d\n", result);
    return 0;
}

解释：这段代码实现了利用深度优先搜索（DFS）方法求解无向图的连通分量个数。首先定义了邻接表的数据结构，然后使用DFS函数进行图的遍历，标记已访问的节点，并递归访问未访问的相邻节点。最后通过CountConnectedComponents函数统计连通分量个数并返回。在main函数中初始化图 G 并调用CountConnectedComponents函数求解连通分量个数，最终输出结果。

跳转到最佳答案楼层

isdkz

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *next;
} ArcNode;

typedef struct VNode {
    int data;
    ArcNode *first;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int visited[MAX_VERTEX_NUM];

void DFS(ALGraph G, int v) {
    visited[v] = 1;
    ArcNode *p = G.vertices[v].first;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->next;
    }
}

int CountConnectedComponents(ALGraph G) {
    int count = 0;
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[ i]) {
            count++;
            DFS(G, i);
        }
    }
    return count;
}

int main() {
    // 初始化图 G
    ALGraph G;
    // 调用CountConnectedComponents函数求出连通分量个数
    int result = CountConnectedComponents(G);
    printf("连通分量个数为：%d\n", result);
    return 0;
}

解释：这段代码实现了利用深度优先搜索（DFS）方法求解无向图的连通分量个数。首先定义了邻接表的数据结构，然后使用DFS函数进行图的遍历，标记已访问的节点，并递归访问未访问的相邻节点。最后通过CountConnectedComponents函数统计连通分量个数并返回。在main函数中初始化图 G 并调用CountConnectedComponents函数求解连通分量个数，最终输出结果。