设有向图G的十字链表已建立,用C语言函数形式写出求图中各顶点度的算法并打印出来:COUNT_D(G[n],D[n]),G[n]为顶点表,D[n]为存放各顶点度的数组,n为图中顶点的个数。
时间: 2024-04-16 20:26:35 浏览: 60
以下是一个用 C 语言编写的求图中各顶点度的算法,并打印出来的函数形式:
```c
#include <stdio.h>
#include <stdlib.h>
// 边节点
typedef struct EdgeNode {
int tailVertex; // 尾顶点
struct EdgeNode* nextTail; // 下一个尾节点
int headVertex; // 头顶点
struct EdgeNode* nextHead; // 下一个头节点
} EdgeNode;
// 顶点节点
typedef struct VertexNode {
int vertex; // 顶点
EdgeNode* firstIn; // 第一个入边
EdgeNode* firstOut; // 第一个出边
} VertexNode;
// 图
typedef struct Graph {
VertexNode* vertices; // 顶点表
int numVertices; // 顶点个数
} Graph;
// 初始化图
Graph* initGraph(int numVertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->vertices = (VertexNode*)malloc(numVertices * sizeof(VertexNode));
for (int i = 0; i < numVertices; ++i) {
graph->vertices[i].vertex = i;
graph->vertices[i].firstIn = NULL;
graph->vertices[i].firstOut = NULL;
}
graph->numVertices = numVertices;
return graph;
}
// 添加边
void addEdge(Graph* graph, int tailVertex, int headVertex) {
EdgeNode* newEdge = (EdgeNode*)malloc(sizeof(EdgeNode));
newEdge->tailVertex = tailVertex;
newEdge->headVertex = headVertex;
newEdge->nextTail = graph->vertices[tailVertex].firstOut;
graph->vertices[tailVertex].firstOut = newEdge;
newEdge->nextHead = graph->vertices[headVertex].firstIn;
graph->vertices[headVertex].firstIn = newEdge;
}
// 求图中各顶点度
void countDegrees(Graph* graph, int* degrees) {
for (int i = 0; i < graph->numVertices; ++i) {
degrees[i] = 0;
EdgeNode* curEdge = graph->vertices[i].firstOut;
while (curEdge) {
degrees[i]++;
curEdge = curEdge->nextTail;
}
curEdge = graph->vertices[i].firstIn;
while (curEdge) {
degrees[i]++;
curEdge = curEdge->nextHead;
}
}
}
// 打印图中各顶点度
void printDegrees(int* degrees, int numVertices) {
for (int i = 0; i < numVertices; ++i) {
printf("顶点 %d 的度为:%d\n", i, degrees[i]);
}
}
int main() {
int numVertices = 5; // 图的顶点数
Graph* graph = initGraph(numVertices);
// 添加边
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
int* degrees = (int*)malloc(numVertices * sizeof(int));
countDegrees(graph, degrees);
printDegrees(degrees, numVertices);
return 0;
}
```
在这个示例中,我们使用十字链表表示有向图,创建了一个有5个顶点的图,并添加了一些边。然后,我们使用函数 `countDegrees` 来计算图中各顶点的度,并使用函数 `printDegrees` 打印出来。
希望这个算法对你有所帮助!如有任何疑问,请随时提问。
阅读全文