c语言输出 在邻接表存储结构下求图G中每个顶点的入度
时间: 2023-08-05 18:03:33 浏览: 55
好的,以下是C语言的实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表存储的图结构
typedef struct EdgeNode {
int adjvex; // 邻接点下标
struct EdgeNode* next; // 指向下一个邻接点的指针
} EdgeNode;
typedef struct VertexNode {
int data; // 顶点信息
EdgeNode* firstedge; // 指向第一个邻接点的指针
} VertexNode;
typedef struct {
VertexNode* adjList; // 顶点数组
int numVertexes, numEdges; // 顶点数和边数
} Graph;
// 添加一条边
void addEdge(Graph* G, int u, int v) {
// 创建一个邻接点节点
EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = v;
e->next = NULL;
// 将邻接点节点插入到邻接表中
if (G->adjList[u].firstedge == NULL) {
G->adjList[u].firstedge = e;
} else {
EdgeNode* p = G->adjList[u].firstedge;
while (p->next != NULL) {
p = p->next;
}
p->next = e;
}
}
// 求每个顶点的入度
int* getIndegree(Graph* G) {
int* indegree = (int*)malloc(G->numVertexes * sizeof(int)); // 动态分配空间,存储每个顶点的入度
// 初始化每个顶点的入度为0
for (int i = 0; i < G->numVertexes; i++) {
indegree[i] = 0;
}
// 遍历每个顶点的邻接表,对于邻接表中的每个节点,将对应的顶点的入度加1
for (int u = 0; u < G->numVertexes; u++) {
EdgeNode* p = G->adjList[u].firstedge;
while (p != NULL) {
int v = p->adjvex;
indegree[v]++;
p = p->next;
}
}
return indegree;
}
int main() {
// 创建一个有向图
Graph G;
G.numVertexes = 5;
G.numEdges = 5;
G.adjList = (VertexNode*)malloc(G.numVertexes * sizeof(VertexNode));
for (int i = 0; i < G.numVertexes; i++) {
G.adjList[i].data = i;
G.adjList[i].firstedge = NULL;
}
addEdge(&G, 0, 1);
addEdge(&G, 0, 2);
addEdge(&G, 1, 2);
addEdge(&G, 2, 3);
addEdge(&G, 3, 4);
int* indegree = getIndegree(&G);
// 输出每个顶点的入度
for (int u = 0; u < G.numVertexes; u++) {
printf("Vertex %d indegree: %d\n", u, indegree[u]);
}
free(indegree);
for (int i = 0; i < G.numVertexes; i++) {
EdgeNode* p = G.adjList[i].firstedge;
while (p != NULL) {
EdgeNode* q = p;
p = p->next;
free(q);
}
}
free(G.adjList);
return 0;
}
```
输出结果与前面的C++实现代码相同:
```
Vertex 0 indegree: 0
Vertex 1 indegree: 1
Vertex 2 indegree: 2
Vertex 3 indegree: 1
Vertex 4 indegree: 1
```