任意给定一个有向图,设计一个算法,对它进行拓扑排序c语言
时间: 2024-01-16 15:02:01 浏览: 28
以下是拓扑排序的C语言实现,假设给定的有向图存储在一个邻接表中:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的位置
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VertexNode {
int data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VertexNode;
typedef struct {
VertexNode vertices[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
int indegree[MAX_VERTEX_NUM]; // 每个顶点的入度
} Graph;
// 初始化有向图
void InitGraph(Graph *G, int vexnum, int arcnum)
{
G->vexnum = vexnum;
G->arcnum = arcnum;
for (int i = 0; i < vexnum; i++) {
G->vertices[i].data = i; // 顶点数据
G->vertices[i].firstarc = NULL; // 邻接表为空
G->indegree[i] = 0; // 入度为0
}
}
// 添加一条边
void AddArc(Graph *G, int tail, int head)
{
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode)); // 创建邻接点
p->adjvex = head;
p->nextarc = G->vertices[tail].firstarc; // 将邻接点插入到邻接表头部
G->vertices[tail].firstarc = p;
G->indegree[head]++; // 更新入度
}
// 拓扑排序
void TopologicalSort(Graph *G)
{
int count = 0; // 计数器,记录已经输出的顶点数
int stack[MAX_VERTEX_NUM]; // 栈,存储入度为0的顶点
int top = -1; // 栈顶指针
// 将所有入度为0的顶点入栈
for (int i = 0; i < G->vexnum; i++) {
if (G->indegree[i] == 0) {
stack[++top] = i;
}
}
while (top != -1) {
int v = stack[top--]; // 出栈
printf("%d ", G->vertices[v].data); // 输出顶点
count++;
// 遍历v的所有邻接点
for (ArcNode *p = G->vertices[v].firstarc; p != NULL; p = p->nextarc) {
int w = p->adjvex;
if (--G->indegree[w] == 0) { // 如果入度为0,入栈
stack[++top] = w;
}
}
}
if (count != G->vexnum) { // 如果输出的顶点数不等于总顶点数,说明存在环路
printf("Error: Graph has a cycle!\n");
}
}
int main()
{
Graph G;
int vexnum = 6;
int arcnum = 8;
InitGraph(&G, vexnum, arcnum);
AddArc(&G, 0, 1);
AddArc(&G, 0, 2);
AddArc(&G, 1, 3);
AddArc(&G, 1, 4);
AddArc(&G, 2, 4);
AddArc(&G, 3, 5);
AddArc(&G, 4, 3);
AddArc(&G, 4, 5);
TopologicalSort(&G);
return 0;
}
```
上述代码中的有向图是这样的:
```
0 -> 1 -> 3 -> 5
| |
v v
2 -> 4
```
其拓扑排序结果为:0 1 2 3 4 5。
相关推荐
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)