概念
设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.从一个顶点能访问其他所有的顶点