数据结构-第7章图-课件

数据结构课程的内容数据结构课程的内容多对多多对多（m:n)2020/12/211.哥尼斯堡七桥问题哥尼斯堡七桥问题德国古城德国古城哥哥尼斯堡尼斯堡普雷格尔河普雷格尔河七七2.桥问题：从任一桥头出发，依次走过每桥问题：从任一桥头出发，依次走过每座座3.桥，每座桥只走一次，最后回到出发点。桥，每座桥只走一次，最后回到出发点。4.一笔画问一笔画问题题2020/12/22精品资料你怎么称呼老师？如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？你所经历的课堂，是讲座式还是讨论式？教师的教鞭“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘”“太阳当空照，花儿对我笑，小鸟说早早早”2020/12/252020/12/267.17.1 基本术语基本术语7.27.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性图的连通性7.5 7.5 图的应用图的应用第第7 7章章 图图2020/12/277.1 7.1 图的基本术语图的基本术语 其中：其中：V V 是是G G 的的顶点顶点集合，是有穷非空集；集合，是有穷非空集；E E 是是G G 的的边边集合，是有穷集。集合，是有穷集。问：当问：当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答：还存在！但此时图答：还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。有向图：有向图：无向图：无向图：完全图：完全图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；图图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；v若若n个顶点的无向图有个顶点的无向图有n(n-1)/2条边条边,称为称为无向完全图无向完全图v若若n个顶点的有向图有个顶点的有向图有n(n-1)条边条边,称为称为有向完全图有向完全图V=vertexE=edge图：图：记为记为 G(V,E)v1v2v3v5v4v4v1v2v3v4有向边有向边(u,v)称为称为弧弧，边的始点，边的始点u叫叫弧尾弧尾，终点，终点v叫叫弧弧头头。2020/12/28例：判断下列例：判断下列4种图形各属什么类型？种图形各属什么类型？无向无向无向图无向图(树树)有向图有向图有向有向n n(n n-1)/2-1)/2条边条边条边条边n n(n n-1)-1)条边条边条边条边G1G1的顶点集合为的顶点集合为V(G1)=0,1,2,3V(G1)=0,1,2,3边集合为边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全完全图图完全完全图图2020/12/29证明：证明：证明：证明：若是完全有向图，则若是完全有向图，则n个顶点中个顶点中的每个顶点都有一条弧指向其它的每个顶点都有一条弧指向其它n-1个个顶点顶点,因此总边数因此总边数=n(n-1)证明：证明：从从可以直接推论出无向完全图的可以直接推论出无向完全图的边数边数因为无方向，两弧合并为一边，因为无方向，两弧合并为一边，所以边数减半，总边数为所以边数减半，总边数为n(n-1)/2。完全无向图有完全无向图有完全无向图有完全无向图有n n(n n-1)/2-1)/2条边条边条边条边。完全有向图有完全有向图有完全有向图有完全有向图有n n(n n-1)-1)条边条边条边条边。123412342020/12/210稀疏图：稀疏图：稠密图：稠密图：设有两个图设有两个图G(V,E)和和G(V,E)。若。若V V 且且E E,则称则称图图G是是图图G的子图。的子图。子子图：图：边较少的图。通常边数远少于边较少的图。通常边数远少于nlognnlogn边很多的图。边很多的图。无向图中，边数接近无向图中，边数接近n n(n n-1)/2-1)/2 有向图中，边数接近有向图中，边数接近n n(n n-1)-1)2020/12/211带权图：带权图：即即边上带权的图边上带权的图。其中。其中权权是指每条边是指每条边可以标上具有某种含义的数值（即与可以标上具有某种含义的数值（即与边相关的数）。边相关的数）。连通图：连通图：在在无向无向图中图中,若从顶点若从顶点v v1 1到顶点到顶点v v2 2有有路径路径,则称顶点则称顶点v v1 1与与v v2 2是是连通连通的。如的。如果图中任意一对顶点都是连通的果图中任意一对顶点都是连通的,则称此图是则称此图是连通图连通图。非连通图的极大连通子图非连通图的极大连通子图叫做叫做连通连通分量分量。带权图带权图在在有向有向图中图中,若对于每一对顶点若对于每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和和从从vj到到vi的路的路径径,则称此图是则称此图是强连通图强连通图。强连通图：强连通图：网网：DEABCFJLMGHIK非强连通图的极大强连通子图非强连通图的极大强连通子图叫做叫做强连通分量强连通分量。2020/12/212生成树：生成树：是一个是一个是一个是一个极小连通子图极小连通子图极小连通子图极小连通子图，它含有图中，它含有图中，它含有图中，它含有图中全部全部全部全部n n个顶点，但只有个顶点，但只有个顶点，但只有个顶点，但只有n n-1-1条边条边条边条边。若干棵若干棵若干棵若干棵生成树的集生成树的集生成树的集生成树的集合合合合，含全部顶点，含全部顶点，含全部顶点，含全部顶点，但构成这些树的边但构成这些树的边但构成这些树的边但构成这些树的边或或或或弧弧弧弧是最少的。是最少的。是最少的。是最少的。有两类图形不在有两类图形不在本章讨论之列：本章讨论之列：图的基本术语图的基本术语图的基本术语图的基本术语(续续续续)v1v2v3v4v如果在生成树上如果在生成树上添加添加1条边条边，必定构成一个环。，必定构成一个环。v若图中有若图中有n个顶点，却个顶点，却少于少于n-1条边条边，必为非连通图。，必为非连通图。生成生成森林：森林：2020/12/213邻接点：邻接点：有向边有向边(u,v)称为称为弧弧，边的始点，边的始点u叫叫弧尾弧尾，终点终点v叫叫弧头弧头。顶点顶点v的的入度入度是以是以v为为终点终点的有向边的条数的有向边的条数,记作记作ID(v);顶点顶点v的的出度出度是以是以v为为始点始点的有向边的条数的有向边的条数,记作记作OD(v)。若若(u,v)是是E(G)中的一条边，则中的一条边，则称称u 与与v 互为互为邻接顶点。邻接顶点。弧头和弧头和弧尾：弧尾：入度和入度和出度：出度：问：当有向图中仅问：当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶点的入度均为其余顶点的入度均为1 1，此时是何形状？此时是何形状？uv度：度：顶点顶点v的的度度是与它相关联的边的条数。记作是与它相关联的边的条数。记作TD(v)。在在有向图有向图中中,顶点的顶点的度度等于该顶点的等于该顶点的入度入度与与出度出度之和。之和。U U U U 的入度的入度的入度的入度=?=?=?=?U U U U 的出度的出度的出度的出度=?=?=?=?答：是树！而且是一答：是树！而且是一棵有向树！棵有向树！2020/12/214简单路径：简单路径：路径上各顶点路径上各顶点 v v1 1,v,v2 2,.,v,.,vm m 均不互相重复。均不互相重复。回路：回路：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，重合，则称这样的路径为则称这样的路径为回路或环回路或环。路径：路径：在图在图在图在图GG(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 v vi i 出发出发出发出发,沿一些边经过一些顶沿一些边经过一些顶沿一些边经过一些顶沿一些边经过一些顶点点点点 v vp p1 1,v vp p2 2,v vpmpm，到达顶点，到达顶点，到达顶点，到达顶点v vj j。则称顶点序列。则称顶点序列。则称顶点序列。则称顶点序列(v vi i v vp p1 1 v vp p22.v vpm pm v vj j)为从顶点为从顶点为从顶点为从顶点v vi i 到顶点到顶点到顶点到顶点 v vj j 的的的的路径路径路径路径。它经过的。它经过的。它经过的。它经过的边边边边(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)应当是属于应当是属于应当是属于应当是属于E E的的的的边边边边。路径长路径长度：度：非带权图非带权图非带权图非带权图的的的的路径长度路径长度路径长度路径长度是指此路径上是指此路径上是指此路径上是指此路径上边的条数边的条数边的条数边的条数；带权图带权图带权图带权图的的的的路径长度路径长度路径长度路径长度是指路径上是指路径上是指路径上是指路径上各边的权之和各边的权之和各边的权之和各边的权之和。图的术语（续）图的术语（续）2020/12/215ADTGraph数据对象数据对象V：数据关系数据关系R：基本操作基本操作P：ADTGraph图的抽象数据类型图的抽象数据类型V V是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。R=VRR=VR；VR=VR=|v,wV|v,wV 且且 P(v,w)P(v,w),表示从表示从v v到到w w的弧，的弧，谓词谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息 CreatGraph(&G,V,VR);初始条件：初始条件：V V是图的是图的顶点集顶点集，VRVR是图中弧的集合。是图中弧的集合。操作结果：操作结果：按按V V和和VRVR的定义构造图的定义构造图G G。注意：注意：V V 的大小的大小写含义不同！写含义不同！InsertVex(&G,v);初始条件：初始条件：图图G G存在，存在，v v 和图中和图中顶点顶点有相同特征。有相同特征。操作结果：操作结果：在图在图G G中添加新顶点。中添加新顶点。（参见教材（参见教材P156-257P156-257）2020/12/2167.2 7.2 图的存储结构图的存储结构图的特点：图的特点：链式存储结构：链式存储结构：顺序存储结构：顺序存储结构：难！难！（多个顶点，无序可言，无法仅以顶点坐（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）标表达相互关系）可用可用多重链表多重链表1.1.邻接矩阵邻接矩阵(数组数组)表示法表示法2.2.邻接表邻接表(链式链式)表示法表示法3.十字链表十字链表表示法表示法4.邻接多重表邻接多重表表示法表示法但可但可用用数组数组描述元素间关系。描述元素间关系。非线性结构非线性结构（m:nm:n）邻接矩阵邻接矩阵邻接表邻接表十字链表十字链表邻接多重表邻接多重表各种表示法成立的原则：各种表示法成立的原则：存入电脑后能惟一复原存入电脑后能惟一复原2020/12/217 建立一个建立一个建立一个建立一个顶点表顶点表顶点表顶点表和一个和一个和一个和一个邻接矩阵邻接矩阵邻接矩阵邻接矩阵。1.1.邻接矩阵（数组）表示法邻接矩阵（数组）表示法邻接矩阵（数组）表示法邻接矩阵（数组）表示法例例例例1 1：邻接矩阵：邻接矩阵：A.Edge=（v1v2v3v4v5）v1v2v3v4v50101010101010111010101110分析分析分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是无向图的邻接矩阵是无向图的邻接矩阵是对称对称对称对称的；的；的；的；分析分析分析分析2 2：顶点顶点顶点顶点i i 的的的的度度度度第第第第 i i 行行行行(列列列列)中中中中1 1 的个数；的个数；的个数；的个数；特别：特别：特别：特别：完全图完全图完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余全，其余全，其余全，其余全1 1。顶点表：顶点表：无向图的邻接矩阵如何表示？无向图的邻接矩阵如何表示？v1v2v3v5v4v4A A记录各个顶点信息记录各个顶点信息表示各个顶点之间关系表示各个顶点之间关系 设图设图设图设图A=(A=(V V,E E)有有有有 n n 个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数组组组组 A A.Edge.Edge n n n n，定义为：，定义为：，定义为：，定义为：000000000000000000000000001010101010101110101011102020/12/218例例2：有向图的邻接矩阵如何表示？有向图的邻接矩阵如何表示？分析分析分析分析1 1 1 1：有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。分析分析分析分析2 2 2 2：顶点顶点v vi i的的出度出度=第第i i行元素之和行元素之和，OD(v vi i)=A.Edge i j 顶点顶点v vi i的的入度入度=第第i i列元素之和列元素之和。ID(v vi i)=A.Edge j i 顶点的顶点的度度=第第i i行元素之和行元素之和+第第i i列元素之和列元素之和,即：即：TD(v vi i )=OD(vi)+ID(vi)v1v2v3v4A A邻接矩阵：邻接矩阵：A.Edge=(v1v2v3v4)v1v2v3v40000000000000000注：注：注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中，第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧(即出度边）；即出度边）；第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧(即入度边）。即入度边）。顶点表：顶点表：011000000001100001100000000110002020/12/219 容易实现图的操作，如：求某顶点的度、判断顶容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。点之间是否有边（弧）、找顶点的邻接点等等。n n个顶点需要个顶点需要n*nn*nn*nn*n个单元存储边个单元存储边(弧弧););空间效率为空间效率为O O(n n2 2 2 2)。例例3：有权图（即有权图（即网络网络）的）的邻接矩阵邻接矩阵如何表示？如何表示？定义：定义：A.Edgeij=Wij或（或（vi,vj）VR无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：邻接矩阵：N.Edge=(v1v2v3v4v5v6)邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：顶点表：顶点表：57489565315748956531v1v2v3v4v5v6对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。2020/12/220注：用两个数组分别存储顶点表和邻接矩阵注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX/最大值最大值#defineMAX_VERTEX_NUM20/假设的最大顶点数假设的最大顶点数TypedefenumDG,DN,AG,ANGraphKind;/有向有向/无向图，有向无向图，有向/无向无向网网图的邻接矩阵在机内如何表示？图的邻接矩阵在机内如何表示？（参见教材（参见教材P161P161）对于对于n n个顶点的图或网，空间效率个顶点的图或网，空间效率=O(n=O(n2 2)TypedefstructArcCell/弧（边）弧（边）结点的定义结点的定义VRTypeadj;/顶点间关系，无权图取顶点间关系，无权图取1 1或或0 0；有权图取权值类型；有权图取权值类型InfoType*info;/该弧相关信息的指针该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;Typedefstruct/图的定义图的定义VertexTypevexsMAX_VERTEX_NUM;/顶点表，用一维向量即可顶点表，用一维向量即可(n n)AdjMatrixarcs;/邻接矩阵邻接矩阵n*nn*nIntVernum,arcnum;/顶点总数顶点总数n n，弧（边）总数，弧（边）总数e eGraphKindkind;/图的种类标志图的种类标志Mgraph;2020/12/221StatusCreateUDN(Mgraph&G)/无向网的构造，用邻接矩阵表示无向网的构造，用邻接矩阵表示scanf(&G.vexnum,&G.arcnum,&IncInfo);/输入总顶点数输入总顶点数n n、总弧数、总弧数e e和信息和信息for(i=0;iG.vexnum,;+i)scanf(&G.vexsi);/输入输入n n个顶点值个顶点值，存入一维向量，存入一维向量例：例：用邻接矩阵生成用邻接矩阵生成无向网无向网的算法的算法（参见教材（参见教材P162P162）对于对于n n个顶点个顶点e e条弧的网，条弧的网，建网时间效率建网时间效率=O(=O(n n+n n2 2+e*ne*n)for(i=0;iG.vexnum;+i)/对邻接矩阵对邻接矩阵n*nn*n个单元初始化，个单元初始化，adj=,info=NULLfor(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;for(k=0;kG.arcnum;+k)/给邻接矩阵有关单元赋初值给邻接矩阵有关单元赋初值(循环次数弧数循环次数弧数e escanf(&v1,&v2,&w);/输入弧的两顶点以及对应权值输入弧的两顶点以及对应权值i=LocateVex(G,v1);j=LocateVex(G,v2);/找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置(n n次次)G.arcsij.adj=w;/输入对应权值输入对应权值If(IncInfo)Input(*G.arcsij.info);/如果弧有信息则填入如果弧有信息则填入G.arcsij=G.arcsji；/无向网是对称矩阵无向网是对称矩阵returnOK;/CreateCreateUDN2020/12/2222.2.邻接表（链式）表示法邻接表（链式）表示法邻接表（链式）表示法邻接表（链式）表示法 对每个顶点对每个顶点对每个顶点对每个顶点v vi i建立一个建立一个建立一个建立一个单链表单链表单链表单链表，把与，把与，把与，把与v vi i有关联的有关联的有关联的有关联的边的信息边的信息边的信息边的信息（即（即（即（即度或出度边）度或出度边）度或出度边）度或出度边）链接链接链接链接起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为3 3个域个域个域个域:每个单链表还应当附设一个每个单链表还应当附设一个每个单链表还应当附设一个每个单链表还应当附设一个头结点头结点头结点头结点（设为（设为（设为（设为2 2个域），存个域），存个域），存个域），存v vi i信息；信息；信息；信息；adjvex nextarcinfodatafirstarc表结点表结点表结点表结点头结点头结点头结点头结点邻接点域邻接点域，表表示示v vi i 邻接点邻接点的位置的位置链域链域，指向指向下一个边或下一个边或弧的结点弧的结点数据域数据域，与与边有关信息边有关信息（如权值）（如权值）数据域数据域，存，存储顶点储顶点vi信信息息链域链域，指向指向单链表的第单链表的第一个结点一个结点 每个单链表的每个单链表的每个单链表的每个单链表的头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储结构存储。结构存储。结构存储。结构存储。2020/12/223例例1 1：无向图的邻接表如何表示？无向图的邻接表如何表示？v1v2v3v5v4v4邻邻接接表表0123413341420例例2 2：有向图的邻接表如何表示？有向图的邻接表如何表示？v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V4V3V2V13020逆邻接表逆邻接表(入边入边)请注意：邻接表不惟一！因各个边结点的链入顺序是任意的。请注意：邻接表不惟一！因各个边结点的链入顺序是任意的。v1v2v3v4v5231420v v1 1邻接点邻接点v v4 4的位置的位置此无权图未开第此无权图未开第3 3分量分量2020/12/224例例3 3：已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储当邻接表的存储结构形成后，图结构形成后，图便唯一确定！便唯一确定！2020/12/225分析分析1:对于对于n n个顶点个顶点e e条边的无向图条边的无向图，邻接表中除了，邻接表中除了n n个头结点个头结点外，只有外，只有2e2e个表结点个表结点,空间效率为空间效率为O(n+2e)O(n+2e)。若是稀疏图若是稀疏图(en(en2 2)，则比邻接矩阵表示法，则比邻接矩阵表示法O(nO(n2 2)省空间。省空间。邻接表存储法的特点：邻接表存储法的特点：分析分析2:在在有向图有向图中，邻接表中除了中，邻接表中除了n n个头结点外，只有个头结点外，只有e e个表结点个表结点,空间效率为空间效率为O(n+e)O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。若是稀疏图，则比邻接矩阵表示法合适。它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？怎样计算无向图顶点的度？邻接表的邻接表的缺点：缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点的入度？怎样计算有向图顶点怎样计算有向图顶点Vi的度：的度：需遍历全表需遍历全表邻接表的邻接表的优点：优点：TD(Vi)TD(Vi)=单链表中链接的结点个数单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数ID(Vi)邻接点为邻接点为ViVi的弧个数的弧个数TD(Vi)=OD(Vi)+I D(Vi)空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。结点对应的单链表，没有邻接矩阵方便。2020/12/226讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但号与顶点编号一致），但邻接表不唯一邻接表不唯一（链接次序（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2)2020/12/227图的邻接表在机内如何表示？图的邻接表在机内如何表示？（参见教材（参见教材P163P163）#defineMAX_VERTEX_NUM20/假设的最大顶点数假设的最大顶点数空间效率为空间效率为O(n+2e)O(n+2e)或或O(n+e)O(n+e)时间效率为时间效率为O(n+e*n)O(n+e*n)TypedefstructVNode/顶点结构顶点结构VertexTypedata;/顶点信息顶点信息ArcNode*firstarc;/指向依附该顶点的第一条弧的指针指向依附该顶点的第一条弧的指针VNode,AdjListMAX_VERTEX_NUM;Typedefstruct/图结构图结构AdjListvertics;/应包含邻接表应包含邻接表intvexnum,arcnum;/应包含顶点总数和弧总数应包含顶点总数和弧总数intkind;/还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph;TypedefstructArcNode/弧结构弧结构intadjvex;/该弧所指向的顶点位置该弧所指向的顶点位置structArcNode*nextarcs;/指向下一条弧的指针指向下一条弧的指针InfoArc*info;/该弧相关信息的指针该弧相关信息的指针ArcNode；图的邻接表图的邻接表生成算法作生成算法作为自测题为自测题2020/12/228它是它是有向图有向图的另一种链式结构。的另一种链式结构。思路：思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1、开设弧结点，弧结点，设设5 5个域个域（每段弧是一个数据元素）（每段弧是一个数据元素）2 2、开设、开设顶点结点，顶点结点，设设3 3个域个域（每个顶点也是一个数据元素）（每个顶点也是一个数据元素）tailvexheadvexhlinktlinkinfodata:顶点信息Firstin:以顶点为弧头的第一条弧结点Firstout:以顶点为弧尾的第一条弧结点dataFirstinFirstout顶点结点顶点结点弧结点弧结点3.3.十字链表表示法十字链表表示法十字链表表示法十字链表表示法tailvex:tailvex:弧尾顶点位置 headvex:headvex:弧头顶点位置hlink:hlink:弧头相同的下一弧位置tlink:tlink:弧尾相同的下一弧位置info:info:弧信息n个顶点的集合怎样储存？个顶点的集合怎样储存？仍用顺序存储结构仍用顺序存储结构2020/12/229v1v2v3v42 0233031例：画出有向图的十字链表。例：画出有向图的十字链表。十字链表优点：十字链表优点：容易操作，如求顶点的入度、出度等。容易操作，如求顶点的入度、出度等。FirstoutFirstindata顶点结点顶点结点infotlinkhlinkheadvextailvex弧结点弧结点0v11v22v33v401230 102此无权图未开第此无权图未开第4 4分量分量空间复杂度和建表的时间复杂度都与邻接表相同空间复杂度和建表的时间复杂度都与邻接表相同。2020/12/230#defineMAX_VERTEX_NUM20十字链表存储结构描述：十字链表存储结构描述：TypedefstructArcBox/弧结点结构，弧结点结构，5 5分量分量inttailvex,headvex;structArcBox*hlink,tlink;InfoType*info;ArcBox;TypedefstructVexNode/顶点结构顶点结构,3,3分量分量VertexTypedata;ArcBox*firstin,*firstout;VexNode;Typedefstruct/图结构图结构,整体概念整体概念VexNodexlistMAX_VERTEX_NUM;/表头向量表头向量intvexnum,arcnum;OLGraph;2020/12/231这是这是无向图无向图的另一种存储结构，当的另一种存储结构，当对边操作对边操作时建议采用此种结构存储。时建议采用此种结构存储。1、设立、设立边结点，边结点，6个域个域（每条边是一个数据元素）（每条边是一个数据元素）2、设立、设立顶点结点，顶点结点，2个域个域（每个顶点也是一个数据元素）（每个顶点也是一个数据元素）markivexilinkjvexjlinkinfo边结点边结点data:存储顶点信息存储顶点信息Firstedge:依附顶点的第一条依附顶点的第一条边结点边结点dataFirstedge顶点结点顶点结点4.4.邻接多重表表示法邻接多重表表示法邻接多重表表示法邻接多重表表示法mark：标志域标志域ivex，jvex:边依附的两个顶点位置边依附的两个顶点位置ilink:指向下一条依附顶点指向下一条依附顶点i的边位置的边位置jlink;指向下一条依附顶点指向下一条依附顶点j的边位置的边位置info:边信息边信息n个顶点的集合怎样储存？个顶点的集合怎样储存？仍用顺序存储结构仍用顺序存储结构2020/12/232121 4232 43 4 v1v2v3v5v4v4例：画出无向图的邻接多重表例：画出无向图的邻接多重表邻接多重表优点：邻接多重表优点：容易操作，如求顶点的度等。容易操作，如求顶点的度等。0v11v22v33v44v501234Firstedgedata顶点结点顶点结点markinfojlinkjvexilinkivex边结点边结点空间复杂度和建表的时间复杂度都与邻接表相同。空间复杂度和建表的时间复杂度都与邻接表相同。0103此无权此无权图未开图未开第第6 6分量分量2020/12/233一、深度优先搜索二、广度优先搜索 7.3图的遍历图的遍历遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历图的遍历图的遍历，它是它是图的图的基本运算基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路回路，且图的任一顶点都可能与其它，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点到了曾经访问过的顶点。解决思路：解决思路：可设置一个辅助数组可设置一个辅助数组 visitedn，用来标记每个被，用来标记每个被访问过的顶点。它的初始状态为访问过的顶点。它的初始状态为0 0，在图的遍历过程中，在图的遍历过程中，一旦某一个顶点一旦某一个顶点i 被访问，就立即改被访问，就立即改 visitedi为为1 1，防止它，防止它被多次访问。被多次访问。图常用的遍历：图常用的遍历：怎样避免重复访问怎样避免重复访问？2020/12/234一、深度优先搜索一、深度优先搜索一、深度优先搜索一、深度优先搜索(DFSDFSDFSDFS )基本思想：基本思想：仿树的先序遍历过程仿树的先序遍历过程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFSDFS结果结果结果结果例例例例1 1 1 1：v2v4v8v5v3v6v7例例例例2 2 2 2：v2v1v3v5v2v1v3v5DFSDFS结果结果结果结果v4v4v6v6起点起点起点起点遍历步骤遍历步骤应退回到应退回到V8V8，因为，因为V2V2已有标记已有标记2020/12/235深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点v 后，由后，由v 出发，访问出发，访问它的任一邻接它的任一邻接顶点顶点w1；E再从再从w1出发，访问出发，访问与与w1邻接邻接但还但还未被访问未被访问过的顶点过的顶点w2；E然后再从然后再从w2出发，进行类似的访问，出发，进行类似的访问，E如此进行下去，直至到达所有的邻接顶点都被访问过的顶点如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u 为止。为止。E接着，退回一步，接着，退回一步，退到前一次刚访问过的顶点退到前一次刚访问过的顶点，看是否还有其，看是否还有其它未被访问的邻接顶点。它未被访问的邻接顶点。如果有，如果有，则访问此顶点，之后再从此顶点出发，进行与前述类则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；似的访问；如果没有，如果没有，就就再退回一步再退回一步进行搜索。重复上述过程，直到连通进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。图中所有顶点都被访问过为止。简单归纳：简单归纳：访问起始点访问起始点v;若若v的第的第1个邻接点没访问过，深度遍历此邻接点；个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v的第的第2个邻接点重新遍历。个邻接点重新遍历。2020/12/236讨论讨论讨论讨论1 1：计算机如何实现计算机如何实现计算机如何实现计算机如何实现DFSDFS？1 2345610 000002 20 0000030 0000040 0000050 0000060 0000000000012345601000011 100001 11 110001 11 11 10101 11 11 111 101 11 11 11 11 11DFSDFS结果结果结果结果邻邻接接矩矩阵阵A辅助数组辅助数组 visitedn起点起点开辅助数组开辅助数组 visitedn！例：例：1 23 456101 11 11 1002 21 1 00 01 1031 1 00 01 1041 1 00 001 1501 11 1 00060 001 100v2v1v3v5v4v6请注意逐级回退是递归概念请注意逐级回退是递归概念2020/12/237for(j=1;jlinkp-link)/当存在起点的第一个邻接点时当存在起点的第一个邻接点时 p=p-link;p=p-link;v=p-data;v=p-data;if(!visitedv)DFS(List,v,p);if(!visitedv)DFS(List,v,p);/进行递归进行递归 return;return;2020/12/240DFSDFS算法效率分析算法效率分析算法效率分析算法效率分析:（设图中有设图中有设图中有设图中有 n n 个顶点，个顶点，个顶点，个顶点，e e 条边条边条边条边）n如果用如果用邻接矩阵邻接矩阵来表示图，遍历图中每一个顶点来表示图，遍历图中每一个顶点都要都要从头扫描从头扫描该顶点所在行，因此遍历全部顶点该顶点所在行，因此遍历全部顶点所需的时间为所需的时间为O(n2)。n如果用如果用邻接表邻接表来表示图，虽然有来表示图，虽然有2e 个表结点，但个表结点，但只需扫描只需扫描e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问n个个头结点的时间，因此遍历图的时间复杂度为头结点的时间，因此遍历图的时间复杂度为O(n+e)。结结论：论：稠密图稠密图适于在邻接矩阵上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。2020/12/241二、广度优先搜索二、广度优先搜索二、广度优先搜索二、广度优先搜索(BFSBFSBFSBFS )基本思想：基本思想：仿树的层次遍历过程。仿树的层次遍历过程。Breadth_FirstSearchv1v1v2v3v8v7v6v4v5BFSBFS结果结果结果结果例例例例1 1 1 1：v2v3v4v5v6v7v8例例例例2 2 2 2：v3v3BFSBFS结果结果结果结果v4v4 v5v5起点起点遍历步骤遍历步骤起点起点v2v1v6v2v1v6v9v8v7v9v8v72020/12/242广度优先搜索（遍历）步骤：广度优先搜索（遍历）步骤：简单归纳：简单归纳：在访问了起始点在访问了起始点v之后，依次访问之后，依次访问v的邻接点；的邻接点；然后再依次然后再依次（顺序）（顺序）访问这些点访问这些点（下一层）（下一层）中未被中未被访问过的邻接点；访问过的邻接点；直到所有顶点都被访问过为止。直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回步可能访问一批顶点，不像深度优先搜索那样有回退的情况。退的情况。因此，广度优先搜索不是一个递归的过程，其算法因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。也不是递归的。2020/12/243讨论讨论1：计算机如何实现计算机如何实现BFS？邻接表邻接表宽度优先搜索要借助队列！宽度优先搜索要借助队列！例：例：起点起点辅助队列辅助队列v2已访问过了已访问过了V2入队入队visitedn仍需要仍需要BFSBFS遍历结果遍历结果遍历结果遍历结果2020/12/244while(rear!=front)/队不空时队不空时front=(front+1)%n;v=qfront;/访问过的顶点出队访问过的顶点出队p=Listv.firstarc;/P/P指向第指向第1 1个邻接点个邻接点while(!p)if(!Visitedadjvex(p)/未到表尾，且邻接域未访问过，未到表尾，且邻接域未访问过，Visit(adjvex(p);Visitedadjvex(p)=1;/则先输出再改标记，则先输出再改标记，rear=(rear+1)%n;qrear=adjvex(p)/最后再入队最后再入队p=nextarc(p);/指向单链表中下一个邻接点指向单链表中下一个邻接点return/BFS1/BFS1讨论讨论2：BFS算法如何编程？算法如何编程？BFS1(List,n,v)/List/List为邻接表，为邻接表，v v为起点，为起点，QnQn为辅助队列为辅助队列Visit(v);Visitedv=1;/访问（例如打印）顶点访问（例如打印）顶点v v并修改标志并修改标志 层次遍历应当用队列！层次遍历应当用队列！（教材上（教材上BFSBFS算法见算法见P170P170）front=n-1;rear=0;/队列指针初始化队列指针初始化qrear=v;/起始点入队起始点入队2020/12/245BFSBFS算法效率分析算法效率分析算法效率分析算法效率分析:DFSDFS与与与与BFSBFS之比较：之比较：之比较：之比较：空间复杂度相同，都是空间复杂度相同，都是O(n)O(n)(借用堆栈或队列装借用堆栈或队列装n n个顶点）；个顶点）；时间复杂度只与存储结构时间复杂度只与存储结构（邻接矩阵或邻接表）（邻接矩阵或邻接表）有关，而有关，而与搜索路径无关。与搜索路径无关。如果使用邻接表来表示图，则如果使用邻接表来表示图，则BFS循环的总时间代价为循环的总时间代价为d0+d1+dn-1=O(e)，其中的，其中的di 是顶点是顶点i 的度。的度。如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（都要循环检测矩阵中的整整一行（n 个元素），总的个元素），总的时间代价为时间代价为O(n2)。（设图中有设图中有设图中有设图中有 n n 个顶点，个顶点，个顶点，个顶点，e e 条边条边条边条边）2020/12/2467.4 7.4 图的连通性问题图的连通性问题1.求图的生成树求图的生成树2.求最小生成树求最小生成树2020/12/2471.1.求图的生成树（或生成森林）求图的生成树（或生成森林）求图的生成树（或生成森林）求图的生成树（或生成森林）生成树：生成树：是一个极小连通子图，它含有图中全部顶点，但只有是一个极小连通子图，它含有图中全部顶点，但只有n-1n-1条边。条边。生成森林：生成森林：由若干棵由若干棵生成树生成树组成，含全部顶点，但构成这些树组成，含全部顶点，但构成这些树的边是最少的。的边是最少的。思考1：若对连通图进行遍历，得到的是什么？得到的将是一个极小连通子图，即图的得到的将是一个极小连通子图，即图的生成树生成树！由深度优先搜索得到的生成树，称为由深度优先搜索得到的生成树，称为深度优先搜索生成树深度优先搜索生成树。由广度优先搜索得到的生成树，称为由广度优先搜索得到的生成树，称为广度优先搜索生成树广度优先搜索生成树。思考2：若对非连通图进行遍历，得到的是什么？得到的将是各连通分量的生成树，即图的得到的将是各连通分量的生成树，即图的生成森林生成森林！2020/12/248例例1：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4无向连通图无向连通图2020/12/249其实由邻接矩阵或邻接表其实由邻接矩阵或邻接表也能直接画出生成森林也能直接画出生成森林DEABCFJLMGHIK例例2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）求解步骤：求解步骤：Step1:Step1:先求出邻接矩阵或邻接表；先求出邻接矩阵或邻接表；Step2:Step2:写出写出DFSDFS或或BFSBFS结果序列；结果序列；Step3:Step3:画出对应子图或生成森林。画出对应子图或生成森林。这是一个无向非连通图这是一个无向非连通图（参（参见教材见教材P170-171P170-171例）例）下面选用下面选用邻接表邻接表方式来求方式来求深度深度优先搜索生成森林优先搜索生成森林生成森林的定义生成森林的定义（对有向或无向图（对有向或无向图均适用）：是若干棵均适用）：是若干棵生成树的集合生成树的集合，含全部顶点，但构成这些树的边或含全部顶点，但构成这些树的边或弧弧是最少的。是最少的。2020/12/250115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子图子图1：再写出再写出DFS结果结果ABMJLCFDEGHKIABCFJLM先写出邻接表（或邻接矩阵）：先写出邻接表（或邻接矩阵）：子图子图2：子图子图3：最小连通！最小连通！怎样找怎样找3 3个根个根？2020/12/251DEGHIK子图子图(或连通分量或连通分量)ABCFJLMABCFJLMDEGHIK生生成成森森林林2020/12/2522.2.求最小生成树求最小生成树首先明确：首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树肯定的生成树肯定有有 n n 个顶点个顶点和仅仅和仅仅n-n-1 1 条边条边。即有权图即有权图构造最小生成树的准则构造最小生成树的准则v必须只使用该网络中的必须只使用该网络中的边边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n n-1-1条边条边来联结网络中的来联结网络中的n n个顶点；个顶点；v不能使用产生回路的边。不能使用产生回路的边。目标：目标：在网络的多个生成树中，寻找一个在网络的多个生成树中，寻找一个各边权值之和各边权值之和最小最小的生成树。的生成树。2020/12/253欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条线路；但因为条线路；但因为每条线路都会有对应的经济成本，而每条线路都会有对应的经济成本，而n n个城市可能有个城市可能有n(n-1)/2 n(n-1)/2 条线路，那么，如何选择条线路，那么，如何选择n1n1条线路使总费用最少？条线路使总费用最少？典型用途：典型用途：先建立数学模型：先建立数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n1n1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间的通信网。个城市间的通信网。显然此连通网是显然此连通网是一棵一棵生成树！生成树！问题抽象：问题抽象：n个顶点的生成树很多，需要从中选一棵个顶点的生成树很多，需要从中选一棵代价最小代价最小的生成树，即该树的生成树，即该树各边的代价之和各边的代价之和最小。此树便称为最小生最小。此树便称为最小生成树成树MST。MinimumcostSpanningTree2020/12/254讨论：如何求得最小生成树？讨论：如何求得最小生成树？最小生成树（最小生成树（最小生成树（最小生成树（MSTMST）的）的）的）的 性质如下：性质如下：性质如下：性质如下：若若U集是集是V的一个非空子集，若的一个非空子集，若(u0,v0)是一条是一条最小权值的边最小权值的边，其中其中u0 U，v0 V-U；则：；则：(u0,v0)必在最小生成树上。必在最小生成树上。设想一下：设想一下：设想一下：设想一下：先把权值最小的边归入生成先把权值最小的边归入生成树内，逐个递增，舍去回路边，则得到树内，逐个递增，舍去回路边，则得到的很可能就是最小生成树！的很可能就是最小生成树！求求MST有多种算法，但最常用的是以下两种：有多种算法，但最常用的是以下两种：vKruskal（克鲁斯卡尔克鲁斯卡尔）算法）算法vPrim（普里姆普里姆）算法）算法KruskalKruskal算法特点：将边归并算法特点：将边归并，适于求，适于求稀疏网稀疏网的最小生成树。的最小生成树。PrimePrime算法特点算法特点:将顶点归并将顶点归并，与边数无关，适于，与边数无关，适于稠密网稠密网。2020/12/255KruskalKruskal算法算法示例：示例：对边操作，归并边对边操作，归并边1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 21 15 54 43 32 21 13 35 52 24 46 6KruskalKruskal算法效率分析：算法效率分析：KruskalKruskal算法的时间效率算法的时间效率O O（elogelog2 2e e）KruskalKruskal算法算法是归并边，适用于稀疏图是归并边，适用于稀疏图（用邻接表）（用邻接表）56普利姆（普利姆（PrimPrim）算法）算法示例：示例：归并顶点归并顶点1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 23 36 64 42 25 51 1PrimPrim算法效率分析：算法效率分析：PrimPrim算法的时间效率算法的时间效率O O（n n2 2）PrimPrim算法算法是归并顶点，适用于稠密网。是归并顶点，适用于稠密网。2020/12/257图5-4-5构造最小生成树过程中辅助数组中各分量的值图图5-4-5 构造最小生成树过程中辅助数组中各分量的值构造最小生成树过程中辅助数组中各分量的值2020/12/2587.5有向无环图及其应用1.拓扑排序拓扑排序2.求关键路径求关键路径2020/12/2591拓扑排序拓扑排序在工程实践中，一个工程项目往往由若干个子项目在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：组成，这些子项目间往往有多种关系：先后关系，即必须在一子项目完成后，才能开先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；始实施另一个子项目；子项目之间无次序要求，即两个子项目可以同子项目之间无次序要求，即两个子项目可以同时进行，互不影响。时进行，互不影响。在工厂中，一件设备的生产包括许多工序，各工序在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。程必须在一些课程学完后才能开始学。2020/12/260这些类似的问题都可以用有向图来表示，我们把这这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为些子项目、工序、课程看成一个个顶点称之为活动活动(Activity)。如果从顶点如果从顶点Vi到到Vj之间存在有向边之间存在有向边,则表则表示活动示活动i必须先于活动必须先于活动j进行。这种图称做顶点表示进行。这种图