有一个邻接表存储的图G,使用c语言分别设计实现以下要求的算法:求出图中每个顶点的出度;计算图中出度为0的顶点数。 完整代码
时间: 2024-03-05 15:52:23 浏览: 69
图的邻接表存储C语言实现
以下是使用C语言实现求出图中每个顶点的出度和计算出度为0的顶点数的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表结点定义
typedef struct AdjListNode {
int dest;
struct AdjListNode* next;
} AdjListNode;
// 邻接表定义
typedef struct AdjList {
struct AdjListNode* head;
} AdjList;
// 图结构体定义
typedef struct Graph {
int V; // 顶点数目
struct AdjList* array;
} Graph;
// 创建邻接表结点
AdjListNode* newAdjListNode(int dest) {
AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建图
Graph* createGraph(int V) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V;
graph->array = (AdjList*)malloc(V * sizeof(AdjList));
for (int i = 0; i < V; i++) {
graph->array[i].head = NULL;
}
return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
// 求出每个顶点的出度
void getOutDegree(Graph* graph, int outDegree[]) {
for (int i = 0; i < graph->V; i++) {
AdjListNode* node = graph->array[i].head;
int count = 0;
while (node != NULL) {
count++;
node = node->next;
}
outDegree[i] = count;
}
}
// 计算出度为0的顶点数
int countZeroOutDegree(Graph* graph) {
int count = 0;
for (int i = 0; i < graph->V; i++) {
AdjListNode* node = graph->array[i].head;
if (node == NULL) {
count++;
}
}
return count;
}
int main() {
int V, E;
printf("请输入顶点数和边数:");
scanf("%d %d", &V, &E);
Graph* graph = createGraph(V);
printf("请输入每条边的起点和终点:\n");
for (int i = 0; i < E; i++) {
int src, dest;
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
// 求出每个顶点的出度
int outDegree[V];
getOutDegree(graph, outDegree);
printf("每个顶点的出度为:\n");
for (int i = 0; i < V; i++) {
printf("顶点 %d 的出度为 %d\n", i, outDegree[i]);
}
// 计算出度为0的顶点数
int zeroOutDegree = countZeroOutDegree(graph);
printf("出度为0的顶点数为:%d\n", zeroOutDegree);
return 0;
}
```
在程序中,我们首先定义了邻接表结点的结构体 `AdjListNode` 和邻接表的结构体 `AdjList`,并定义了图的结构体 `Graph`,包括顶点数目 `V` 和邻接表数组 `array`。
接着,我们定义了创建邻接表结点的函数 `newAdjListNode` 和创建图的函数 `createGraph`,以及添加边的函数 `addEdge`。
然后,我们定义了求出每个顶点的出度的函数 `getOutDegree`,遍历每个顶点的邻接表,计算出度并存储在数组 `outDegree` 中。
最后,我们定义了计算出度为0的顶点数的函数 `countZeroOutDegree`,遍历每个顶点的邻接表,如果邻接表为空,则该顶点的出度为0,计数器加1。
在 `main` 函数中,我们先输入顶点数和边数,然后逐一输入每条边的起点和终点,创建图。接着,我们调用 `getOutDegree` 函数求出每个顶点的出度,并打印出度。最后,我们调用 `countZeroOutDegree` 函数计算出度为0的顶点数,并打印结果。
阅读全文