数据结构22.ppt

《数据结构22.ppt》由会员分享，可在线阅读，更多相关《数据结构22.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图图的表示和实现图的表示和实现图的邻接矩阵表示图的邻接表表示图的邻接矩阵表示图的邻接矩阵表示v邻接矩阵 不带权图的邻接矩阵带权图的邻接矩阵 邻接矩阵表示的带权图类邻接矩阵表示的带权图类 邻接矩阵表示的带权图类的声明及构造方法 v顶点集合A,B,C,D,E;v边集合(0,1,5),(0,3,2),(1,0,5),(1,2,7),(1,3,6),(2,1,7),(2,3,8),(2,4,3),(3,0,2),(3,1,6),(3,2,8),(3,4,9),(4,2,3),(4,3,9);图的插入操作图的删除操作 带权值的边类 邻接矩阵表示的带权图类 图的邻接表表示图的邻接表表示v邻接表无向图的邻接

2、表表示 有向图的邻接表表示 邻接表表示的带权图类邻接表表示的带权图类 顶点表元素类邻接表表示的带权图类的声明及构造方法图的插入操作 图的删除操作 邻接表表示的图类图的遍历图的遍历 图图的的遍遍历历（traversing graph）是是指指从从图图中中的的某某一一顶顶点点出出发发，对对图图中中的的所所有有顶顶点点访访问问一一次次，而而且且仅仅访访问问一一次次。图图的的遍遍历历是是图图的的一一种种基基本本操操作作。由由于于图图结结构构本本身身的的复复杂杂性性，所所以以图图的遍历操作也较复杂，主要表现在以下四个方面：的遍历操作也较复杂，主要表现在以下四个方面：（1）在在图图结结构构中中，每每一一个

3、个结结点点的的地地位位都都是是相相同同的的，没没有有一一个个“自自然然”的的首首结结点点，图图中中任任意意一一个个顶顶点点都都可可作作为为访访问问的的起起始结点。始结点。（2）在在非非连连通通图图中中，从从一一个个顶顶点点出出发发，只只能能够够访访问问它它所所在在的的连连通通分分量量上上的的所所有有顶顶点点，因因此此，还还需需考考虑虑如如何何访访问问图图中中其其余的连通分量。余的连通分量。（3）在在图图结结构构中中，如如果果有有回回路路存存在在，那那么么一一个个顶顶点点被被访访问问之后，有可能沿回路又回到该顶点。之后，有可能沿回路又回到该顶点。（4）在在图图中中，一一个个顶顶点点可可以以和和其

4、其它它多多个个顶顶点点相相连连，当当这这个个顶点访问过后，就要考虑如何选取下一个要访问的顶点。顶点访问过后，就要考虑如何选取下一个要访问的顶点。图的遍历图的遍历1 图的深度优先搜索遍历2 图的广度优先搜索遍历深度优先搜索深度优先搜索 深深度度优优先先搜搜索索（Depth-Fisrst Search）遍遍历历类类似似于于树树的的先先根遍历，是树的先根遍历的推广。根遍历，是树的先根遍历的推广。假假设设初初始始状状态态是是图图中中所所有有顶顶点点未未曾曾被被访访问问，则则深深度度优优先先搜搜索索可可从从图图中中某某个个顶顶点点发发v出出发发，首首先先访访问问此此顶顶点点，然然后后任任选选一一个个v的

5、的未未被被访访问问的的邻邻接接点点w出出发发，继继续续进进行行深深度度优优先先搜搜索索，直直到到图图中中所所有有和和v路路径径相相通通的的顶顶点点都都被被访访问问到到；若若此此时时图图中中还还有有顶顶点点未未被被访访问问到到，则则另另选选一一个个未未被被访访问问的的顶顶点点作作为为起始点，重复上面的做法，直至图中所有的顶点都被访问。起始点，重复上面的做法，直至图中所有的顶点都被访问。V1V5V2V4V8V3V6V7无向图无向图G5 以以左左图图的的无无向向图图G5为为例例，其其深深度度优优先先搜搜索索得得到到的的顶顶点点访访问问序序列为：列为：v1 v2 v4 v8 v5 v3 v6、v77.

6、3.1 图的深度优先搜索遍历图的深度优先搜索遍历2 广度优先搜索广度优先搜索 广度优先搜索广度优先搜索 遍历类似于树的按层次遍历。遍历类似于树的按层次遍历。假假设设从从图图中中某某顶顶点点v出出发发，在在访访问问了了v之之后后依依次次访访问问v的的各各个个未未曾曾访访问问过过的的邻邻接接点点，然然后后分分别别从从这这些些邻邻接接点点出出发发依依次次访访问问它它们们的的邻邻接接点点，并并使使“先先被被访访问问的的顶顶点点的的邻邻接接点点”先先于于“后后被被访访问问的的顶顶点点的的邻邻接接点点”被被访访问问，直直至至图图中中所所有有已已被被访访问问的的顶顶点点的的邻邻接接点点都都被被访访问问到到。

7、若若此此时时图图中中尚尚有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，重重复复上上述述过过程程，直直至至图图中中所所有有顶顶点点都都被被访访问问到到为为止止。换换句句话话说说，广广度度优优先先搜搜索索遍遍历历图图的的过过程程中中以以v为为起起始始点点，由由近近至至远远，依依次次访访问和问和v有路径相通且路径长度为有路径相通且路径长度为1，2，的顶点。的顶点。图的广度优先搜索遍历图的广度优先搜索遍历 对对左左图图所所示示的的无无向向图图G5进进行行广广度度优优先先搜搜索索遍遍历历，首首先先访访问问v1 和和v1的的邻邻接接点点v2和和

8、v3，然然后后依依次次访访问问v2 的的邻邻接接点点v4 和和v5 及及v3 的的邻邻接接点点v6和和v7，最最后后访访问问v4 的的邻邻接接点点v8。由由于于这这些些顶顶点点的的邻邻接接点点均均已已被被访访问问，并并且且图图中中所所有有顶顶点点都都被被访访问问，由由些些完完成成了了图图的的遍遍历历。得到的顶点访问序列为：得到的顶点访问序列为：v1v2 v3 v4 v5 v6 v7 v8 和和深深度度优优先先搜搜索索类类似似，在在遍遍历历的的过过程程中中也也需需要要一一个个访访问问标标志志数数组组。并并且且，为为了了顺顺次次访访问问路路径径长长度度为为2、3、的的顶顶点点，需需附附设设队队列列

9、以以存存储储已已被被访访问问的的路路径径长长度度为为1、2、的顶点。的顶点。V1V5V2V4V8V3V6V7 无向图无向图G5 最小生成树最小生成树 生成树生成树v树v生成树和生成森林 v最小生成树 最小生成树的构造算法最小生成树的构造算法vPrim算法 2.Kruskal算法算法 最短路径最短路径小小 结结（1 1）图图是是一一种种复复杂杂的的数数据据结结构构，图图中中的的每每一一个个顶顶点点都都可可以以有有多多个个直直接接前驱和多个直接后继，所以是一种非线性的数据结构。前驱和多个直接后继，所以是一种非线性的数据结构。（2 2）因因为为图图是是由由顶顶点点的的集集合合和和顶顶点点间间边边的的

10、集集合合组组成成，所所以以图图的的存存储储也也包括顶点信息和边的信息两个方面。包括顶点信息和边的信息两个方面。（3）图的存储结构常用的有：邻接矩阵和邻接表等要求理解。）图的存储结构常用的有：邻接矩阵和邻接表等要求理解。（4）对于）对于n个顶点的图来说，它的邻接矩阵是一个个顶点的图来说，它的邻接矩阵是一个nn阶的方阵。邻接阶的方阵。邻接矩阵中的元素取值只能是矩阵中的元素取值只能是0或或1，若图为无向图，则矩阵一定是对称矩阵，若图为无向图，则矩阵一定是对称矩阵，所以可以采用压缩存储；若是网，则要存储的是权值。所以可以采用压缩存储；若是网，则要存储的是权值。（5）对于由）对于由n个顶点和个顶点和e

11、条边的图，它的邻接表由条边的图，它的邻接表由n个单链表所组成。个单链表所组成。无向图的邻接表占用无向图的邻接表占用n+2e个存储单元；有向图的邻接表占用个存储单元；有向图的邻接表占用n+e个存储个存储单元。单元。（6 6）图图的的遍遍历历就就是是从从图图的的某某一一顶顶点点出出发发，访访问问图图中中每每个个顶顶点点一一次次且且仅仅一一次次。遍遍历历的的基基本本方方法法有有深深度度优优先先搜搜索索遍遍历历和和广广度度优优先先搜搜索索遍遍历历两两种种。深深度度优优先先遍遍历历类类似似于于树树的的先先序序遍遍历历；广广度度优优先先遍遍历历类类似似于于树树的的按按层层次次遍遍历。历。作业作业v有如下图所示的无向图，请以写出以H为起点的深度优先和广度优先遍历序列。