用c语言编写代码:以邻接矩阵作存储结构,编写程序对给定的无向图进行深度优先遍历,并在遍历的过程中计算图G的连通分量个数及边的数目。输入格式: 第一行输入图的顶点数和边数。 第二行输入顶点值。 接下来每行代表一条边,输入边依附的两个顶点。各边输入先后次序无要求。 输出格式: 输出分三行 :第一行: 深度优先遍历序列 ;第二行: 连通分量个数; 第三行 :边数
时间: 2024-03-23 16:44:06 浏览: 73
邻接表或者邻接矩阵为存储结构实现连通无向图的深度优先和广度优先遍历
3星 · 编辑精心推荐
好的,以下是用 C 语言编写的代码实现你要求的功能:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct Graph {
int vertex[MAX_VERTEX_NUM];
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int visited[MAX_VERTEX_NUM];
int vertex_num;
int edge_num;
} Graph;
void init_graph(Graph* graph) {
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
graph->vertex[i] = 0;
graph->visited[i] = 0;
for (int j = 0; j < MAX_VERTEX_NUM; j++) {
graph->edge[i][j] = 0;
}
}
graph->vertex_num = 0;
graph->edge_num = 0;
}
void add_edge(Graph* graph, int v1, int v2) {
graph->edge[v1][v2] = 1;
graph->edge[v2][v1] = 1;
graph->edge_num++;
}
void dfs(Graph* graph, int vertex) {
printf("%d ", vertex);
graph->visited[vertex] = 1;
for (int i = 0; i < graph->vertex_num; i++) {
if (graph->edge[vertex][i] == 1 && graph->visited[i] == 0) {
dfs(graph, i);
}
}
}
int main() {
Graph graph;
init_graph(&graph);
int vertex_num, edge_num;
scanf("%d %d", &vertex_num, &edge_num);
for (int i = 0; i < vertex_num; i++) {
scanf("%d", &graph.vertex[i]);
graph.vertex_num++;
}
for (int i = 0; i < edge_num; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
add_edge(&graph, v1, v2);
}
int connected_component = 0;
int edge_count = 0;
for (int i = 0; i < vertex_num; i++) {
if (graph.visited[i] == 0) {
dfs(&graph, i);
printf("\n");
connected_component++;
}
for (int j = i + 1; j < vertex_num; j++) {
if (graph.edge[i][j] == 1) {
edge_count++;
}
}
}
printf("%d\n", connected_component);
printf("%d\n", edge_count);
return 0;
}
```
代码中定义了一个 `Graph` 结构体来表示图,包括顶点数组、邻接矩阵、访问数组、顶点数和边数等信息。通过 `init_graph` 函数初始化图,通过 `add_edge` 函数添加边,通过 `dfs` 函数进行深度优先遍历,并在遍历过程中计算连通分量个数和边数。在 `main` 函数中,根据输入构建图,并对每个未访问的顶点进行深度优先遍历,最后输出遍历序列、连通分量个数和边数。
阅读全文