概念
设g=(v,e )为具有n个顶点的有向图,v中顶点的序列v1、v2、…、vn称为拓扑序列,有向图g中有从顶点vi到vj的路径时,在拓扑序列中顶点vi排列在顶点vj之前,有向
步骤
1 .从图中选择一个入度为0的顶点,输出该顶点。
2 .从图中删除此顶点及相关弧,并调整已删除弧头的节点入口。
3 .重复步骤1和步骤2,直到输出所有入度为0的顶点,拓扑排序完成,或者图中没有入度为0的顶点。
图中拓扑排序的顺序是C1、C2、C5、C4、C3
总结
1 .首先查找进入度为0的节点,而不是默认从V0或1出发
2 .无环有向图的任何一个,其所有顶点都可以排列成一个拓扑序列
3 .可以从一个顶点访问所有其他顶点