用c语言定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、深度优先遍历、计算并输出图中每个顶点的度等基本操作。
时间: 2023-08-11 19:03:41 浏览: 107
好的,以下是用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 create_graph(Graph* G) {
int v1, v2;
printf("请输入顶点数:");
scanf("%d", &G->vertex_num);
printf("请输入边数:");
scanf("%d", &G->edge_num);
for (int i = 0; i < G->vertex_num; i++) {
printf("请输入第%d个顶点信息:", i + 1);
scanf("%d", &G->vertex[i]);
}
for (int i = 0; i < G->edge_num; i++) {
printf("请输入第%d条边的两个顶点:", i + 1);
scanf("%d%d", &v1, &v2);
add_edge(G, v1, v2);
}
}
// 输出图
void print_graph(Graph* G) {
printf("顶点:");
for (int i = 0; i < G->vertex_num; i++) {
printf("%d ", G->vertex[i]);
}
printf("\n边:\n");
for (int i = 0; i < G->vertex_num; i++) {
for (int j = 0; j < G->vertex_num; j++) {
printf("%d ", G->edge[i][j]);
}
printf("\n");
}
}
// 深度优先遍历
void dfs(Graph* G, int v, int* visited) {
visited[v] = 1;
printf("%d ", G->vertex[v]);
for (int i = 0; i < G->vertex_num; i++) {
if (G->edge[v][i] == 1 && visited[i] == 0) {
dfs(G, i, visited);
}
}
}
// 计算顶点的度
int get_degree(Graph* G, int v) {
int degree = 0;
for (int i = 0; i < G->vertex_num; i++) {
if (G->edge[v][i] == 1) {
degree++;
}
}
return degree;
}
// 输出每个顶点的度
void print_degree(Graph* G) {
printf("每个顶点的度:\n");
for (int i = 0; i < G->vertex_num; i++) {
printf("%d的度为%d\n", G->vertex[i], get_degree(G, i));
}
}
int main() {
Graph G;
init_graph(&G);
create_graph(&G);
print_graph(&G);
printf("深度优先遍历结果:");
int visited[MAX_VERTEX_NUM] = {0};
dfs(&G, 0, visited);
printf("\n");
print_degree(&G);
return 0;
}
```
以上代码实现了基本的图操作,你可以根据需要进行修改和扩展。
阅读全文