用C语言写一段代码,用邻接表存储,用拓扑排序检验有向无权图的连通性typedef struct ArcNode { int adjvex; // 邻接点的下标 struct ArcNode *nextarc; // 指向下一条边的指针 } ArcNode; // 顶点表结构体 typedef struct VNode { char data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附于该顶点的边的指针 } VNode, AdjList[MAX]; // 图结构体 typedef struct { AdjList vertices; // 邻接表 int vexnum, arcnum; // 顶点数和边数 } ALGraph; // 初始化有向图 void InitGraph(ALGraph *G) { int i; G->vexnum = G->arcnum = 0; for (i = 0; i < MAX; i++) { G->vertices[i].data = ' '; G->vertices[i].firstarc = NULL; } }
时间: 2024-01-08 22:01:50 浏览: 44
// 拓扑排序检验有向无权图的连通性
int TopologicalSort(ALGraph *G) {
int i, count = 0;
int indegree[MAX] = {0}; // 记录每个顶点的入度
ArcNode *p;
// 统计每个顶点的入度
for (i = 0; i < G->vexnum; i++) {
p = G->vertices[i].firstarc;
while (p) {
indegree[p->adjvex]++;
p = p->nextarc;
}
}
// 创建一个队列,用于存储入度为0的顶点
Queue Q;
InitQueue(&Q);
for (i = 0; i < G->vexnum; i++) {
if (indegree[i] == 0)
EnQueue(&Q, i);
}
// 对队列进行拓扑排序
while (!IsEmpty(&Q)) {
DeQueue(&Q, &i);
count++;
p = G->vertices[i].firstarc;
while (p) {
indegree[p->adjvex]--;
if (indegree[p->adjvex] == 0)
EnQueue(&Q, p->adjvex);
p = p->nextarc;
}
}
// 如果拓扑排序后顶点数不等于总顶点数,则说明图不连通
if (count != G->vexnum)
return 0;
else
return 1;
}