数据结构与算法之图

梦里梦外; 2022-06-07 02:23 184阅读 0赞

图跟树一样，也是非线性结构，咋看起来有点复杂，其实它很简单。树具有层次关系，上层元素可以与下一个多个元素连接，但是只能和上层的一个元素连接。在图结构中，节点间的连接是任意的，任何一个元素都可以与其他元素连接。

图相对而言很简单，我们只介绍的图的遍历和最小生成树，现在我们开始。

# 遍历 #

1.概念

从图中某一个顶点出发，访问图中的每一个结点，并要求只能访问一次，不能重复访问。

2.方法

![SouthEast][]

（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

总结，图的广度优先遍历和深度优先遍历的结果并不唯一。

# 最小生成树 #

![SouthEast 1][]

（1）普里姆（Prim）算法  
基本思想：选一个顶点开始，查找与顶点相邻且代价（边值）最小的边的另一个顶点，直到最后。  
例如：V1作为顶点，V1->V3->V6->V4，V3->V2->V5，连接图中所有的结点即可。  
（2）克鲁斯卡尔（Kruskal）算法  
基本思想：选择图中最小的边，直到所有结点都连通。  
例如：第一小边：V1->V3，第二小边：V4->V6，第三小边：V2-V5，第四小边：V3->V6，第五小边：V3->V2，此时所有的结点都连到了一起。  
（3）算法对比  
普里姆算法更加注重的是结点，点与点之间距离最短的优先；克鲁斯卡尔算法更加注重的是边，将边排序，最小边排在前面，最大边排在后面。

# 总结 #

由于图的内容相对要简单，所以我们讲解的内容相对而言要少，就当是精益求精吧。后面的排序和算法才是我们的重点，后面的博文马上杀到。

[SouthEast]: /images/20220607/dcad6072758e47a7971db6cb80e58dd9.png
[SouthEast 1]: /images/20220607/2687d079e66c434a97c3eabcc07d2412.png

发表评论取消回复

表情：

评论列表（有 0 条评论，184人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法之图的应用

一.树之习题选讲-Tree Traversals Again 树习题-TTA.1 题意理解非递归中序遍历的过程 1. Push的顺序为先序遍历(pre)

旧城等待，/ 2024年03月31日 15:17/ 0 赞/ 55 阅读

相关【数据结构与算法之图结构】案例

【数据结构与算法之图结构】案例文章目录【数据结构与算法之图结构】案例 1 迷宫问题 1 迷宫问题如

超、凢脫俗/ 2024年03月25日 16:38/ 0 赞/ 105 阅读

相关【数据结构与算法之图结构】图的遍历

【数据结构与算法之图结构】图的遍历文章目录【数据结构与算法之图结构】图的遍历 1 深度优先搜索遍历

ゝ一纸荒年。/ 2024年03月25日 16:38/ 0 赞/ 113 阅读

相关【数据结构与算法之图结构】图的存储形式

【数据结构与算法之图结构】图的存储形式文章目录【数据结构与算法之图结构】图的存储形式常见的图的存储形式有两种：邻接矩阵邻

红太狼/ 2024年03月25日 14:13/ 0 赞/ 7 阅读

相关【数据结构与算法之图结构】图的基本概念

【数据结构与算法之图结构】图的基本概念文章目录【数据结构与算法之图结构】图的基本概念 1 图的定义

末蓝、/ 2024年03月25日 14:13/ 0 赞/ 47 阅读

相关算法与数据结构之图

重要概念 1. 在数据结构中，线性结构，树形结构和图形结构数据元素之间分别存着一对一，一对多，多对多的联系。 2. n个顶点的连通图至少有n-1条边。 3. 有向图G

水深无声/ 2022年12月17日 04:25/ 0 赞/ 183 阅读

相关【数据结构与算法】图

一：如何理解“图” 1，图和树一样都是非线性表数据结构，和树不同的是图是一种更加复杂的非线性表结构 2，树中的元素称之为节点，图中的元素则称之为顶点。 3，顶点可以

港控/mmm°/ 2022年11月30日 04:20/ 0 赞/ 170 阅读

相关数据结构与算法之图

图跟树一样，也是非线性结构，咋看起来有点复杂，其实它很简单。树具有层次关系，上层元素可以与下一个多个元素连接，但是只能和上层的一个元素连接。在图结构中，节点间的连接是任意的，任

梦里梦外;/ 2022年06月07日 02:23/ 0 赞/ 185 阅读

相关 C++数据结构与算法（图）

> 回顾：线性表中，每个元素只有一个直接前驱和直接后继，在树形结构中，数据之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。但这都

谁借莪１个温暖的怀抱￠/ 2021年10月31日 16:30/ 0 赞/ 397 阅读

相关数据结构与算法之图

图基本概念无向图和有向图 ![70][] 前一个不带箭头的就是无向图，后一个带尖头的就是有向图子图如果图G中包含G1，那么G1就是G的

桃扇骨/ 2021年06月11日 15:11/ 0 赞/ 546 阅读