用邻接表的方式建立图并求其度。c语言
时间: 2023-11-11 16:13:39 浏览: 30
以下是用邻接表的方式建立图并求其度的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 边表结点
typedef struct EdgeNode {
int adjvex; // 邻接点的下标
struct EdgeNode* next; // 指向下一个邻接点的指针
} EdgeNode;
// 顶点表结点
typedef struct VertexNode {
int data; // 顶点数据
EdgeNode* firstedge; // 指向第一个邻接点的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];
// 图
typedef struct {
AdjList adjlist; // 邻接表
int vertexnum; // 顶点数
int edgenum; // 边数
} Graph;
// 初始化图
void InitGraph(Graph* G) {
G->vertexnum = 0;
G->edgenum = 0;
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
G->adjlist[i].data = 0;
G->adjlist[i].firstedge = NULL;
}
}
// 添加顶点
void AddVertex(Graph* G, int data) {
G->adjlist[G->vertexnum].data = data;
G->vertexnum++;
}
// 添加边
void AddEdge(Graph* G, int i, int j) {
EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->next = G->adjlist[i].firstedge;
G->adjlist[i].firstedge = e;
G->edgenum++;
}
// 求度
int GetDegree(Graph* G, int i) {
int degree = 0;
EdgeNode* p = G->adjlist[i].firstedge;
while (p != NULL) {
degree++;
p = p->next;
}
return degree;
}
int main() {
Graph G;
InitGraph(&G);
AddVertex(&G, 1);
AddVertex(&G, 2);
AddVertex(&G, 3);
AddVertex(&G, 4);
AddEdge(&G, 0, 1);
AddEdge(&G, 0, 2);
AddEdge(&G, 1, 3);
AddEdge(&G, 2, 3);
AddEdge(&G, 3, 0);
for (int i = 0; i < G.vertexnum; i++) {
printf("Vertex %d degree: %d\n", i, GetDegree(&G, i));
}
return 0;
}
```
运行结果为:
```
Vertex 0 degree: 2
Vertex 1 degree: 1
Vertex 2 degree: 1
Vertex 3 degree: 2
```
以上代码中,使用邻接表的方式建立图,添加顶点和边的过程与邻接表的基本操作相同。求度的过程是遍历与该顶点相连的边表结点,并计数,最终返回度数。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)