用C语言无向图采用邻接表作为存储结构,设计一个算法,求解该图的连通分量个数并输出各连通分量的顶点集。
时间: 2024-05-04 09:16:20 浏览: 130
实验_C++_数据结构_图连通分量_
5星 · 资源好评率100%
好的,我可以为您提供一个基于深度优先搜索(DFS)的算法来解决这个问题。
首先,我们需要定义邻接表和无向图的数据结构,比如:
```c
#include<stdio.h>
#include<stdlib.h>
// 邻接表中的边节点
typedef struct EdgeNode{
int vertex; // 相邻顶点的下标
struct EdgeNode *next; // 指向下一条边的指针
}EdgeNode;
// 邻接表中的顶点节点
typedef struct VertexNode{
int value; // 顶点存储的值
EdgeNode *first_edge; // 指向第一条边的指针
}VertexNode;
// 无向图的结构体
typedef struct UndirectedGraph{
VertexNode *vertices; // 存储顶点的数组
int vertex_num; // 顶点个数
}UndirectedGraph;
```
接下来,我们可以使用DFS来遍历所有连通分量。具体做法是,在图片中任选一个顶点,标记为已遍历后,遍历该顶点的所有邻居顶点,将邻居顶点标记为已遍历,并继续遍历邻居顶点的邻居顶点,以此类推。当无法再遍历到邻居顶点时,就找到了一个连通分量。
下面是基于DFS算法来实现求解无向图连通分量个数的示例代码:
```c
// DFS函数,用于遍历相邻顶点,并将遍历到的顶点标记为已遍历
void DFS(UndirectedGraph *graph, int i, int *visited, int *component) {
visited[i] = 1; // 将该顶点标记为已遍历
printf("%d ", graph->vertices[i].value);
component[i] = 1; // 将该顶点加入到当前连通分量中
// 遍历相邻顶点
EdgeNode *p = graph->vertices[i].first_edge;
while (p) {
int j = p->vertex;
if (!visited[j]) {
DFS(graph, j, visited, component);
}
p = p->next;
}
}
// 获取无向图的连通分量个数
int getComponentCount(UndirectedGraph *graph) {
int count = 0; // 连通分量个数
int *visited = (int*)malloc(graph->vertex_num * sizeof(int)); // 标记顶点是否已经遍历过
int *component = (int*)malloc(graph->vertex_num * sizeof(int)); // 标记某个顶点是否属于当前连通分量
// 初始化visited数组
for (int i = 0; i < graph->vertex_num; i++) {
visited[i] = 0;
}
// 遍历所有顶点
for (int i = 0; i < graph->vertex_num; i++) {
if (!visited[i]) { // 如果该顶点还未遍历过,则是一个新的连通分量
count++;
printf("component %d: ", count);
DFS(graph, i, visited, component); // 遍历连通分量中的所有顶点
printf("\n");
}
}
free(visited);
free(component);
return count;
}
```
在调用getComponentCount函数时,我们需要将无向图的邻接表数组作为参数传入,示例代码如下:
```c
int main() {
// 创建无向图
UndirectedGraph graph;
graph.vertex_num = 6;
graph.vertices = (VertexNode*)malloc(graph.vertex_num * sizeof(VertexNode));
for (int i = 0; i < graph.vertex_num; i++) {
graph.vertices[i].value = i+1;
graph.vertices[i].first_edge = NULL;
}
// 添加边
addEdge(&graph, 1, 2);
addEdge(&graph, 2, 3);
addEdge(&graph, 1, 5);
addEdge(&graph, 4, 5);
// 输出连通分量个数和各连通分量的顶点集
printf("component count = %d\n", getComponentCount(&graph));
// 释放内存
freeGraph(&graph);
return 0;
}
```
上面的示例代码中使用了addEdge函数来添加无向图的边,这个函数的实现可以参考以下代码:
```c
// 添加无向图的边
void addEdge(UndirectedGraph *graph, int i, int j) {
// 将j加入到i的邻接表中
EdgeNode *new_edge = (EdgeNode*)malloc(sizeof(EdgeNode));
new_edge->vertex = j;
new_edge->next = graph->vertices[i-1].first_edge;
graph->vertices[i-1].first_edge = new_edge;
// 将i加入到j的邻接表中
EdgeNode *new_edge2 = (EdgeNode*)malloc(sizeof(EdgeNode));
new_edge2->vertex = i;
new_edge2->next = graph->vertices[j-1].first_edge;
graph->vertices[j-1].first_edge = new_edge2;
}
```
希望这个长长的示例程序能够帮到你!
阅读全文