数据结构复习—图

图我觉的是数据结构中的最高境界了,其实想想,链表是图,所以栈,队列,字符串 都可以理解为图;树是图,所以各种树,森林,堆等数据结构都可以理解为图。。。。生活中的各种物品,事情,关系,工程项目中的工作,计划,代码 非常非常多的东西都能理解为图,所以可以看到图这种数据结构是多么的普遍而具有通用性。

图的一般定义是个有序二元组(V,E),其中V称为顶集(Vertices Set),E称为边集(Edges set)。当然点集合和边集合又可以根据不同的场景有不同的定义和使用方法,这篇帖子对应用方面介绍比较少,重点还是对于知识点的复习。那么我们通过一幅图来说明问题,描述图方面的知识点,其实还有拓扑,最大流最小割的知识,过一段时间再做更新。

图

关于图的基本操作,要讲解的点比较少,这里说一个我以前经常犯的错误,图和常见的树不一样,相反他更像森林,所以在遍历的时候,DFS的顶层调用是要遍历所有点的(!visited的点)

那么重点要将的是最小生成树最短路径相关的五个算法:
Prime,Kruskal, Dijkstra, Folyd, SFPA

这一部分的代码是:图代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.