数据结构与算法第六章清华大学出版社赵玉兰

第6章图6.1图的基本概念6.2图的存储结构6.3图的遍历6.4无向图的应用6.5有向图的应用6.6最短路径数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第1页!6.1图的基本概念图图是由顶点集合V及顶点间的关系集合E所组成的一种数据结构：

Graph＝<V,E>其中：

V={x|x某个数据对象}是非空的有限顶点集合；

E={(x,y)|x,yV}//边(Edge)的集合或E={<x,y>|x,yV}//弧(Arc)的集合是顶点之间关系的有限集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第2页!6.1图的基本概念无向图无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集；E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 有向图有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集；E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾(或始点)，w为弧头(终点)，<v,w>≠<w,v>。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第3页!6.1图的基本概念例无向图G1V(G1)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}有向图G2V(G2)={1,2,3,4,5,6}E(G2)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}245136G2157324G16数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第4页!6.1图的基本概念——图的术语邻接点（或相邻点，关联）如果e=(u,v)是E(G)中的一条边，则称u与v互为邻接点或相邻点；称边e与顶点u,v关联；如果a=<u,v>是E(G)中的一条弧，则称u邻接到v或v邻接于u；称弧a与顶点u,v关联。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第5页!在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第6页!6.1图的基本概念——图的术语顶点的度（与树中结点的度不同）无向图中，顶点的度是与每个顶点关联的边数，记作TD(v)。有向图中，顶点的度分成入度与出度入度：以该顶点为终头的弧的数目，记为ID(v)出度：以该顶点为始点的弧的数目，记为OD(v)一个顶点的度等于该顶点的入度与出度之和，即TD(v)=OD(v)+ID(v)数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第7页!6.1图的基本概念——图的术语简单图图中不含有自环和多重边（或弧）的图称为简单图，否则称为非简单图。本章只讨论简单图，即有两类图形不在本章讨论之列数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第8页!6.1图的基本概念——图的术语路径在图G中，顶点序列(vi1,vi2,…,vim)且(vij,vij+1)E或<vij,vij+1>E，j=1,2,…,m-1，则称此序列为从顶点vi1到顶点vim的一条路径。顶点vi1称为始点；顶点vim

称为终点。回路始点和终点相同的路径。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第9页!6.1图的基本概念——图的术语路径长度无权图的路径长度是指此路径上边（或弧）的条数。带权图的路径长度是指路径上各边（或弧）的权之和。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第10页!6.1图的基本概念——图的术语连通图在无向图中，

若从顶点v1到顶点v2有路径，则称顶点v1与v2是连通的。图中任意两个顶点都连通的无向图称为连通图。连通分量非连通图中极大连通子图称做连通分量。1.含有极大顶点数；2.依附于这些顶点的所有边。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第11页!6.1图的基本概念——图的术语强连通图与强连通分量在有向图中，若对于每一对顶点vi

和vj，都存在一条从vi到vj和从vj到vi的有向路径，则称此图是强连通图。非强连通图的极大强连通子图称做强连通分量。V1V2V3V4V1V3V4V22个强连通分量

数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第12页!6.1图的基本概念——图的术语生成森林由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。FGIJLK生成森林ABCDEFGIJLHMK无向图GABCDEHM数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第13页!6.2图的存储结构邻接矩阵（AdjacencyMatrix）在图的邻接矩阵表示中有一个记录各个顶点信息的顶点表（一维数组）还有一个表示各个顶点之间邻接关系的邻接矩阵设图G=(V,E)是一个有n个顶点的图，则G的邻接矩阵定义如下A[i][j]=1若(vi,vj)∈E或<vi,vj>∈E0反之数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第14页!6.2图的存储结构例，有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第15页!6.2图的存储结构带权图的邻接矩阵A[i][j]＝0i=j∞其它

wij

若(vi,vj)∈E或<vi,vj>∈E数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第16页!6.2图的存储结构classAdjGraph{

AdjMatrix*adj； DataType*elem；public: AdjGraph(intm){

adj=newAdjMatrix(m)；

elm=newDataSet(m)；} voidCreateGraph();//建立一个图G的邻接矩阵Matrix

intLocateVex(v);//确定图G中顶点v在顶点中的位置 DataTypeGetVex(v);//得到图G中顶点v的值

intFirstAdjVex(v);//确定图G中顶点v的个邻接点

intNextAdjVex(v,w);//确定图G中顶点v相对于w的下一个邻接点

voidDFSTraverse(intv)；//图的深度优先遍历

voidBFSTraverse(intv)；//图的广度优先遍历};//AdjGraph 数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第17页!6.2图的存储结构邻接表（AdjacencyList）表示法无向图的邻接表为每个顶点建立一个单链表第i个单链表中的结点表示与顶点vi

所关联的所有边注：邻接表不唯一，因各个边结点的链入顺序是任意的。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第18页!6.2图的存储结构有向图的邻接表和逆邻接表在有向图的邻接表中，第i个单链表链接的弧都是顶点vi发出的，也称做出边表。在有向图的逆邻接表中，第i个单链表链接的弧都是进入顶点vi

的，也称做入边表。v1v2v3v4V4V3^V2V12^3^0^1V4V3V2V1^3^0^2^0邻接表逆邻接表01230123用邻接表或逆邻接表表示有向图时，只需n个顶点结点，e个弧结点。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第19页!6.2图的存储结构网（带权图）的邻接表边/弧结点adjvexcostlink数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第20页!6.2图的存储结构classLinkGraph{//邻接表

intn；//顶点的个数VNodeghead[MaxSize]；//邻接表public: LinkGraph(intm){n=m；} voidCreateGraph()；//建立图g intLocateVex(v)；//得到顶点v在图中的序号

DataTypeGetVex(v)；//得到顶点v的值

intFirstAdjVex(v)；//得到顶点v的个邻接顶点intNextAdjVex(v,w);//确定图G中顶点v相对于w的下一个邻接点voidDFSTraverse(intv)；//图的深度优先遍历voidBFSTraverse(intv)；//图的广度优先遍历};//LinkGraph数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第21页!6.2图的存储结构讨论：邻接表与邻接矩阵的比较联系都可以用来存储有向图和无向图；邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第22页!6.3图的遍历图的遍历从图中某一顶点出发，按照某种搜索路径访问图中所有的顶点，使得每个顶点被访问一次且仅被访问一次。图的遍历操作要解决的关键问题在图中，如何选取遍历的起始顶点？解决方案：从编号小的顶点开始数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第23页!6.3图的遍历深度优先遍历DFS（DepthFirstSearch）DFS算法思想从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至V0的所有邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第24页!6.3图的遍历从访问图中某一起始点v开始，由v出发，访问它的邻接点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直到某一顶点所有的邻接点都被访问完。退回到上一步刚访问过的顶点，看是否还有其它没有被访问的邻接点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第25页!6.3图的遍历例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归递归返回

V1遍历序列：V1V2

V2V4

V4V5

V5数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第26页!6.3图的遍历例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归递归返回

V1遍历序列：V1V2

V2V4

V4V5V8数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第27页!6.3图的遍历不同存储结构下的DFS实现图以邻接矩阵存储voidDFS(intv){

visited[v]=1;

visit(v);

for(w=0;w<n;w++) if(A[v][w]>0) if(!visited[w])DFS(w);}//DFS图以邻接表存储voidDFS(intv){visited[v]=1;p=ghead[v]->firstout;while(p){w=p->adjvex;

if(!visited[w])DFS(w);

p=p->link;} }//DFS数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第28页!6.3图的遍历算法分析图中有n个顶点，e条边。如果用邻接矩阵存储图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。如果用邻接表存储图，在每一个单链表中可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点(无向图)，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第29页!6.3图的遍历例

广度优先搜索过程广度优先生成树数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第30页!6.3图的遍历算法思想1）清队列Q；2）对出发顶点v做v入队；标记v；3）当Q不空反复做：出队头元素到u；访问u；将u的每个未被访问的邻接点w入队；标记w。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第31页!6.3图的遍历BFS从出发点只能遍历一个连通分量，若对任意图的遍历需要对每个分量中一个未被访问的顶点为出发点进行BFS遍历。voidBFSTraverse(){//广度优先求图的连通分量

intvisited[n]；//设置访问标志数组for(v=0；v<n；v++)visited[v]=0；//初始化访问标志

for(v=0；v<n；v++)if(!visited[v])BFS(v)；}//BFSTraverse数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第32页!6.3图的遍历算法分析如果用邻接矩阵存储图，则对于每一个被访问过的顶点，循环要检测矩阵中的n个元素，总的时间代价为O(n2)。如果用邻接表存储图，则循环的总时间代价为D0+D1+…+Dn-1=O(e)，其中的Di

是顶点i的度。而且对所有顶点访问1次，所以遍历图的时间复杂性为O(n+e)。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第33页!6.4无向图的应用——最小生成树生成树包含连通无向图中全部顶点的极小连通子图（n个顶点、n-1条边）一个连通图的生成树不唯一使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树对于非连通图，通过图的遍历，得到的是生成森林数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第34页!6.4无向图的应用——最小生成树最小生成树MST（Minimum-costSpanningTree）连通无向网中边权之和最小的生成树最小生成树MST的典型用途假设在7个城市之间要建立通信网络线，要求使得每个城市之间连通且费用最少。数学模型连通网——表示7个城市间的通信网顶点——表示城市边———表示城市间的通信线路边的权值—表示线路的经济代价2812345671016141812252422数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第35页!6.4无向图的应用——最小生成树最小生成树的性质若集合U是集合V的一个非空子集，若(u,v)是一条具有最小权值的边，其中uU，vV-U；则：(u,v)必在最小生成树上。UV-U数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第36页!6.4无向图的应用——最小生成树例0126345281612222510251418T={}U={0}Min{10,28}=10(0,5),5Min{25,28}=25,(5,4),4Min{28,25,22}=22,(4,3),3Min{28,25,18,12}=12,(3,2),2Min{28,25,18,16}=16,(2,1),1Min{25,18,14}=14,(1,6),6

U=V，算法结束数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第37页!6.4无向图的应用——最小生成树从顶点0出发利用Prim算法构造最小生成树过程中辅助数组各分量的值的变化i123456closedgeadjvexlowcost0280∞0∞0∞0100∞525422424312318216i123456edgeadjvexlowcost1140123456U1000000525010114221312121611141数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第38页!6.4无向图的应用——最小生成树closedge[v].lowcost=G.matrix[u][v];}for(t=1；t<n；t++){//选择其余的n-1个顶点

k=minimum(closedge)；//

求出T的下一个顶点k顶点

u=closedge[k].adjvex；

edge[k].lowcost=G.matrix[k][u];//保存选中边的权值

edge[k].adjvex=u;//保存选中边的顶点

U[k]=1；

for(j=0；j<n；j++) if(U[j]==0&&closedge[j].lowcost>G.matrix[k][j]){ closedge[j].lowcost=G.matrix[k][j]；

closedge[j].adjvex=k；} }//for }//MinSpanTree_Prim数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第39页!6.4无向图的应用——最小生成树Kruscal算法基本思想

先构造一个只含n个顶点、不含有边的零图T，然后从权值最小的边开始，若它的添加不使T产生回路，则在T上加上这条边，如此重复，直至加上n-1条边为止。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第40页!6.4无向图的应用——最小生成树算法思想设无向连通图G=(V,E)的最小生成树为T=(U,TE)1）初始化：U=V；TE={}；2）循环直到T中的连通分量个数为1在E中寻找最短边(u,v)；如果顶点u、v位于T的两个不同的连通分量，则将边(u,v)并入TE，并将这两个连通分量合为一个；在E中标记边(u,v)，使之不参加后续最短边的选取。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第41页!6.5有向图的应用例，学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求有先修课程，有些则不要求。C1 高等数学C2 计算机基础C3 离散数学 C1,C2

C4 数据结构 C3,C2C5 高级语言程序设计 C2C6 编译原理 C5,C4C7 操作系统 C4,C9C8 普通物理 C1C9 计算机原理 C8

课程代号课程名称先修课程数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第42页!6.5有向图的应用——拓扑排序AOV网用顶点表示活动，用弧表示活动间的优先关系的有向图，称为顶点表示活动的网（ActivityOnVertices）若<vi,vj>是图中的有向边，则表示活动vi必须先于活动vj

进行AOV网中不允许有回路，这意味着某项活动不能以自己为先决条件数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第43页!6.5有向图的应用——拓扑排序由给定的AOV网所描述的工程是否可行？检测方法：拓扑排序对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在回路，工程可行。相反，如果得不到满足要求的拓扑有序序列，则说明AOV网中存在有向回路，此AOV网所代表的工程是不可行的。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第44页!6.5有向图的应用——拓扑排序例，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为

C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6

拓扑序列并不唯一数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第45页!6.5有向图的应用——拓扑排序拓扑排序的思想输入一个AOV网，令n为顶点个数。 (1)在AOV网中选一个没有前驱的顶点，并输出之。(2)从图中删去该顶点，同时删去与该顶点关联的弧。(3)重复以上(1)、(2)步，直到全部顶点均已输出，拓扑序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网中一定存在有向回路。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第46页!6.5有向图的应用——拓扑排序拓扑排序的算法思想图的存储：邻接表增设一个数组indegree[]，记录各个顶点的入度在输入数据时，每输入一条弧<j,k>，就需要建立一个弧结点，将它链入相应弧链表中，并统计入度信息EArcNode*p=newEArcNode(k);p→link=ghead[j].firstout;ghead[j].firstout=p;indegree[k]++; //顶点k入度加1数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第47页!6.5有向图的应用——拓扑排序拓扑排序的算法boolTopologicalSort(){FindInDegree(indegree)；

top=-1;for(i=0；i<n；i++)if(!indegree[i]){indegree[i]=top；top=i;};count=0；数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第48页!6.5有向图的应用——拓扑排序例数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第49页!6.5有向图的应用——关健路径AOE网在没有回路的有向网中，如果用顶点表示事件（Event）

用弧表示一个工程中的各项活动（Activity）用弧上的权值表示活动的持续时间（Duration）则称这样的有向图为用弧表示活动的网（Activity

onEdge）数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第50页!6.5有向图的应用——关健路径AOE网在某些工程预算方面非常有用，它可以使人们了解到完成整个工程最短需要多少时间（假设网中没有有向回路）？为缩短完成工程所需的时间，应当加快哪些活动？数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第51页!6.5有向图的应用——关健路径问题2——为缩短工期，应当加快哪些活动？要找出关键路径，必须找出关键活动，只有提高关键活动的功效，才可能缩短整个工期。关键路径为：

(v0,v1,v4,v6,v8

)或(v0,v1,v4,v7,v8

)关键路径的长度为：18关键活动为：a1,a4,a7,a10,a8,a11数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第52页!6.5有向图的应用——关健路径ee(i)——事件vi

的最早发生时间从始点v0

到顶点vi

的最长路径长度le(i)——事件vi

的最晚发生时间在保证终点vn-1

在le(n-1)时刻完成的前提下，事件vi

的最晚发生时间P(j)表示以顶点vj

为弧头的所有弧的尾顶点集合S(j)表示以顶点vj

为弧尾的所有弧的头顶点集合数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第53页!6.5有向图的应用——关健路径求关键路径的算法思想1）建立AOE网；2）从始点v0

出发，令ee(0)=0，边进行拓扑排序，边计算其余各顶点的ee(i)。若图中有回路则结束。3）从终点vn-1

出发，le(n-1)=ee(n-1)，按逆拓扑有序的顺序求le(i)，i=n-2,…,0。4）根据各点的ee和le的值，求每个活动（弧）的最早开始时间e(i)和最迟开始时间l(i)。若某弧满足条件e(i)=l(i)，则对应活动是关键活动。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第54页!6.5有向图的应用——关健路径while(!S.IsEmpty()){j=S.Pop();T.Push(j);count++;//顶点j入栈并计数

for(p=ghead[j].firstout;p;p=p->link){//对顶点j的每个后继顶点入度减1k=p->adjvex;if(--indegree[k]==0)S.Push(k);//若入度为0，则入栈Sif(ee[j]+dut(<j,k>)>ee[k])ee[k]=ee[j]+dut(<j,k>);//对j的各后继点k修改ee[k]}}if(count<n)returnfalse;//有回路

elsereturntrue;}//TopologicalSort数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第55页!6.5有向图的应用——关健路径例顶点ee[i]le[i]v0v1v2v3v4v5v6v7v80645771614180668710161418活动e[k]l[k]l-ea1a2a3a4a5a6a7a8a9a10a110 0 00 2 20 3 36 6 04 6 25 8 37 7 07 7 07 10 316 16 014 14 0数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第56页!6.6最短路径（ShortestPath）数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第57页!6.6最短路径——求单源最短路径单源最短路径问题如果从图中某一顶点（称为源点）到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。问题解法Dijkstra算法给定一个网G={V,E,W}与源点v0，求从v0到G中其它顶点的最短路径。规定各边（或弧）上的权值大于或等于0。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第58页!6.6最短路径——求单源最短路径第二条最短路径长度的求法它只可能有两种情况直接从源点到某顶点v2（只含一条弧）从源点经过顶点v1，再到达该顶点v2（由两条弧组成）数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第59页!6.6最短路径——求单源最短路径例602010305010003421103421源点终点最短路径路径长度v0v1<v0,v1>10v2----v3<v0,v3>30v4<v0,v4>10060<v0,v1,v2><v0,v3,v4><v0,v3,v2,v4><v0,v3,v2>509060数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第60页!6.6最短路径——求单源最短路径Dijkstra算法描述如下初始化置S＝{v0};dist[i]←cost[0][i],i=1,…,n-1;//n为图中顶点个数(1)求出最短路径的长度dist[k]←min{dist[i]},iV-S;S←S∨{k};(2)修改对于每一个iV-S，dist[i]←min{dist[i],dist[k]+cost[k][i]}；(3)重复(1)和(2)n-1次。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第61页!6.6最短路径——求单源最短路径Dijkstra描述的单源最短路径算法voidShortestPath_DIJ(intv0;intpath;int*dist){for(v=0;v<Vexnum;v++){find[v]=0;

path[v]=0;

dist[v]=cost[v0][v];}find[v0]=1;for(i=1;i<Vexnum;i++){k=mininum(dist);

find[k]=1;for(w=1;w<Vexnum;w++)if(!find[w]&&cost[k][w]<max)if(dist[w]>dist[k]+cost[k][w]){dist[w]=dist[k]+cost[k][w];

path[w]=k;}}}//ShortestPath_DIJ算法的时间复杂度：O(n2)数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第62页!6.6最短路径——求单源最短路径思考当网中有负的权值时，Dijkstra算法是否还能正确执行？15-5720数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第63页!6.6最短路径——所有顶点之间的最短路径Floyd算法思想逐个顶点试探法求最短路径步骤初始时设图以相邻矩阵存储；逐步试着在原路径中增加中间顶点，若加入中间顶点后路径变短，则修改之；否则，维持原值。所有顶点试探完毕，算法结束。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第64页!6.6最短路径——所有顶点之间的最短路径算法实现图用邻接矩阵cost[][]存储a[][]存放最短路径长度path[i][j]是从vi

到vj

的最短路径上vj前一顶点序号数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第65页!6.6最短路径——所有顶点之间的最短路径for(v=0；v<n；v++)for(w=0；w<n；w++){A[v][w]=cost[v][w]；

if(A[v][w]<max)path[v][w]=v；

elsepath[v][w]=-1；}for(u=0；u<n；u++)for(v=0；v<n；v++)for(w=0；w<n；w++)if(A[v][u]+A[u][w]<A[v][w]){A[v][w]=A[v][u]+A[u][w]；

path[v][w]=path[u][w]；

}//if}//ShortestPath_Floyed数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第66页!6.6最短路径——所有顶点之间的最短路径例数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第67页!本章小结图存储结构邻接矩阵邻接表遍历深度优先遍历DFS广度优先遍历BFS应用最小生成树Prim算法Kruskal算法无向图的应用有向图的应用AOE网关键路径AOV网拓扑排序最短路径Dijkstra算法Floyd算法数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第68页!书面作业P2276-1，6-2，6-3，6-4，6-5，6-8，6-12，6-14，6-15实验题实验7，实验8数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第69页!6.1图的基本概念图的抽象数据类型classGraph{public: Graph();//建立一个空图

voidInsertVertex(Type&vertex);voidInsertEdge(intv1,intv2);voidRemoveVertex(intv);voidRemoveEdge(intv1,intv2);intIsEmpty();TypeGetWeight(intv1,intv2);intGetFirstNeighbor(intv);

intGetNextNeighbor(intv1,intv2);}数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第70页!在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第71页!6.1图的基本概念——图的术语权与图的边或弧相关的数。网带权的无向图称为无向网；带权的有向图称为有向网。有向网无向网数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第72页!6.1图的基本概念——图的术语自环称边(v,v)E(G)或弧<v,v>E(G)为自环多重边（或弧）若在G中有两条或两条以上相同的边或弧，称之为多重边（或弧）数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第73页!6.1图的基本概念——图的术语完全图若有n个顶点的无向图有n(n-1)/2条边，则此图为完全无向图。若有n个顶点的有向图有n(n-1)条边，则此图为完全有向图。稀疏图（sparsegraph）边或弧很少的图，通常边数e<nlog2n稠密图（Densegraph）无向图中，边数接近n(n-1)/2；有向图中，弧数接近n(n-1)。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第74页!6.1图的基本概念——图的术语简单路径序列中顶点不重复出现的路径。简单回路始点和终点相同的简单路径。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第75页!6.1图的基本概念——图的术语子图已知图G(V,E)和图G’(V’,E’)。若V’V且E’E，则称G’为G的子图。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第76页!6.1图的基本概念——图的术语例ABCDEFGIJLHMKABCDEHMFGIJLK3个连通分量

数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第77页!6.1图的基本概念——图的术语生成树n个顶点的连通图的生成树是包含图中全部n个顶点的一个极小连通子图；ABCDEHM无向图G

ABCDEHM无向图G的生成树

多——构成回路少——不连通含有n-1条边数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第78页!6.2图的存储结构是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第79页!6.2图的存储结构例，无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第80页!6.2图的存储结构从邻接矩阵中可以反映图的许多特征无向图(1)对称矩阵（可采用压缩存储）；(2)每一行（或列）1的个数是该顶点的度；(3)主对角线全为0（简单图）。有向图(1)每一行1的个数是该顶点的出度；(2)每一列1的个数是该顶点的入度；(3)主对角线全为0（简单图）；(4)有向图的邻接矩阵不一定对称。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第81页!6.2图的存储结构用邻接矩阵表示的图的类的定义classAdjMatrix{//非带权图

intn；//顶点的个数

intmatrix[MaxSize][MaxSize]；//邻接矩阵

public:AdjMatrix(intm){n=m；}};//AdjMatrixclassAdjMatrix{//带权图

constintINFINITE=∞；

intn；//顶点的个数

floatmatrix[MaxSize][MaxSize]；//邻接矩阵public: AdjMatrix(intm){n=m；}};//AdjMatrix数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第82页!6.2图的存储结构邻接矩阵的优点容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。邻接矩阵的缺点n个顶点需要n×n个单元存储边；空间效率为O(n2)。对稀疏图而言尤其浪费空间。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第83页!6.2图的存储结构问题在无向图的邻接表中，如何求每个顶点的度？

第i个链表中的边结点个数是顶点i的度若顶点数为n，边数为e时，则在无向图的邻接表中共需多少个结点？

n个顶点结点，2e个边结点

数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第84页!6.2图的存储结构data：结点的数据域，保存顶点的数据值。firstout：结点的指针域，指向与该顶点相关联的条边（弧）的地址表头结点datafirstoutadjvexlink边/弧结点adjvex：该边或弧所指向的顶点的序号link：指向下一条边或弧的指针adjvexlinkdatafirstout数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第85页!6.2图的存储结构邻接表表示的图的类定义classEArcNode{//边(或弧)结点intadjvex；//该边或弧所指向的顶点的序号

EArcNode*link；//指向下一条边或弧的指针public: EArcNode(intadj){adjvex=adj;link=NULL;};friendclassLinkGraph;};//EArcNodeclassVNode{//表头结点

DataTypedata；//顶点的信息

EArcNode*firstout；//指向与该顶点关联的条边(弧)public: VNode(DataTypee){data=e;firstout=NULL;}friendclassLinkGraph;};//VNode数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第86页!6.2图的存储结构图的操作在邻接表的上的实现intFirstAdjVex(intv){ returnghead[v]->firstout.adjvex；}//FirstAdjVexintNextAdjVex(intv，intw){ p=ghead[v]->firstout；

while(p&&p->adjVex!=w)p=p->link；

if(!p||!p->link)return0；

elsereturnp->link->adjVex；}//NextAdjVex数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第87页!6.2图的存储结构区别对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2)，而邻接表的空间复杂度为O(n+e)。邻接矩阵多用于稠密图的存储（e接近n(n-1)/2）；而邻接表多用于稀疏图的存储（e<<n2）。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第88页!6.3图的遍历从某个起点开始可能到达不了所有其它顶点，怎么办？

解决方案：多次调用从某顶点出发遍历图的算法。图中可能存在回路，某些顶点可能会被重复访问，如何避免遍历因回路而陷入死循环。

解决方案：附设访问标志数组visited[n]在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问后，如何选取下一个要访问的顶点？

解决方案：深度优先遍历和广度优先遍历数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第89页!6.3图的遍历例深度优先搜索过程 深度优先生成树数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第90页!6.3图的遍历连通图的深度优先遍历算法voidDFSTraverse(){//深度优先求图的连通分量

intvisited[n]；//设置访问标志数组

for(v=0;v<n;v++)visited[v]=0；//初始化访问标志数组

for(v=0;v<n;v++)if(!visited[v])DFS(v)；//每次从尚未访问过的顶点出发}//DFSTraversevoidDFS(intv){//从顶点v出发访问包含该顶点的最大连通子图中的所有顶点

visited[v]=1；visit(v)；

for(w=firstAdjVex(v);w;w=nextAdjVex(v,w))if(!visited[w])DFS(w)；

}//DFS数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第91页!6.3图的遍历例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归递归返回

V1遍历序列：V1V2

V2V4

V4V5V8

V8数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第92页!6.3图的遍历例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归递归返回

V1遍历序列：V1

V7V2V4V5V8V3

V3V6

V6V7数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第93页!6.3图的遍历例V1V2V4V5V3V7V6V8例01231342datafirstout

1

6

7

2^^^adjvexlink45

5^

3

71^6785676^^^深度遍历：V1V3V7V6V2V4V8V5数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第94页!6.3图的遍历广度优先遍历BFS（BreadthFirstSearch）思路在访问了起始顶点v之后，由v出发，依次访问v的所有未被访问过的邻接点w1,w2,…,wt，然后再顺序访问w1,w2,…,wt的所有未被访问过的邻接点。再从这些访问过的顶点出发，再访问它们的所有未被访问过的邻接点，…，如此重复，直到图中所有顶点都被访问完为止。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第95页!6.3图的遍历说明广度优先遍历是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先遍历不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的顶点，以便向下一层访问。与深度优先遍历过程一样，为避免重复访问，需要一个辅助数组visited[n]，对被访问过的顶点加以标记。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第96页!6.3图的遍历广度优先搜索算法voidBFS(intv){//广度优先求图的连通分量

Q=newQueue()；//清队列QQ.Enter(v)；//每次从尚未访问过的顶点中选取一个顶点vvisited[v]=1；//标记vwhile(!Q.Empty()){//Q不空

u=Q.Leave()；//出队头元素到uvisited(u)；//访问ufor(w=FirstAdjVex(u);w;w=NextAdjVex(u,w))if(!visited[w]){Q.Enter(w)；//将u的每个未被访问的邻接点w入队

visited[w]=1；

}} }//BFS数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第97页!6.3图的遍历例，广度优先遍历序列，入队序列，出队序列。V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8V4V1V2V3数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第98页!6.3图的遍历DFS与BFS之比较空间复杂度相同，都是O(n)（借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第99页!6.4无向图的应用——最小生成树例（a）深度优先生成树（b）广度优先生成树V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第100页!6.4无向图的应用——最小生成树构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来连接网络中的n个顶点；不能使用产生回路的边。求一个连通无向网中最小生成树的方法Prim算法Kruskal算法都是利用MST的性质构造最小生成树数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第101页!6.4无向图的应用——最小生成树Prim算法Prim算法的基本思想设连通N={V,E}，T是N的最小生成树中边的集合，U是生成树的顶点集合。（1）T={}，U={u}（u为任一顶点）；（2）在所有u∈U，v∈V-U的边(u,v)∈E中找一条代价最小的边(u,v)加入集合T中，同时v加入U；（3）重复（2），直到U=V为止。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第102页!6.4无向图的应用——最小生成树Prim算法的实现图的存储：邻接矩阵在构造过程中，还设置了一个辅助数组closedge：每个元素closedge[v]有两个域lowcost：存放生成树顶点集合内顶点到生成树外各顶点v的各边上的当前最小权值adjvex：记录生成树顶点集合外各顶点距离集合内哪个顶点最近（即权值最小）数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第103页!6.4无向图的应用——最小生成树利用Prim算法求最小生成树的算法classAddArray{intadjvex;floatlowcost;};//AddArrayvoidMinSpanTree_Prim(intu,AddArrayclosedge[],AddArrayedge[],AdjMatrixG){//设图以邻接矩阵存储，用Prim算法从顶点u出发构造网G的最小生成树且保存到数组edge中

for(v=0；v<n；v++)U[v]=0；U[u]=1；

for(v=0；v<n；v++)if（u!=v){closedge[v].adjvex=u;数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第104页!6.4无向图的应用——最小生成树Prime算法分析设连通无向网有n个顶点，则该算法的时间复杂度为O(n2)适用于稠密的网络数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第105页!6.4无向图的应用——最小生成树例101214162522数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第106页!有向图可以用来描述一个工程（或系统）的进行过程。每个工程由若干个子工程（活动）组成，完成了这些子工程整个工程就结束了。这些子工程间有两种关系有先后顺序：即前一子工程结束后一子工程才能开始无先后顺序：即两个子工程谁先谁后都互不影响6.5有向图的应用数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第107页!6.5有向图的应用两个问题整个工程能否顺利进行？哪些活动是影响工程按期完工的关键？——拓扑排序——关键路径数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第108页!6.5有向图的应用——拓扑排序例学生课程学习工程图数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第109页!6.5有向图的应用——拓扑排序概念拓扑（有序）序列在AOV网中若将各个顶点（代表各个活动）排列成一个线性有序的序列v1,v2,…,vn，使得若从顶点vi

到vj有一条有向路径，则在序列中顶点vi必须排在顶点vj之前。拓扑排序在AOV网中找一个拓扑序列的过程。数据结构与算法第六章清华大学出版社赵玉兰共135页，您现在浏览的是第110页!6.5有向图的应用——拓扑排序例，对下列有向图不能求得它的拓扑有序序列BDAC因为图中存在一