C语言实现7. 有向图G采用邻接表存储方式,编写代码求G中每个顶点的入度和出度。
时间: 2025-01-12 09:57:01 浏览: 8
好的,我来为您介绍如何使用C语言实现求有向图每个顶点的入度和出度。假设我们采用邻接表存储有向图,下面是实现代码:
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
// 定义邻接表节点结构
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *next; // 指向下一条弧的指针
} ArcNode;
// 定义顶点表节点结构
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 定义图结构
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的当前顶点数和弧数
} ALGraph;
// 初始化图
void InitGraph(ALGraph *G) {
G->vexnum = 0;
G->arcnum = 0;
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].firstarc = NULL;
}
}
// 插入顶点
void InsertVertex(ALGraph *G, int v) {
G->vertices[G->vexnum].data = v;
G->vertices[G->vexnum].firstarc = NULL;
G->vexnum++;
}
// 插入边
void InsertArc(ALGraph *G, int v1, int v2) {
// 从v1到v2的边
ArcNode *newNode = (ArcNode *)malloc(sizeof(ArcNode));
newNode->adjvex = v2;
newNode->next = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = newNode;
G->arcnum++;
}
// 计算入度和出度
void CalculateInOutDegree(ALGraph *G, int *inDegree, int *outDegree) {
// 初始化入度和出度数组
for (int i = 0; i < G->vexnum; i++) {
inDegree[i] = 0;
outDegree[i] = 0;
}
// 计算出度
for (int i = 0; i < G->vexnum; i++) {
ArcNode *p = G->vertices[i].firstarc;
while (p != NULL) {
outDegree[i]++;
p = p->next;
}
}
// 计算入度
for (int i = 0; i < G->vexnum; i++) {
ArcNode *p = G->vertices[i].firstarc;
while (p != NULL) {
inDegree[p->adjvex]++;
p = p->next;
}
}
}
// 打印入度和出度
void PrintInOutDegree(ALGraph *G, int *inDegree, int *outDegree) {
for (int i = 0; i < G->vexnum; i++) {
printf("顶点 %d: 入度 = %d, 出度 = %d\n", G->vertices[i].data, inDegree[i], outDegree[i]);
}
}
int main() {
ALGraph G;
InitGraph(&G);
// 插入顶点
for (int i = 0; i < 5; i++) {
InsertVertex(&G, i);
}
// 插入边
InsertArc(&G, 0, 1);
InsertArc(&G, 0, 2);
InsertArc(&G, 1, 2);
InsertArc(&G, 1, 3);
InsertArc(&G, 2, 3);
InsertArc(&G, 3, 4);
int inDegree[MAX_VERTEX_NUM];
int outDegree[MAX_VERTEX_NUM];
CalculateInOutDegree(&G, inDegree, outDegree);
PrintInOutDegree(&G, inDegree, outDegree);
return 0;
}
这段代码实现了以下功能:
- 定义了邻接表存储结构。
- 实现了图的初始化、插入顶点和插入边操作。
- 实现了计算入度和出度的函数。
- 实现了打印入度和出度的函数。
- 在main函数中,我们创建了一个图,插入了一些顶点和边,然后计算并打印了每个顶点的入度和出度。
运行这段代码,您将得到每个顶点的入度和出度结果。这种方法的时间复杂度为O(V+E),其中V是顶点数,E是边数,因为我们遍历了每个顶点和每条边。