c语言 邻接表图的出度算法
时间: 2023-09-28 15:10:58 浏览: 56
邻接表是一种表示图的数据结构,一般用于稀疏图。邻接表中的每个节点代表图中的一个顶点,每个节点中维护一个链表,这个链表存储与该节点对应的顶点相邻的顶点。邻接表中每个节点的链表称为该节点的邻接表。
邻接表表示的图的出度就是该节点的邻接表的长度。因为邻接表中存储的是该节点所连接的所有节点,所以邻接表的长度就代表了该节点的出度。
下面是一个简单的C语言实现邻接表图的出度算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct ArcNode { // 边表节点
int adjvex; // 邻接点域,存储该节点所连接的顶点在顶点数组中的下标
struct ArcNode* next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode { // 顶点表节点
int data; // 顶点信息
ArcNode* first; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 邻接表
AdjList vertices; // 顶点表数组
int vexnum, arcnum; // 图的当前顶点数和边数
} ALGraph;
// 计算出度
int outdegree(ALGraph G, int v) {
int count = 0;
ArcNode* p = G.vertices[v].first; // 指向v的第一个邻接点
while (p != NULL) {
count++;
p = p->next;
}
return count;
}
int main() {
// 创建图的代码省略
// ...
int v = 1; // 计算顶点1的出度
int out = outdegree(G, v);
printf("Vertex %d's outdegree is %d\n", v, out);
return 0;
}
```
在这个代码中,我们定义了邻接表的数据结构,包括一个 `VNode` 结构体表示顶点表节点,一个 `ArcNode` 结构体表示边表节点,以及一个 `ALGraph` 结构体表示邻接表。然后,我们实现了一个 `outdegree` 函数来计算给定顶点的出度。
`outdegree` 函数首先将计数器 `count` 初始化为0,然后遍历该顶点的邻接表,每遍历到一个节点就将计数器 `count` 加1。最后,函数返回计数器 `count` 的值,即为该顶点的出度。
在 `main` 函数中,我们创建了一个邻接表表示的图 `G`,然后调用 `outdegree` 函数来计算顶点1的出度,并输出结果。