图跟树一样,也是非线性结构,咋看起来有点复杂,其实它很简单。树具有层次关系,上层元素可以与下一个多个元素连接,但是只能和上层的一个元素连接。在图结构中,节点间的连接是任意的,任何一个元素都可以与其他元素连接。
图相对而言很简单,我们只介绍的图的遍历和最小生成树,现在我们开始。
遍历
1.概念
从图中某一个顶点出发,访问图中的每一个结点,并要求只能访问一次,不能重复访问。
2.方法
(1)广度优先遍历
基本思想:首先访问顶点,再访问顶点的全部未访问的邻结点,再访问邻结点的所有结点即可(类似树的层次遍历)。
广度优先遍历:V1,V2,V3,V4,V5,V6或V1,V4,V3,V2,V6,V5
(2)深度优先遍历
基本思想:首先访问顶点,再访问顶点的每个邻结点,从该点继续深度优先遍历(类似于树的前序遍历)
深度优先遍历:V1,V2,V5,V3,V6,V4或V1,V4,V6,V3,V5,V2
总结,图的广度优先遍历和深度优先遍历的结果并不唯一。
最小生成树
(1)普里姆(Prim)算法
基本思想:选一个顶点开始,查找与顶点相邻且代价(边值)最小的边的另一个顶点,直到最后。
例如:V1作为顶点,V1->V3->V6->V4,V3->V2->V5,连接图中所有的结点即可。
(2)克鲁斯卡尔(Kruskal)算法
基本思想:选择图中最小的边,直到所有结点都连通。
例如:第一小边:V1->V3,第二小边:V4->V6,第三小边:V2-V5,第四小边:V3->V6,第五小边:V3->V2,此时所有的结点都连到了一起。
(3)算法对比
普里姆算法更加注重的是结点,点与点之间距离最短的优先;克鲁斯卡尔算法更加注重的是边,将边排序,最小边排在前面,最大边排在后面。
总结
由于图的内容相对要简单,所以我们讲解的内容相对而言要少,就当是精益求精吧。后面的排序和算法才是我们的重点,后面的博文马上杀到。
后续博客的更新列表,敬请期待。
我的软考之路(一)——开篇(已更新)
我的软考之路(二)——J2SE宏观总结(已更新)
我的软考之路(三)——数据结构与算法(1)之线性表(已更新)
我的软考之路(四)——数据结构与算法(2)之树与二叉树(已更新)
我的软考之路(六)——数据结构与算法(4)之八大排序(已更新)
相关推荐
.1_编程的灵魂——数据结构+算法=程序.ppt.1_编程的灵魂——数据结构+算法=程序.ppt.1_编程的灵魂——数据结构+算法=程序.ppt.1_编程的灵魂——数据结构+算法=程序.ppt
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法...
编程的灵魂——数据结构+算法=程序编程的灵魂——数据结构+算法=程序编程的灵魂——数据结构+算法=程序编程的灵魂——数据结构+算法=程序
《C++语言描述——数据结构算法与应用》高清版
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
数据结构、算法与应用——C++语言描述.rar
数据结构与算法——C++版(第3版)源文件
《C++语言描述——数据结构算法与应用》高清版 经典的数据结构教材,第二版尚未在国内出版,与第一版区别主要是部分代码更新,但数据结构作为经典内容主干还是不变的 分栏的pdf,非影印扫描版,方便学习
软考辅导—数据结构与算法 ppt 数据结构的主要逻辑结构 线性结构:线性表、栈、队列、数组、广义表 非线性结构:树、图 常用的排序算法、查找算法、数值计算、字符串处理、数据压缩算法、递归算法、图的相关算法 ...
数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院...
数据结构——————KMP算法
数据结构与算法分析——Java语言描述.pdf
C++数据结构与算法,本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾 了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
五大常见算法策略之——回溯策略,算法数据结构 五大常用算法
——————————————————————————————————————————————————————————————————————————— C#数据结构和算法
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
《C语言描述——数据结构算法与应用》绝对高清版 经典计算机书籍!内容十分十分全面,几乎涵盖一切C和C++的算法。 可贵的是,本书不仅仅介绍了理论知识,还提供了50多个应用实例及600多道练习题以加深你的功力!
数据结构与算法(c++),里面有7个pdf文件 本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图...