《数据结构》--第六章-图

数据的逻辑结构线性结构非线性结构线性表栈队树形结构图形结构串第6章图多对多（m:n)学习目的要求:1.掌握图的基本概念。2.熟练掌握图的存储结构。3.熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。4.掌握最小生成树的普里姆和克鲁斯卡尔算法。5.掌握最短路径的两个经典算法:迪杰斯特拉和弗洛伊德算法。6.掌握拓扑排序的概念，会求拓扑序列。7.了解关键路径。第6章图6.1图的基本术语6.2图的存储结构6.3图的遍历6.4最小生成树6.5最短路径6.6拓扑排序6.7关键路径第6章图6.1图的基本术语6.1.1图的定义1.图（Graph）•图是一种数据结构，图中的数据元素通常用顶点来表示，而数据元素间的关系用边来表示，故图可定义为:图G由两个集合V（G）和E（G）所组成，记作G=（V，E）其中V（G）是图中顶点的非空有限集合，E（G）是边的有限集合（边是V（G）中顶点的无序对或有序对集合）。G1=(V1,E1)V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}V0V4V3V1V2无序对(vi,vj)和(vj,vi)都是表示同一条边，用圆括号括起来。•顶点集V（G）不可为空集，边集E（G）可以为空集。若E（G）为空集，则图G只有顶点且没有边，称为零图。6.1图的基本术语6.1图的基本术语有序对vi,vj：用以vi为起点、vj为终点的有向线段表示，称为有向边或弧；用尖括号括起来。V0V1V2V3G1=(V1,E1)V1={v0v1,v2,v3}E1={v0,v1,v0,v2,v2,v3,v3,v0}2.无向图（Undigraph）如果图中每条边都是顶点的无序对，即每条边在图示时都没有箭头，则称此图为无向图。3.有向图（Digraph）如果图中每条边都是顶点的有序对，即每条边在图示时都用箭头表示方向，则称此图为有向图。6.1图的基本术语图的应用举例【例1】交通图（公路、铁路）顶点：地点边：连接地点的公路【例2】电路图顶点：元件边：连接元件之间的线路【例3】各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系6.1图的基本术语6.1.2图的基本术语1.完全图(CompletedGraph)无向完全图:若一个无向图有n个顶点，且每一个顶点与其他n-1个顶点之间都有边，这样的图称为无向完全图。有向完全图:若一个有向图有n个顶点，且每一个顶点与其他n-1个顶点之间都有一条以该顶点为弧尾的弧，这样的图称为有向完全图。6.1图的基本术语有向边u,v称为弧，边的始点u叫弧尾，终点v叫弧头。证明：证明：若是完全有向图，则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数=n(n-1)证明：从①可以直接推论出无向完全图的边数——因为无方向，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。②无向完全图有n(n-1)/2条边。①有向完全图有n(n-1)条边。12341234例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n(n-1)/2条边n(n-1)条边G1的顶点集合为V(G1)={0,1,2,3}边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全图完全图2.子图（Subgraph）设有两个图A和B且满足条件:V(B)是V(A)的子集，E(B)是E(A)的子集，则称图B是图A的子图。6.1图的基本术语3.路径（Path）在无向图G中，从顶点Vp到Vq的一条路径是顶点序列（Vp，Vi1，Vi2，…，Vin，Vq）且（Vp，Vi1），（Vi1，Vi2），…，（Vin，Vq）是E(G)中的边。路径上边的数目称为路径长度。对于有向图，其路径也是有向的，路径由弧组成。6.1图的基本术语4.简单路径如果一条路径上所有顶点（起始点和终止点除外）彼此都是不同的，则称该路径是简单路径。5.回路（Cycle）和简单回路在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路。简单路径相应的回路称为简单回路。6.1图的基本术语6.1图的基本术语（a）简单路径（b）非简单路径（c）简单回路6.连通图（ConnectedGraph）和强连通图在无向图G中，若从Vi到Vj有路径，则称Vi和Vj是连通的。若G中任意两顶点都是连通的，则称G是连通图。对于有向图而言，若有向图G中每一对不同顶点Vi和Vj之间有从Vi到Vj和从Vj到Vi的路径，则称G为强连通图。6.1图的基本术语非连通图非强连通图非连通图连通图强连通图非强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V46.1图的基本术语7.连通分量和强连通分量连通分量指的是无向图G中的极大连通子图。强连通分量指的是有向图G中的极大强连通子图。注意:•这里是极大而不是最大。•任意一个连通图的连通分量只有一个，即它本身。•非连通图有多个连通分量。6.1图的基本术语该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通连通分量非连通图V0V2V3V1V5V4V0V2V1非连通分量V5V4V0V2V3V16.1图的基本术语强连通分量V0V1V2V3V0V2V3V1非强连通图6.1图的基本术语8.邻接点（Adjacent）和相关边对于无向图G=（V，E），若（Vi，Vj）是E（G）中的一条边，则称顶点Vi和Vj互为邻接点，即Vi和Vj相邻接，而边（Vi，Vj）是与顶点Vi与Vj相关联的边。对于有向图G=（V，E），若Vi，Vj是E（G）中的一条边，则称顶点Vi邻接到顶点Vj，顶点Vj邻接于顶点Vi，而边Vi，Vj则是与顶点Vi和Vj相关联的边。6.1图的基本术语9.度（Degree）、入度（Indegree）和出度（Outdegree）所谓顶点的度，就是指和该顶点相关联的边数。在有向图中，以终止于该顶点的弧的数目称为该顶点的入度;以起始于该顶点的弧的数目称为该顶点的出度;某顶点的入度和出度之和称为该顶点的度。6.1图的基本术语顶点V0的度为顶点V1的度为顶点V0的入度为出度为度为顶点V1的入度为出度为度为顶点V2的入度为出度为度为6.1图的基本术语321，2，1，2，1，1，332提问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是树！而且是一棵有向树！6.1图的基本术语10.权和网（Net）在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权。边上带权的图称为带权图，也称为网。6.1图的基本术语练习1、在一个图中，所有顶点的度数之和等于所有边数的（）倍。A、1/2B、1C、2D、42、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A、1/2B、1C、2D、43、一个有n个顶点的无向图最多有（）条边。A、nB、n(n-1)C、n(n-1)/2D、2n4、具有4个顶点的无向完全图有（）条边。A、6B、12C、16D、20CBCA练习5、具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。A、5B、6C、7D、86、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。A、nB、n+1C、n-1D、n/2AC练习7、对于右图，分别求：（1）每个顶点的度。（2）给出一条从V0到V3的简单路径。【答案】（1）V0、V1、V2、V3的度均为3，V4的度为4（2）V0到V3的简单路径为（V0，V4，V3）V0V2V4V1V3练习8、对于右图，分别求：（1）每个顶点的入度、出度和度。（2）给出一条从V0到V3的简单路径。【答案】（1）V0的入度为2，出度为1，度为3；V1的入度为1，出度为3，度为4；V2的入度为2，出度为1，度为3；V3的入度为1，出度为2，度为3；V4的入度为1，出度为1，度为2；V5的入度为3，出度为2，度为5。（2）V0到V3的简单路径为（V0，V5，V1，V3）V0V2V5V4V3V16.2图的存储结构6.2.1邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵，可以用一个二维数组来表示。设G=（V，E）是具有n个顶点的图，顶点序号依次为0，1，2，…，n-1，则G的邻接矩阵是具有如下定义的n阶方阵:对于带权图（网）的邻接矩阵可以定义为:A[i][j]={1有边0不是边A[i][j]={Wi有边（Wi为权值）∞不是边6.2图的存储结构6.2.1邻接矩阵0110100110010110A1=v0v1v2v3∞1023∞6∞5∞A2=v0v1v2v3v0v1v2v0v1v2练习：写出以下带权图的邻接矩阵6.2图的存储结构v0v1v2v3Nv4v55489755613∞5∞7∞∞∞∞4∞∞∞8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞3∞∞∞1∞无向图的邻接矩阵是对称的有向图的邻接矩阵不一定对称对于无向图，顶点Vi的度是邻接矩阵中第i行（或第i列）的非零元素的个数对于有向图，顶点Vi的度是邻接矩阵中第i行和第i列的非零元素的个数之和;顶点Vi的出度是邻接矩阵中第i行的非零元素的个数;顶点Vi的入度是邻接矩阵中第i列的非零元素的个数。。6.2图的存储结构6.2.2邻接表邻接表是图的一种顺序和链式分配相结合的存储结构。在邻接表中，为图中每个顶点建立一个单链表。单链表中每个结点由两个域:顶点域（vertex）和链域（next）组成。6.2图的存储结构v0v1v2v4v4v3邻接表01234^1334^142^0v0v1v2v3v423^142^0v0邻接点v3的位置6.2图的存储结构练习：画出以下无向图的连接表6.2.3边集数组带权图（网）的另一种存储结构是边集数组，它适用于一些以边为主的操作。用边集数组表示带权图时，列出每条边所依附的两个顶点及边上的权，即每个数组元素代表一条边的信息。6.2图的存储结构beginvertexendvertexweight起始点终止点权练习1、请写出右图的邻接矩阵和邻接表。【答案】邻接矩阵：0110110011100110110111110V0V2V4V1V3邻接表：V0V4V3V2V10432114^2034^034^124^0123^练习2、请写出右图的邻接矩阵和邻接表。【答案】邻接矩阵：000001101100000001001001100000010010V0V2V5V4V3V1邻接表：V0V4V3V2V1043215^025^254^01V55^^3^3、写出以下网的边集数组存储表。起始点终止点权值12271519162123524626113410461456335718练习6.3图的遍历从图的任一顶点出发访问图中的各个顶点，并且使每个顶点仅被访问一次。这一过程叫做图的遍历。对图的遍历通常采用两种遍历次序，即深度优先搜索（DFS）和广度优先搜索（BFS）。6.3.1深度优先搜索（DFS）基本思想是:从图G的某个顶点V0出发，访问V0，然后选择一个与V0相邻且未被访问的顶点Vi访问，再从Vi出发选择一个与Vi相邻且未被访问的顶点Vj进行访问，依此继续。如果当前被访问的顶点的所有相邻顶点都已被访问，则退回到已被访问顶点序列中最后一个拥有未被访问的相邻顶点W，从W出发按同样方法向前遍历，直到图中所有顶点都被访问到为止。这种搜索方式类似于树的先序遍历。特点是尽可能向纵深方向进行搜索。6.3图的遍历深度优先生成树:由图中的全部顶点和深度优先搜索过程所经过的边集构成。注意：一个图的存储结构不同，其DFS序列可能不唯一。邻接表及初始出发点确定后，DFS唯一。邻接矩阵及源点确定后，DFS唯一。6.3图的遍历A图的邻接表如下：6.3图的遍历DFS序列：V0V2V3V1A图的邻接表如下：6.3图的遍历DFS序列：V0V1V2V3根据邻接矩阵存储结构，分别以V0和V6为起点得到DFS序列6.3图的遍历以V0为起点的DFS序列：V0V1V2V5V4V6V3V7以V6为起点的DFS序列：V6V3V0V1V2V5V4V76.3图的遍历练习：根据下图和它的邻接表，以V0为起点，给出DFS序列