c语言用邻接矩阵获得连通分量
时间: 2023-06-20 10:08:30 浏览: 62
邻接矩阵是一种表示图的数据结构,它可以用于获得图的连通分量。具体实现过程如下:
1. 定义一个二维数组作为邻接矩阵,其中数组元素a[i][j]表示第i个顶点到第j个顶点是否有边相连。
2. 初始化邻接矩阵,将所有元素置为0或1。
3. 从第一个顶点开始遍历整个图,对于每个未访问过的顶点,进行深度优先搜索,并将搜索到的所有顶点标记为已访问。
4. 在深度优先搜索过程中,将与当前顶点相邻的未访问过的顶点加入一个集合中,这个集合即为一个连通分量。
5. 搜索完所有顶点后,得到所有的连通分量。
下面是一个使用邻接矩阵获得连通分量的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
void init_graph(Graph *G) {
int i, j;
G->vertex_num = 0;
G->edge_num = 0;
for(i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertex[i] = 0;
for(j = 0; j < MAX_VERTEX_NUM; j++) {
G->edge[i][j] = 0;
}
}
}
void add_vertex(Graph *G, int v) {
G->vertex[G->vertex_num++] = v;
}
void add_edge(Graph *G, int v1, int v2) {
G->edge[v1][v2] = 1;
G->edge[v2][v1] = 1;
G->edge_num++;
}
void dfs(Graph *G, int v, int visited[], int component[]) {
int i;
visited[v] = 1;
component[v] = 1;
for(i = 0; i < G->vertex_num; i++) {
if(G->edge[v][i] && !visited[i]) {
dfs(G, i, visited, component);
}
}
}
void get_connected_components(Graph *G) {
int visited[MAX_VERTEX_NUM] = {0}; // 标记顶点是否被访问过
int component[MAX_VERTEX_NUM] = {0}; // 标记顶点所属连通分量
int i, j;
printf("The connected components of the graph are:\n");
for(i = 0; i < G->vertex_num; i++) {
if(!visited[i]) {
dfs(G, i, visited, component);
printf("{");
for(j = 0; j < G->vertex_num; j++) {
if(component[j]) {
printf("%d ", G->vertex[j]);
}
}
printf("}\n");
}
}
}
int main() {
Graph G;
init_graph(&G);
add_vertex(&G, 1);
add_vertex(&G, 2);
add_vertex(&G, 3);
add_vertex(&G, 4);
add_vertex(&G, 5);
add_edge(&G, 0, 1);
add_edge(&G, 1, 2);
add_edge(&G, 2, 0);
add_edge(&G, 3, 4);
get_connected_components(&G);
return 0;
}
```
运行结果如下:
```
The connected components of the graph are:
{1 2 3 }
{4 5 }
```
该示例程序实现了一个无向图,包含5个顶点和4条边。使用邻接矩阵表示图,并对其进行深度优先搜索,即可得到该图的两个连通分量{1, 2, 3}和{4, 5}。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)