用c语言创建一个无向图,选用任一数据存储结构,并求出任意一个项的度
时间: 2024-02-18 21:59:39 浏览: 76
好的,我可以为您解答这个问题。
在C语言中,我们可以使用邻接矩阵或邻接表来表示无向图。其中,邻接矩阵是一个二维数组,每个元素表示两个顶点之间是否有边相连;邻接表则是由链表组成的数组,每个数组元素表示一个顶点,链表中存储该顶点所连向的其他顶点。
以下是使用邻接矩阵实现无向图的示例代码:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100 // 最大顶点个数
typedef struct {
int vexs[MAX_VERTEX_NUM]; // 存储顶点的数组
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的邻接矩阵
int vex_num, arc_num; // 顶点个数和边个数
} Graph;
void init(Graph* G, int vex_num) {
// 初始化图
G->vex_num = vex_num;
G->arc_num = 0;
for (int i = 0; i < vex_num; i++) {
G->vexs[i] = i; // 顶点的编号从0开始
for (int j = 0; j < vex_num; j++) {
G->arcs[i][j] = 0; // 初始化邻接矩阵
}
}
}
void add_edge(Graph* G, int u, int v) {
// 添加边
G->arcs[u][v] = 1;
G->arcs[v][u] = 1;
G->arc_num++;
}
int degree(Graph* G, int v) {
// 计算顶点v的度
int degree = 0;
for (int i = 0; i < G->vex_num; i++) {
if (G->arcs[v][i] == 1) {
degree++;
}
}
return degree;
}
int main() {
Graph G;
init(&G, 5);
add_edge(&G, 0, 1);
add_edge(&G, 0, 2);
add_edge(&G, 0, 3);
add_edge(&G, 1, 4);
printf("顶点1的度为:%d\n", degree(&G, 1));
return 0;
}
```
在上面的代码中,我们定义了一个`Graph`结构体来存储无向图,其中包含了顶点数组和邻接矩阵。我们通过`init`函数初始化图,通过`add_edge`函数向图中添加边,通过`degree`函数计算指定顶点的度。
在`main`函数中,我们创建了一个包含5个顶点的无向图,并向其中添加了4条边。最后,我们调用`degree`函数计算顶点1的度,并将结果输出到控制台中。
如果您想使用邻接表来实现无向图,可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ArcNode {
int adjvex; // 该边所连向的顶点编号
struct ArcNode* next; // 指向下一条边的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点的数据
ArcNode* first; // 指向第一条边的指针
} VNode;
typedef struct {
VNode vexs[MAX_VERTEX_NUM]; // 存储顶点的数组
int vex_num, arc_num; // 顶点个数和边个数
} Graph;
void init(Graph* G, int vex_num) {
// 初始化图
G->vex_num = vex_num;
G->arc_num = 0;
for (int i = 0; i < vex_num; i++) {
G->vexs[i].data = i; // 顶点的编号从0开始
G->vexs[i].first = NULL; // 初始化指向第一条边的指针
}
}
void add_edge(Graph* G, int u, int v) {
// 添加边
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v;
p->next = G->vexs[u].first;
G->vexs[u].first = p;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = u;
p->next = G->vexs[v].first;
G->vexs[v].first = p;
G->arc_num++;
}
int degree(Graph* G, int v) {
// 计算顶点v的度
int degree = 0;
ArcNode* p = G->vexs[v].first;
while (p != NULL) {
degree++;
p = p->next;
}
return degree;
}
int main() {
Graph G;
init(&G, 5);
add_edge(&G, 0, 1);
add_edge(&G, 0, 2);
add_edge(&G, 0, 3);
add_edge(&G, 1, 4);
printf("顶点1的度为:%d\n", degree(&G, 1));
return 0;
}
```
在这个示例中,我们定义了`ArcNode`和`VNode`两个结构体来分别表示边和顶点,使用链表的方式来存储每个顶点所连向的其他顶点。我们通过`init`函数初始化图,通过`add_edge`函数向图中添加边,通过`degree`函数计算指定顶点的度。
在`main`函数中,我们创建了一个包含5个顶点的无向图,并向其中添加了4条边。最后,我们调用`degree`函数计算顶点1的度,并将结果输出到控制台中。
希望我的回答能够帮到您,如果您有任何疑问,请随时向我提出。
阅读全文