用c语言创建一个无向图,选用任一数据存储结构,并求出任意一个顶的度。同时写出图的深度,广度遍历算法
时间: 2024-02-18 11:59:04 浏览: 89
数据结构 图的深度、广度遍历
好的,我明白了。下面是对您的问题的回答:
用 C 语言创建一个无向图,可以选择邻接矩阵或邻接表作为数据存储结构。以邻接矩阵为例,代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 50 // 最大顶点数
typedef struct {
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertexNum; // 顶点数
int edgeNum; // 边数
} Graph;
// 初始化无向图
void init(Graph *graph, int vertexNum) {
graph->vertexNum = vertexNum;
graph->edgeNum = 0;
for (int i = 0; i < vertexNum; i++) {
for (int j = 0; j < vertexNum; j++) {
graph->matrix[i][j] = 0;
}
}
}
// 添加边
void addEdge(Graph *graph, int v1, int v2) {
graph->matrix[v1][v2] = 1;
graph->matrix[v2][v1] = 1;
graph->edgeNum++;
}
// 计算顶的度
int degree(Graph *graph, int v) {
int degree = 0;
for (int i = 0; i < graph->vertexNum; i++) {
degree += graph->matrix[v][i];
}
return degree;
}
// 深度优先遍历
void dfs(Graph *graph, int v, int *visited) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < graph->vertexNum; i++) {
if (graph->matrix[v][i] && !visited[i]) {
dfs(graph, i, visited);
}
}
}
// 广度优先遍历
void bfs(Graph *graph, int v, int *visited) {
int queue[MAX_VERTEX_NUM], head = 0, tail = 0;
visited[v] = 1;
queue[tail++] = v;
while (head < tail) {
int cur = queue[head++];
printf("%d ", cur);
for (int i = 0; i < graph->vertexNum; i++) {
if (graph->matrix[cur][i] && !visited[i]) {
visited[i] = 1;
queue[tail++] = i;
}
}
}
}
int main() {
Graph graph;
int visited[MAX_VERTEX_NUM] = {0};
init(&graph, 5);
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 2);
addEdge(&graph, 1, 2);
addEdge(&graph, 1, 3);
addEdge(&graph, 2, 4);
addEdge(&graph, 3, 4);
int v = 2;
printf("顶 %d 的度为 %d\n", v, degree(&graph, v));
printf("深度优先遍历:");
dfs(&graph, 0, visited);
printf("\n");
for (int i = 0; i < graph.vertexNum; i++) {
visited[i] = 0;
}
printf("广度优先遍历:");
bfs(&graph, 0, visited);
printf("\n");
return 0;
}
```
上述代码中,我们使用邻接矩阵作为数据存储结构,顶点编号从 0 开始。`init` 函数用于初始化无向图,`addEdge` 函数用于添加边,`degree` 函数用于计算某个顶的度。`dfs` 函数和 `bfs` 函数分别实现了深度优先遍历和广度优先遍历算法。在 `main` 函数中,我们创建了一个 5 个顶点的无向图,并输出了顶 2 的度以及深度优先遍历和广度优先遍历的结果。
希望能够帮到您!
阅读全文