c语言设有向图G的十字链表已建立,用C语言函数形式写出求图中各顶点度的算法:COUNT_D(G[n],D[n]),G[n]为顶点表,D[n]为存放各顶点度的数组,n为图中顶点的个数。
时间: 2024-04-16 22:26:20 浏览: 60
C语言版是十字链表
以下是求图中各顶点度的算法的C语函数形式:
```c
void COUNT_D(VertexNode G[], int D[], int n) {
// 初始化各顶点的度为0
for (int i = 0; i < n; i++) {
D[i] = 0;
}
// 遍历图中的所有边,计算顶点度
for (int i = 0; i < n; i++) {
ArcNode* arc = G[i].firstOut; // 获取顶点i的第一条出边
while (arc != NULL) {
D[i]++; // 顶点i的出度加1
int j = arc->adjvex; // 获取顶点i指向的顶点j的编号
D[j]++; // 顶点j的入度加1
arc = arc->nextOut; // 继续遍历顶点i的下一条出边
}
}
}
```
这个算法首先将各顶点的度初始化为0,然后遍历图中的所有边,对于每条边,分别更新起点和终点的度。最终得到的结果存放在数组D中,D[i]表示顶点i的度。
注意:这个算法基于十字链表表示法,假设图中每个顶点都有一个对应的VertexNode结构体,其中包含了一个指向第一条出边的指针firstOut。同时,每个顶点的出边也使用ArcNode结构体进行表示,其中包含了一个指向终点顶点的编号adjvex以及一个指向下一条出边的指针nextOut。请根据具体的图的表示方式进行相应的调整。
阅读全文