PowerPoint Presentation - 华中师范大学

2020/3/111第7章图本章主题：图的基本概念、图的存储结构和图的常用算法教学目的：教学重点：图的各种存储方式及其运算教学难点：图结构存储方式的选择，几种经典图算法的实现本章内容：图的基本概念图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径2020/3/112本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该：1)了解图的定义和术语2)掌握图的各种存储结构3)掌握图的深度优先搜索和广度优先搜索遍历算法4)理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法本章学习导读2020/3/113图（Graph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。2020/3/1147.1.1图的定义图是由一个顶点集V和一个弧集R构成的数据结构。Graph=(V,R)V={x|x某个数据对象}，是顶点的有穷非空集合；R——边的有限集合R={(x,y)|x,yV}无向图或R={x,y|x,yV&&Path(x,y)}有向图是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条单向通路,它是有方向的。x弧尾，y弧头。7.1图及其基本运算2020/3/115有向图与无向图有向图中：边用x,y表示，且x与y是有序的。a.有向图中的边称为“弧”b.x——弧尾或初始点y——弧头或终端点无向图：边用(x,y)表示，且顶x与y是无序的。完全图在具有n个顶点的有向图中，最大弧数为n(n-1)在具有n个顶点的无向图中，最大边数为n(n-1)/2顶点的度无向图：与该顶点相关的边的数目有向图：入度ID(v)：以该顶点为头的弧的数目出度OD(v)：以该顶点为尾头的弧的数目在有向图中,顶点的度等于该顶点的入度与出度之和。2020/3/116（a)G1（b)G2（c)G3（d)G45234112346752222364521图7-1无向图和有向图2020/3/117在图7-1中，图(a)为无向图，其中G1的顶点集合和边集合分别为：V(G1)={1，2，3，4，5，6，7}，E(G1)={(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)}。图(c)为有向图，其中G3的顶点集合和弧集合分别为V(G3)={1，2，3，4，5，6}，E(G3)={1，2，1，3，1，4，3，1，4，5，5，6，6，4}2020/3/1187.1.2图的基本术语1．顶点的度与顶点v相关的边或弧的数目称作顶点v的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。例如图7-1中，无向图G1中顶点3的度为4，顶点5的度为3。例如在图7-1中，有向图G3中顶点1的出度OD(1)=3，入度ID(1)=1，其度TD(1)=4。2020/3/1192．路径和回路在无向图G中，若存在一个顶点序列Vp,Vi1，Vi2，…，Vin，Vq,使得（Vp,Vi1）,(Vi1,Vi2),…..，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路；简单路径组成的回路称为简单回路。路径长度路径上经过的边的数目称为该路径的路径长度。非带权图的路径长度是指此路径上边/弧的条数。带权图的路径长度是指路径上各边/弧的权之和。2020/3/11102020/3/11113.边和弧边:无向图中顶点的偶对，写成（Vx，Vy）或（Vy，Vx）。弧:有向图中顶点的偶对,〈Vx,Vy〉表示从Vx到Vy。弧头:弧的终点弧尾:弧的起点弧〈Vx，Vy〉弧尾Vx弧头Vy2020/3/11124．子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。2020/3/111312345(a)12345(b)1245(c)145(d)22020/3/11145．连通性在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点vi和vj（vi，vj∈V）都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。6．强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。2020/3/1115(a)无向网(b)有向网图7-4无向带权图和有向带权图5312441672358ABC215347．网络权某些图的边或弧具有与它相关的数,称之为权。权可以代表一个顶点到另一个顶点的距离，耗费等。网络这种带权连通图一般称为网络。如图7-4所示。2020/3/11168．生成树、生成森林生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的是连同图的极小连同子图包含图中的所有顶点有且仅有n-1条边非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。2020/3/11179．邻接点顶点:图中的结点邻接点:无向图中，若边(Ｖx,Ｖy)E，两顶点之间有条边，则两顶点互为邻接点。x——y(x,y)有向图中，若弧(Ｖx,Ｖy)E，从x到y有一条弧，则y是x的邻接点，但x不是y的邻接点。xyx,yVxVyＶx、Ｖy互为邻接点VxVyＶy是Ｖx的邻接点2020/3/11187.1.3图的基本运算图的基本运算:见P1562020/3/11197.2.1邻接矩阵邻接矩阵(AdjacencyMatrix)是表示顶点之间相邻关系的矩阵。设G＝(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵。7.2图的存储结构Aij=1对无向图若存在边(vi,vj),对有向图若存在弧vi,vj0反之无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。在有向图中：第i行1的个数就是顶点i的出度，第j列1的个数就是顶点j的入度。在无向图中,第i行(列)1的个数就是顶点i的度。2020/3/112014320011000010100101(a)(b)图7-6有向图及其邻接矩阵154320010101011001001110010011(a)(b)图7-5无向图及其邻接矩阵2020/3/1121对于无向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。对有向图，弧vi，vj和vj，vi表示方向不同的两条弧，Aij和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。邻接矩阵表示法适合于以顶点为主的运算。2020/3/1122对于有向图，顶点vi的出度OD(vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID(vi)等于邻接矩阵第i列元素之和，即：对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即：njjiA1],[njjiA1],[njijA1],[OD(vi)=ID(vi)=TD（vi）=对于带权图的邻接矩阵，定义为：Aij=Wij若(vi,vj)或vi,vj∈E，Wij为该边或弧的权∞反之2020/3/1123顶点表:一个记录各个顶点信息的一维数组，邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下：#defineMAX_VERTEX_NUM20//最大顶点数typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵类型typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点表AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的顶点数和弧数}MGraph;由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。2020/3/11247.2.2邻接表图的链式存储结构1)为每个顶点建立一个单链表，2)第i个单链表中包含顶点Vi的所有邻接顶点。邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。2020/3/1125把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点（边结点），邻接点域adjvex保存与该边相关联的另一顶点的顶点下标，链域nextarc存放指向同一链表中下一个表结点的指针，数据域info存放边的权。边链表的表头指针存放在头结点中。头结点以顺序结构存储，其数据域data存放顶点信息，链域firstarc指向链表中第一个顶点。表结点头结点adjvexnextarcinfodatafirstarc2020/3/1126带权图的边结点中info保存该边上的权值。顶点Vi的边链表的头结点存放在下标为i的顶点数组中。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。2020/3/1127有向图的邻接表和逆邻接表在有向图的邻接表中，第i个链表中结点的个数是顶点Vi的出度。在有向图的逆邻接表中，第i个链表中结点的个数是顶点Vi的入度。2020/3/1128图7-7为图7-6(a)的的邻接表和逆邻接表图7-7有向图的邻接表和逆邻接表7-6(a)(b)41320212310123(c)143213003201232020/3/1129网络(带权图)的邻接表2020/3/1130存储表示typedefstructArcNode{intadjvex;structArcNode*nextarc;intinfo;}ArcNode;//边结点类型typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;//邻接表intvexnum,arcnum;}ALGraph;2020/3/11317.2.3十字链表十字链表(OrthogonalList)是有向图的另一种链式存储结构。可看作是将有向图的邻接表和逆邻接表结合的一种链表。在十字链表中，为每个顶点vi设置一个结点，它包含数据域data和两个链域firstout、firstin，称为顶点结点。数据域data用于存放顶点vi的有关信息；链域firstin指向以顶点vi为弧头的第一个弧结点；链域firstout指向以顶点vi为弧尾的第一个弧结点。弧结点包括四个域：尾域tailvex、头域headvex，链域hlink和tlink。hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧；data顶点信息，firstin以该顶点为头的第一个弧结点，firstout以该结点为尾的第一个弧结点headvextailvexhlinktlinkinfofirstin