7.2 图的定义

图是由顶点的有穷非空集和顶点之间边的集合，通常表示为：G(V. E)，其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。

07数据结构——图 随笔 第1张

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

07数据结构——图 随笔 第2张

07数据结构——图 随笔 第3张07数据结构——图 随笔 第4张

07数据结构——图 随笔 第5张

07数据结构——图 随笔 第6张07数据结构——图 随笔 第7张07数据结构——图 随笔 第8张

07数据结构——图 随笔 第9张07数据结构——图 随笔 第10张

07数据结构——图 随笔 第11张

07数据结构——图 随笔 第12张

07数据结构——图 随笔 第13张

7.3图的抽象数据类型

 07数据结构——图 随笔 第14张 07数据结构——图 随笔 第15张

7.4   图的存储

7.4.1 邻接矩阵

07数据结构——图 随笔 第16张

07数据结构——图 随笔 第17张

07数据结构——图 随笔 第18张

07数据结构——图 随笔 第19张

07数据结构——图 随笔 第20张07数据结构——图 随笔 第21张

07数据结构——图 随笔 第22张07数据结构——图 随笔 第23张07数据结构——图 随笔 第24张

7.4.2  邻接表

07数据结构——图 随笔 第25张07数据结构——图 随笔 第26张07数据结构——图 随笔 第27张

07数据结构——图 随笔 第28张

07数据结构——图 随笔 第29张07数据结构——图 随笔 第30张07数据结构——图 随笔 第31张07数据结构——图 随笔 第32张

07数据结构——图 随笔 第33张07数据结构——图 随笔 第34张07数据结构——图 随笔 第35张07数据结构——图 随笔 第36张

7.4.3 十字链表

07数据结构——图 随笔 第37张07数据结构——图 随笔 第38张07数据结构——图 随笔 第39张07数据结构——图 随笔 第40张

7.5  图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。

 07数据结构——图 随笔 第41张07数据结构——图 随笔 第42张

07数据结构——图 随笔 第43张07数据结构——图 随笔 第44张

07数据结构——图 随笔 第45张07数据结构——图 随笔 第46张07数据结构——图 随笔 第47张

07数据结构——图 随笔 第48张07数据结构——图 随笔 第49张07数据结构——图 随笔 第50张

07数据结构——图 随笔 第51张07数据结构——图 随笔 第52张

07数据结构——图 随笔 第53张07数据结构——图 随笔 第54张

07数据结构——图 随笔 第55张07数据结构——图 随笔 第56张

7.6生成树

07数据结构——图 随笔 第57张

07数据结构——图 随笔 第58张

7.6.1最小生成树

07数据结构——图 随笔 第59张

07数据结构——图 随笔 第60张07数据结构——图 随笔 第61张

07数据结构——图 随笔 第62张07数据结构——图 随笔 第63张07数据结构——图 随笔 第64张

普里姆算法

07数据结构——图 随笔 第65张

第一步：随机从所有顶点集合V中选取一个初始顶点，然后把这个顶点放入集合U中，集合W=V-U； 第二步：计算集合U中这个顶点到集合W中所有顶点距离最小的那个顶点，把这个顶点从集合W中移入到集合U中； 第三步：因为有集合U中刚刚有新的顶点加入，所以现在需要更新集合U中顶点到集合W中顶点的距离，计算刚刚加入的这个顶点到集合W中每个顶点的距离和
原先集合U中顶点到集合W中顶点的距离做比较，如果前者更小，则更新这个最小距离；
第四步：重复以上步骤。

举个例子：

07数据结构——图 随笔 第66张

第一步：随机选取一个顶点，放入集合U中，假设为顶点1，则U={1}，W={2,3,4,5,6}，计算顶点1到顶点2，3,4,5,6的距离，连接距离最小的边13；

07数据结构——图 随笔 第67张

第二步：把距离最小的顶点3，从W集合中移入到U集合中；

第三步：计算顶点3与顶点2,4,5,6的距离，如果顶点3与顶点2的距离比顶点1与顶点2的距离小，则更新这个最小距离，否则不更新，同理就算顶点4,5,6，连接最小的边36；

07数据结构——图 随笔 第68张

第四步：重复以上步骤一二三。

 

07数据结构——图 随笔 第69张

 07数据结构——图 随笔 第70张07数据结构——图 随笔 第71张07数据结构——图 随笔 第72张07数据结构——图 随笔 第73张07数据结构——图 随笔 第74张07数据结构——图 随笔 第75张07数据结构——图 随笔 第76张07数据结构——图 随笔 第77张07数据结构——图 随笔 第78张07数据结构——图 随笔 第79张

克鲁斯卡尔算法

07数据结构——图 随笔 第80张07数据结构——图 随笔 第81张

07数据结构——图 随笔 第82张07数据结构——图 随笔 第83张07数据结构——图 随笔 第84张

07数据结构——图 随笔 第85张07数据结构——图 随笔 第86张07数据结构——图 随笔 第87张

07数据结构——图 随笔 第88张

7.7最短路径

07数据结构——图 随笔 第89张

07数据结构——图 随笔 第90张07数据结构——图 随笔 第91张

07数据结构——图 随笔 第92张

07数据结构——图 随笔 第93张 

 07数据结构——图 随笔 第94张

07数据结构——图 随笔 第95张07数据结构——图 随笔 第96张07数据结构——图 随笔 第97张

07数据结构——图 随笔 第98张

07数据结构——图 随笔 第99张

07数据结构——图 随笔 第100张07数据结构——图 随笔 第101张07数据结构——图 随笔 第102张

07数据结构——图 随笔 第103张07数据结构——图 随笔 第104张07数据结构——图 随笔 第105张07数据结构——图 随笔 第106张07数据结构——图 随笔 第107张07数据结构——图 随笔 第108张07数据结构——图 随笔 第109张07数据结构——图 随笔 第110张

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄