从零开始学数据结构系列之第四章《拓扑排序代码详解》

代码详解

我们的代码思路是这样的：

• 找到所有入度为 0 的顶点，并将其输出到拓扑序列中。
• 将这些顶点从图中删除，并将所有以该顶点为起点的边的终点的入度减 1 。
• 不断重复以上两个操作，直到所有的顶点都被输出到拓扑序列中或者图中不存在入度为 0 的顶点为止。

我们拿这张图来进行代码详解

图的入度

步骤详解

首先我们得栈是先进后出，后进先出

​ 第一次我们入栈是 0 ，6，但是出栈的时候是6 先出栈 然后 0 再出栈

6 出栈时候 ，要把它有关联的弧都要去掉，图变成下面这样

此时图的入度表更新为

之后再次检查入度表是否有新的变成 0 ，发现没有之后继续出栈，这次出栈的是1

此时图的入度表更新为

之后再次检查入度表是否有新的变成 0 ，发现3,4 以及没有入度了，将3 4 进行入栈，之后再将4进行出栈

此时图的入度表更新为

之后再次检查入度表是否有新的变成 0 ，发现无，之后再将3进行出栈

此时图的入度表更新为

之后再次检查入度表是否有新的变成 0 ，发现2，5的入度都变成0了，之后再将5，2进行出栈，此时，排序完成

总代码

#include <stdio.h>
#include <stdlib.h>typedef struct Graph 
{char* vexs;int** arcs;int vexNum;int arcNum;
}Graph;typedef struct Node 
{int data;struct Node* next;
}Node;Node* initStack() 
{Node* stack = (Node*)malloc(sizeof(Node));stack -> data = 0;stack -> next = NULL;return stack;
}int isEmpty(Node* stack) 
{if (stack -> next == NULL) {return 1;}else {return 0;}
}void push(Node* stack, int data) 
{Node* node = (Node*)malloc(sizeof(Node));node -> data = data;node -> next = stack -> next;stack -> next = node;stack -> data ++;
}int pop(Node* stack) 
{if (!isEmpty(stack)) {Node* node = stack -> next;stack -> next = node -> next;return node -> data;}else {return -1;}
}
/* 寻找入度 */
int* findInDegrees(Graph* G) 
{int i=0,j=0;int *inDegrees = (int*)malloc(sizeof(int) * G->vexNum);for(i=0;i<G->vexNum;i++)inDegrees[i] = 0;for(i=0;i<G->vexNum;i++)for(j=0;j<G->vexNum;j++)if(G->arcs[i][j])inDegrees[j]+=1;return  inDegrees;
}/* 入栈且拓扑 */
void topologicalSort(Graph* G) 
{int i=0;int value=0;int *inDegrees = findInDegrees(G);Node *stack = initStack();for (i = 0 ; i < G -> vexNum; i++) if (inDegrees[i] == 0) push(stack, i);while(!isEmpty(stack)){value = pop(stack);printf("%c  ",G->vexs[value]);for(i=0;i<G->vexNum;i++)if(G->arcs[value][i]){inDegrees[i]-=1;if (inDegrees[i] == 0) push(stack, i);}	}printf("\r\n");
}Graph* initGraph(int vexNum) 
{int i=0;Graph* G = (Graph*)malloc(sizeof(Graph));G -> vexs = (char*)malloc(sizeof(char) * vexNum);G -> arcs = (int**)malloc(sizeof(int*) * vexNum);for (i = 0 ; i < vexNum; i++) {G -> arcs[i] = (int*)malloc(sizeof(int) * vexNum);}G -> vexNum = vexNum;G -> arcNum = 0;return G;
}void createGraph(Graph* G, char* vexs, int* arcs) 
{int i=0,j=0;for (i = 0 ; i < G -> vexNum; i++) {G -> vexs[i] = vexs[i];for (j = 0; j < G -> vexNum; j++) {G -> arcs[i][j] = *(arcs + i * G -> vexNum + j);if (G -> arcs[i][j] != 0)G -> arcNum ++;}}G -> arcNum /= 2;
}void DFS(Graph* G, int* visited, int index) 
{int i=0;printf("%c\t", G -> vexs[index]);visited[index] = 1;for (i = 0; i < G ->vexNum; i++) {if (G -> arcs[index][i] == 1 && !visited[i]) {DFS(G, visited, i);}}
}int main() 
{int i=0;Graph* G = initGraph(6);int* visited = (int*)malloc(sizeof(int) * G -> vexNum);int arcs[6][6] = {0,1,1,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0};for (i = 0; i < G -> vexNum; i++)visited[i] = 0;  createGraph(G, "123456", (int*)arcs);DFS(G, visited, 0);printf("\n");topologicalSort(G);return 0;
}

☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法（普里姆算法）详解》
46【第四章】《prim算法（普里姆算法）详解2》
47【第四章】《prim算法（普里姆算法）详解3》
48【第四章】《prim算法（普里姆算法）讲解汇总》
49【第四章】《prim算法（普里姆算法）代码讲解》
50【第四章】《prim算法（普里姆算法）总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》
54【第四章】《克鲁斯卡尔算法应用场景-公交站问题》
55【第四章】《克鲁斯卡尔算法判断回路问题》
56【第四章】《克鲁斯卡尔算法步骤回顾》
57【第四章】《克鲁斯卡尔算法代码初始化详解》
58【第四章】《克鲁斯卡尔算法总代码详解》
59【第四章】《了解最短路径》
60【第四章】《迪杰斯特拉算法了解》
61【第四章】《Dijkstra 迪杰斯特拉算法图解》
62【第四章】《Dijkstra 迪杰斯特拉算法总代码》
63【第四章】《弗洛伊德(floyd)算法简介》
64【第四章】《弗洛伊德算法详解》
65【第四章】《弗洛伊德代码详解》
66【第四章】《拓扑排序之AOV网》
67【第四章】《拓扑排序代码详解》