拓扑排序(Topological sorting)是对于有向无圈图顶点的一种排序
说明
- 它如果存在一条从vi到vj的路径，那么在排序中vj出现在vi的后面
- 如果图中含有圈，那么拓扑排序是不可能的
算法
- 先找出任意一个没有入边的顶点
- 显示该顶点，并将它和它的边一起从图中删除
- 重复上述操作1、2
过程详解
声明结构体
创建邻接表 //create_example_lgraph
step1 用一维数组_vexs存储顶点信息，用二维数组edges存储关联顶点信息
step2 用malloc函数分配指定字节大小的空间，将地址赋给pG、pG->vexs
step3 写入_vexs中的信息
step4 写入edges中的信息
以i=0时为例
a）创建VNode类型的对象，用进行赋值
b）将赋值好的对象，连接在对应的位置
最终得到邻接表:
step5 返回地址 pG
拓扑排序 //topological_sorting()
step1 创建ins(入度数组)、queue(辅助队列)、tops(拓扑排序结果数组)
step2 入度数组赋值
以i=0为例:
一开始，ins被memset函数初始化为零
声明ENode类型的指针node，并令其指向pG->vexs[0].first_edge
我们不妨将其单独拿出来讨论：
将node依次指向这条链上的所有结点、并将结点上ivex的值提取，在对应的ins数组上入度+1
i=0,完成后，得到如下的ins:
循环结束后，最终得到的ins：
step3 将入度为零的顶点对应的序号，放入队中queue
step4 将入度为零的顶点，写入tops，并将相应的顶点入度减一
将入度为零的顶点写入tops
用node指向对应的顶点所在的链
用node一次指向链上的所有结点、并提取链上结点的ivex值，在ins的对应位置减1
step5 重复3、4直到没有顶点可以被写入tops
最终得到:
