用C语言写一段代码,用邻接表存储,用拓扑排序检验有向无权图的连通性
时间: 2024-01-24 16:17:45 浏览: 28
以下是用邻接表存储的有向无权图拓扑排序检验连通性的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 邻接表中的边结构体
typedef struct EdgeNode {
int adjvex; // 邻接点在顶点数组中的下标
struct EdgeNode *next; // 指向下一条边的指针
} EdgeNode;
// 邻接表中的顶点结构体
typedef struct VertexNode {
int data; // 顶点的数据
EdgeNode *firstedge; // 指向第一条边的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];
// 邻接表结构体
typedef struct Graph {
AdjList adjList; // 邻接表
int vexnum, arcnum; // 顶点数、边数
} Graph;
// 初始化有向图
void InitGraph(Graph *G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->adjList[i].data = 0;
G->adjList[i].firstedge = NULL;
}
}
// 获取顶点在邻接表中的下标
int GetVertexPos(Graph *G, int data) {
int i;
for (i = 0; i < G->vexnum; i++) {
if (G->adjList[i].data == data) {
return i;
}
}
return -1;
}
// 添加有向边
void AddDirectedEdge(Graph *G, int data1, int data2) {
int i, j;
i = GetVertexPos(G, data1);
j = GetVertexPos(G, data2);
EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->next = G->adjList[i].firstedge;
G->adjList[i].firstedge = e;
G->arcnum++;
}
// 拓扑排序检验连通性
int TopoSort(Graph *G) {
int i, k, count = 0;
int inDegree[MAX_VERTEX_NUM] = {0}; // 记录每个顶点的入度
EdgeNode *e;
// 统计每个顶点的入度
for (i = 0; i < G->vexnum; i++) {
e = G->adjList[i].firstedge;
while (e != NULL) {
inDegree[e->adjvex]++;
e = e->next;
}
}
// 将入度为0的顶点加入队列
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
for (i = 0; i < G->vexnum; i++) {
if (inDegree[i] == 0) {
queue[rear++] = i;
}
}
// 依次弹出队列中的顶点,将其邻接点的入度减1,若减为0,则加入队列
while (front != rear) {
k = queue[front++];
count++;
e = G->adjList[k].firstedge;
while (e != NULL) {
if (--inDegree[e->adjvex] == 0) {
queue[rear++] = e->adjvex;
}
e = e->next;
}
}
// 若所有顶点都在队列中出现过,则表示图连通
if (count == G->vexnum) {
return 1;
} else {
return 0;
}
}
int main() {
Graph G;
int i, data1, data2;
printf("请输入顶点数和边数(空格分隔):");
scanf("%d %d", &G.vexnum, &G.arcnum);
printf("请输入顶点数据:");
for (i = 0; i < G.vexnum; i++) {
scanf("%d", &G.adjList[i].data);
}
printf("请输入边的起点和终点(空格分隔):\n");
for (i = 0; i < G.arcnum; i++) {
scanf("%d %d", &data1, &data2);
AddDirectedEdge(&G, data1, data2);
}
if (TopoSort(&G)) {
printf("该图连通。\n");
} else {
printf("该图不连通。\n");
}
return 0;
}
```
该代码首先定义了邻接表中的边结构体和顶点结构体,以及邻接表结构体。然后定义了初始化有向图、获取顶点在邻接表中的下标、添加有向边、拓扑排序检验连通性等函数。在主函数中,先从用户输入中读取顶点数和边数,然后读取顶点数据和边的起点和终点,最后调用拓扑排序检验连通性函数。