首页 > 编程知识 正文

图 拓扑排序(数据结构导论pdf百度云)

时间:2023-05-06 15:44:14 阅读:65414 作者:2056

概念

设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 .可以从一个顶点访问所有其他顶点

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。