首页 > 程序开发 > 软件开发 > 其他 > 正文
数据结构与算法之有向图的拓扑排序
2017-03-20       个评论    来源:耿国锋的博客  
收藏    我要投稿

数据结构与算法之有向图的拓扑排序:图的基础介绍和基础算法深度优先搜索,广度优先搜索在我前两篇博文中。当图的边有方向时,即有向图,这时图的搜索策略将发生变化。

一,有向性在数组中的表现为单向的,不像无向图的双向。

二,搜索规则

规则1:找到没有后继的顶点

规则2,在图中删除没有后继顶点的顶点

三,找到没有后继的顶点

有一种图此算法是无法处理的,比如环图,如图所示

在N个顶点的图中,如果没有环,边的个数小于等于n-1 。

找后继顶点的算法如下:只要找到数组一行中全是0的行号,即是没有后继的顶点,当找不到这种行号,图中必然存在环。

四,删除顶点

图中删除顶点操作反应在二维数组中是:将属于顶点的行和列删除,同时在顶点与脚标的对应的一维数组VtertexList[nvertex++] = new Vertex(v)中,将顶点删除。

二维数组行的删除:将被删除顶点所在行之下的所有行向上移一格,这样便覆盖了被删除顶点的行。

二维数组列的删除:将被删除顶点所在列之右的所有列向左移一格,这样便覆盖了被删除顶点的列。

一维对应数组的删除:将被删除顶点后面的顶点向前移一格。

五,根据规则设计算法:

点击复制链接 与好友分享!回本站首页
上一篇:MyBaitis与Hibernate的区别
下一篇:阻塞队列实现消费之生产模式
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站