数据结构（c语言描述） 教学课件 作者 库波 第7章 图.ppt

《数据结构（c语言描述） 教学课件 作者 库波 第7章 图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C#）主编：库波第7章图7.1基本定义和术语7.2图的存储结构7.3图的遍历7.4最小生成树7.5最短路径7.6拓扑排序图（Graph）是一种较为复杂的数据结构，是一种图状结构，比线性表和数更为复杂的数据结构。在图中，任何结点都可以相互建立联系，可以任意连接，图中的任意两个结点之间都有可能相关。近年来信息社会飞速发展，图的应用更为广泛，已渗透到逻辑学、物理、化学、语言学、计算机科学、人文科学和自然科学中，以及数学中。7.1基本定义和术语图(Graph)是由非空的顶点(Vertices)集合和描述顶点之间的关系——边（Edge）或弧（A

2、rc）的集合组成。其形式化定义为：G＝（V，E）V＝{Vi

3、Vi∈dataobject}E＝{(Vi，Vj)

4、Vi,Vj∈V∧P(Vi,Vj)}图的定义（1）无向图（2）有向图（3）顶点、边、弧、弧头、弧尾（4）无向完全图、有向完全图（5）顶点的度、入度、出度（6）边的权、网图（7）路径、路径长度（8）简单路径、回路、简单回路（9）子图（10）连通图、连通分量（11）强连通图、强连通分量（12）生成树（13）生成森林图的相关术语图的基本操作图和其他的数据结构一样，它的基本操作包括查找、插入和删除。图的基本操作说明：1）GetNumOfVerte

5、x()如果图存在；则返回图中的顶点数。2）GetNumOfEdge()如果图存在；则返回图中的边或弧的数目。基本定义和术语3）SetEdge(NodeV1,NodeV2,intv)如果图存在，顶点V1和V2是图的两个顶点；那么在顶点V1和V2之间添加一条边或弧并设边或弧的值为v。4）DelEdge(NodeV1,NodeV2)如果图存在，顶点V1和V2是图的两个顶点并且V1和V2之间有一条边或弧；则删除顶点V1和V2之间的边或弧。5）IsEdge(NodeV1,NodeV2)如果图存在，顶点V1和V2是图的两

6、个顶点；如果V1和V2之间有一条边或弧，返回true,否则返回false。基本定义和术语例：在无向图G1和有向图G2中找出各个顶点的入度和出度。基本定义和术语例:如下图所示无向网图，查看各条边的特点和权值。7.2图的存储结构图的结构很复杂，任意两个顶点之间都有可能存在联系，所以没有办法用数据元素在存储区中的物理位置来表示元素与元素之间的关系，但是，可以借助元素与元素相邻接的关系来表示元素之间的关系。下面将介绍两种常用的表示方法，对无向图和有向图都有效，它们是邻接矩阵和邻接表表示法。邻接矩阵邻接矩阵（AdjacencyMatrix）很容易判断任意

7、两个顶点之间是否有边或弧相连接，并且容易得出图中各个顶点的度。设图G＝(V，E)是具有n个顶点，图的邻接矩阵是n阶方阵A，若G是无向图，其中的元素表示为：若G是网络，则邻接矩阵可定义为：例：无向图G7和有向图G8的邻接矩阵分别为A1和A2，用邻接矩阵表表示。无向图G7和有向图G8邻接表邻接表（AdjacencyList）是图的一种链式存储结构。在邻接表中，图的各个顶点也是顺序存放的。在邻接表中，我们为每个顶点建立一个单链表结点，把所有邻接于某个顶点的顶点构成一个表，采用链式存储结构。每个单链表由邻接顶点域adjvex和引用域next表示，邻接顶

8、点域用来存放邻接顶点的信息，即邻接顶点在顶点数组中的序号；引用域用来存放下一个邻接点的地址。例：用邻接表表示无向图G7和有向图G8。邻接表算法无向图邻接表的存储结构可用无向图邻接表类来表示，类中主要存储的是邻接表结点。邻接表结点用类adjListNode来描述，类中有两个成员，一个是存储邻接顶点adjvex的信息，一个是存储下一个邻接表节点next的地址，类的实现见教材。}无向图邻接表中顶点节点类用VexNode表示，它包括两个成员字段，一个是用来存储图中顶点本身的信息data，一个用来存储顶点的邻接表中第一个结点的地址firstA

9、dj。VexNode的实现见教材。7.2图的存储结构无向图邻接表中包括顶点结点和邻接表结点，把这些结点组合到一起，我们还需要定义一个无向图邻接表类GraphAdjList，该类中有一个成员字段用来表示邻接表数组adjList。GraphAdjList类继承了接口IGraph，并实现了其中的方法，两个方法成员是IsNode和GetIndex。功能与GraphMatrix一样。无向图邻接表类GraphAdjList的实现见教材。在无向图邻接表类中，有几个方法需要说明一下：1）GetNumOfVertex()方法算

10、法思路：要求无向图的顶点数量，直接返回adjList数组的长度即可。2）GetNumOfEdge()方法算法思路：要求无向图的边数，需要求出所有顶点的