数据结构 课件 第8章 图 .pptx

第8章图总体要求：熟悉图的定义熟悉图的抽象数据类型描述中各种操作的含义掌握图的存储结构熟练掌握图各种存储接结构下的建立、遍历算法熟练掌握带权图的最小生成树的定义和普里姆算法、克鲁斯卡尔算法熟练掌握带权图的最短路径的定义和迪杰斯特拉算法、弗洛伊德算法核心技能点：具有图理论应用于实际问题的能力1

第8章图8.1图的实例及概念8.1.1实例8.1.2图的定义和基本概念8.2图的存储结构及实现8.2.1邻接矩阵8.2.2邻接链表8.2.3图的ADT定义8.3遍历图8.3.1深度优先有哪些信誉好的足球投注网站法8.3.2广度优先有哪些信誉好的足球投注网站2

第8章图8.4最小生成树8.4.1最小生成树的基本概念8.4.2普里姆算法8.4.3克鲁斯卡尔算法8.5最短路径8.5.1从某个源点到其它各顶点的最短路径8.5.2求每一对顶点之间最短路径8.6上机实验本章小结习题3

第8章图扩展技能点：图各种存储结构和算法C语言环境下的实现相关知识点：C语言数组的知识C语言结构体的知识C语言指针的知识C语言函数的知识离散数学图论的知识4

第8章图学习重点：熟悉图的定义熟悉图的抽象数据类型描述中各种操作的含义掌握图的存储结构熟练掌握图各种存储接结构下的建立、遍历算法熟练掌握带权图的最小生成树的定义和普里姆算法、克鲁斯卡尔算法熟练掌握带权图的最短路径的定义和迪杰斯特拉算法、弗洛伊德算法5

第8章图图(Graph)是一种复杂的非线性结构。在线性表中，数据元素满足唯一的线性关系，每个元素(除第一个元素和最后一个元素之外)，只有一个直接前趋和直接后继；在树型结构中，数据元素有明显的层次关系，并且每个元素只与上层一个元素(双亲结点)及下层中多个元素(孩子结点)相关；而在图型结构中，数据元素之间的关系是任意的，任何两个元素都可以相关，因此它较线性结构和树结构更复杂。图在各个领域的应用是十分广泛的。在计算机的应用领域如开关理论、逻辑设计、人工智能、形式语言、操作系统、编译程序以及信息检索内，图都起着重要的作用；在其他领域如电路分析、项目规划、遗传学、控制论以及一些社会科学中，图的应用也非常普遍。有关图论的内容是离散数学的主要内容之一，因此本章将主要讨论图在计算机中的存储表示、操作的实现及典型的应用等。6

第8章图8.1图的实例及概念8.1.1实例在日常生活中，对象和对象之间的关系常常可以用包括点和线的示意图来表示。如图8.1表示的是我国部分省市之间的铁路交通示意图，反映了这几个城市之间的铁路分布情况。其中，省市用点表示，点和点之间的连线代表了对应的两个省市之间的铁路线。7

第8章图8从以上例子可以看出，点及点之间的连线可被用来反映客观世界中某些对象之间的特定关系。图8．1我国部分省市之间的铁路交通示意图

第8章图8.1.2图的定义和基本概念1．图的定义图(graph)是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph=(V，E)其中，V={x|x∈某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,y∈V}或E={x,y|x,y∈VPath(x,y)}是顶点之间关系的有穷集合，也叫做边(Edge)集合。Path(x,y)表示从x到y的一条单向通路，它是有方向的。9

第8章图2．一些与图有关的基本概念(1)有向图(DirectedGraph)与无向图(UndirectedGraph)。在有向图中，顶点对x,y是有序的，它称为从顶点x到顶点y的一条有向边。因此，x,y与y,x是不同的两条边。此时，顶点对x,y用一对尖括号括起来，x是有向边的始点，y是有向边的终点。在无向图中，顶点对(x,y)是无序的，它称为与顶点x和顶点y相关联的一条边，这条边没有特定的方向，(x,y)与(y,x)是同一条边。一般为了有别于有向图，顶点对用一对圆括号括起来。图8.2中有4个图，其中图G1和G2是无向图，G1的顶点集合为V(G1)={0，l，2，3}，边集合为E(G1)={(0，1)，(0，2)，(0，3)，(1，2)，(1，3)，(2，3)}。G2的顶点集合为V(G2)={0，1，2，3，4，5，6}，边集合为E(G2)={(0，1)，(0，2)，(1，3)，(1，4)，(2，5)，(2，6)}。在无向图中边上不加箭头。图G3和G4是有向图，G3的顶点集合为V(G3)={0，1，2}，边集合为E(G3)={0，1，l，0，1，2}。G4的顶点集合为V(G4)={0，1，2，3}，边集合为E(G4)={0，1，l，0，0，2，2，0，0，3，3，0，l，2，2，1，1，3，3，1，2，3，3，2}。在有向图中，为了表示有向边，按边的方向用箭头画出