无向图采用邻接表作为存储结构,设计一个C算法,求解该图的连通分量个数并输出各连通分量的顶点集。
时间: 2023-06-20 21:03:39 浏览: 163
以下是基于深度优先搜索(DFS)算法的C代码实现:
```c
#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; // 顶点数和边数
int visited[MAX_VERTEX_NUM]; // 标记各个顶点是否被访问过
} ALGraph;
// 创建邻接表存储的无向图
void createGraph(ALGraph *G) {
int i, j, k;
ArcNode *p;
printf("请输入顶点数和边数:\n");
scanf("%d %d", &G->vexnum, &G->arcnum);
printf("请输入顶点数据:\n");
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].first = NULL;
}
printf("请输入边的信息(顶点编号从0开始):\n");
for (k = 0; k < G->arcnum; k++) {
scanf("%d %d", &i, &j);
p = (ArcNode*) malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertices[i].first;
G->vertices[i].first = p;
p = (ArcNode*) malloc(sizeof(ArcNode));
p->adjvex = i;
p->next = G->vertices[j].first;
G->vertices[j].first = p;
}
}
// DFS遍历连通分量
void DFS(ALGraph G, int v, int *cnt) {
ArcNode *p;
G.visited[v] = 1;
printf("%d ", G.vertices[v].data);
(*cnt)++;
p = G.vertices[v].first;
while (p) {
if (!G.visited[p->adjvex]) {
DFS(G, p->adjvex, cnt);
}
p = p->next;
}
}
// 求连通分量并输出各连通分量的顶点集
void findConnectedComponent(ALGraph G) {
int i, cnt;
printf("连通分量个数:");
cnt = 0;
for (i = 0; i < G.vexnum; i++) {
if (!G.visited[i]) {
cnt = 0;
printf("\n{ ");
DFS(G, i, &cnt);
printf("},顶点个数:%d\n", cnt);
}
}
}
int main() {
ALGraph G;
createGraph(&G);
findConnectedComponent(G);
return 0;
}
```
该算法的主要思路是,从一个未访问的顶点出发,利用深度优先搜索遍历该顶点所在的连通分量,并统计其中的顶点个数。遍历时,需要记录每个顶点是否被访问过,以避免重复访问。最后,输出连通分量个数和各连通分量的顶点集。
可以通过以下方式测试该算法:
输入:
```
5 5
0 1 0 2 1 2 2 3 3 4
```
输出:
```
连通分量个数:
{ 0 1 2 },顶点个数:3
{ 3 4 },顶点个数:2
```
阅读全文