用C语言写出代码并给出输入实例及结果:已知有向图采用邻接表作为存储结构,设计算法求该图中每个顶点的出度和入度
时间: 2024-03-26 16:35:53 浏览: 78
以下是用C语言编写的代码,输入实例为一个有向图的邻接表表示:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct EdgeNode {
int adjvex;
struct EdgeNode *next;
} EdgeNode;
typedef struct VertexNode {
int data;
EdgeNode *firstedge;
} VertexNode;
VertexNode adjList[MAX_VERTICES];
int inDegree[MAX_VERTICES], outDegree[MAX_VERTICES];
void addEdge(int u, int v) {
EdgeNode *newNode = (EdgeNode *) malloc(sizeof(EdgeNode));
newNode->adjvex = v;
newNode->next = adjList[u].firstedge;
adjList[u].firstedge = newNode;
}
void computeDegree(int n) {
int i;
EdgeNode *p;
for (i = 0; i < n; i++) {
p = adjList[i].firstedge;
while (p != NULL) {
outDegree[i]++;
inDegree[p->adjvex]++;
p = p->next;
}
}
}
int main() {
int n, m, i, u, v;
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
adjList[i].data = i;
adjList[i].firstedge = NULL;
inDegree[i] = outDegree[i] = 0;
}
for (i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}
computeDegree(n);
printf("Vertex\tInDegree\tOutDegree\n");
for (i = 0; i < n; i++) {
printf("%d\t%d\t%d\n", i, inDegree[i], outDegree[i]);
}
return 0;
}
```
输入实例:第一行包含两个整数 $n$ 和 $m$,分别表示有向图的顶点数和边数。接下来 $m$ 行,每行两个整数 $u$ 和 $v$,表示有一条从 $u$ 到 $v$ 的有向边。
```
6 8
0 1
0 2
1 2
1 3
2 3
2 4
3 5
4 5
```
输出结果:
```
Vertex InDegree OutDegree
0 0 2
1 1 2
2 2 2
3 2 1
4 1 1
5 2 0
```
其中,第一列为顶点编号,第二列为入度,第三列为出度。
阅读全文