已知某有向图(n个结点)的邻接表,求该图各结点的入度数。用C语言写代码
时间: 2024-04-16 16:24:16 浏览: 24
为了求解有向图中各节点的入度数,我们可以使用邻接表表示图的数据结构。遍历每个节点的邻接表,并统计指向该节点的边的数量,即为该节点的入度数。
以下是使用C语言编写的求解有向图各节点入度数的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接表的链表节点
struct Node {
int vertex;
struct Node* next;
};
// 图的结构体
struct Graph {
struct Node* adjLists[MAX_VERTICES];
};
// 创建新节点
struct Node* createNode(int v) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// 创建图
struct Graph* createGraph() {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
for (int i = 0; i < MAX_VERTICES; i++) {
graph->adjLists[i] = NULL;
}
return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
// 添加 src -> dest 边
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
// 计算节点的入度数
int calculateIndegree(struct Graph* graph, int vertex) {
int indegree = 0;
for (int i = 0; i < MAX_VERTICES; i++) {
struct Node* node = graph->adjLists[i];
while (node != NULL) {
if (node->vertex == vertex) {
indegree++;
}
node = node->next;
}
}
return indegree;
}
int main() {
struct Graph* graph = createGraph();
int numVertices, numEdges;
// 输入顶点数和边数
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);
printf("Enter the number of edges: ");
scanf("%d", &numEdges);
// 输入边信息
for (int i = 0; i < numEdges; i++) {
int src, dest;
printf("Enter edge %d (source destination): ", i + 1);
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
// 计算并打印各节点的入度数
printf("Indegree of each vertex:\n");
for (int i = 0; i < numVertices; i++) {
int indegree = calculateIndegree(graph, i);
printf("Vertex %d: %d\n", i, indegree);
}
return 0;
}
```
在上述代码中,我们首先定义了邻接表的链表节点结构 `Node` 和图的结构体 `Graph`。然后,我们实现了创建新节点、创建图、添加边和计算节点入度数的函数。在 `main` 函数中,我们先输入顶点数和边数,然后输入边的信息并使用邻接表表示图。接下来,我们调用 `calculateIndegree` 函数计算每个节点的入度数,并打印出结果。
注意:上述代码仅为示例,实际使用时需要根据实际情况进行修改。同时,为了简化示例,我们没有进行输入验证和错误处理,请在实际应用中进行适当的验证和错误处理。