数据结构CC版第8章 掌握图形结构.pptx

《数据结构CC版第8章 掌握图形结构.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C语言版）项目八掌握图形结构图作为一种非线性数据结构，被广泛应用于多种技术领域，如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等。这些技术领域把图作为解决问题的数学手段之一。离散数学侧重于对图的理论进行系统的研究。在本项目中，通过1个工作任务，向读者介绍图的应用与操作。目录任务实现图的遍历实现图的遍历准备知识实现图的遍历图的定义与基本术语图的概述图的相关术语图的抽象数据类型和基本操作邻接矩阵表示法邻接表表示法十字链表邻接多重表深度优先搜索广度优先搜索实现图的遍历准备知识11.最短路径问题12.单源最短路径问题13

2、.狄克斯特拉(Dikastra)算法14.最小生成树15.最小生成树的性质16.构造最小生成树的算法17.拓扑排序18.AOV网19.拓扑排序(TopologicalSort)1.图的定义与基本术语1.图的定义与基本术语图状结构较树形结构来说是一种更一般的非线性结构，它可以用来表示数据对象之间的任意关系，因此在现实生活中应用也更加广泛。例如在五个地区之间建立通信网络，要求其中任意两个地区之间都有直接或间接的通信线路，已知每两个地区间通信线路的造价，求如何建立满足要求的通信网络并使总造价最低。求最小生成树1.图的定义与基本术语把每个地区表示成一

3、个结点，每对结点之间的边表示它们之间存在通信线路，边上的数值表示通信线路的造价，得到如下图所示的图。此问题的求解就是著名的求最小生成树的问题。2.图的概述2.图的概述图(Graph)是由非空的顶点(Vertex)集合和描述顶点之间的关系——边(Edge)或弧(Arc)的集合组成。其形式化定义为：G=(V，E)V={vi

4、vi∈某个数据元素集合}E={(vi,vj)

5、vi,vj∈V∧P(vi,vj)}或E={

6、vi,vj∈V∧P(vi,vj)}其中，G表示图；V是顶点的集合；E是边或弧的集合。在集合E中，P(vi,vj)表示顶点v

7、i和顶点vj之间有边或弧相连。2.图的概述如图所示给出了图的示例。(a)无向图(b)有向图图的示例知识点链接由图的形式化定义可知，图的抽象数据类型Graph的数据集合包括顶点集合V和边/弧的集合E。3.图的相关术语3.图的相关术语图是相对较复杂的数据结构，图的相关术语也比较多，包括无向图、无向完全图、有向图、有向完全图、阶、带权图、邻接点、顶点的度、出度和入度、自环、子图、路径，路径长度和回路、距离和桥、连通图与连通分量、强连通图和强连通分量、生成树和生成森林。4.图的抽象数据类型和基本操作4.图的抽象数据类型和基本操作图的抽象数据类型定义如

8、下：ADTGraph{（1）数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。（2）数据关系R：R={VR}VR={

9、v,w∈V且P(v,w)，表示从v到w的弧，P(v,w)定义了弧的意义}（3）图的基本操作。}4.图的抽象数据类型和基本操作图的基本操作如下：（1）创建图：创建一个图。（2）判断图是否为空：若图G为空，则返回真值，否则返回假值。（3）求图的顶点：求图的顶点数量。（4）清空图：从图中清除所有数据元素，图为空。（5）求图的边的数目：求图中边或弧的数目。（6）添加边：在图的两个顶点间添加边或弧。

10、（7）删除边：删除两个顶点之间的边或弧。（8）判断是否有边：判断两个顶点之间是否有边或弧。知识点链接数据结构在存储时主要考虑两方面：如何存储数据；如何存储数据间的关系。当数据和关系都存储在存储器中时，就可以按数据间的关系，实现对数据的各种操作。图的存储方法多种多样，对于不同的应用问题有不同的表示方法。图有以下几种比较常用的存储方法：邻接矩阵表示法、邻接表、邻接多重表、十字链表。5.邻接矩阵表示法5.邻接矩阵表示法在图的邻接矩阵表示法中：（1）用邻接矩阵表示顶点间的相邻关系（2）用一个顺序表来存储顶点信息5.邻接矩阵表示法下左图、下右图所示图的

11、邻接矩阵效果无向图的邻接矩阵有向图的邻接矩阵邻接矩阵示意图6.邻接表表示法6.邻接表表示法邻接链表（AdjacencyList）是图的一种链式存储结构，与树型结构中的孩子链表相似。通常邻接链表也称邻接表。7.十字链表7.十字链表十字链表（OrthogonalList)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧都有一个结点，对应于每个定顶点也有一个结点。8.邻接多重表8.邻接多重表邻接多重表(AdjacencyMultilist)是无向图的一种存储结构，邻接多重

12、表这种存储结构能够提供更方便的处理。邻接多重表，是对用邻接表存储无向图的一种压缩存储，当然也是链式存储，这个结构在对无向图的边进行操作的时候会比较方便。9.深度优先