用C语言编写已知无向图G=(V,E),给出求图G的连通分量个数的算法。
时间: 2024-04-16 09:26:19 浏览: 100
要求无向图G的连通分量个数,可以使用深度优先(DFS)算法来实现。具体的C语言代码如下:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTEX_NUM 100 // 图中顶点的最大个数
typedef struct ArcNode {
int adjvex; // 邻接顶点的位置
struct ArcNode *nextarc; // 指向下一个邻接顶点的指针
} ArcNode;
typedef struct VNode {
bool visited; // 访问标志,用于DFS
ArcNode *firstarc; // 指向第一个邻接顶点的指针
} VNode;
typedef struct {
VNode vertices[MAX_VERTEX_NUM]; // 存储顶点的数组
int vexnum; // 顶点个数
} ALGraph;
void DFS(ALGraph *G, int v) {
G->vertices[v].visited = true;
ArcNode *p = G->vertices[v].firstarc;
while (p != NULL) {
int adjvex = p->adjvex;
if (!G->vertices[adjvex].visited) {
DFS(G, adjvex);
}
p = p->nextarc;
}
}
int CountConnectedComponents(ALGraph *G) {
int count = 0; // 连通分量个数
for (int i = 0; i < G->vexnum; i++) {
G->vertices[i].visited = false;
}
for (int i = 0; i < G->vexnum; i++) {
if (!G->vertices[i].visited) {
DFS(G, i);
count++;
}
}
return count;
}
int main() {
ALGraph G;
int n, m; // n为顶点个数,m为边的个数
printf("请输入顶点个数和边的个数:");
scanf("%d%d", &n, &m);
G.vexnum = n;
printf("请输入边的信息(起始顶点、终止顶点):\n");
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));***
阅读全文