1、数据结构数据结构-图图 数据结构数据结构-图图1.熟练掌握图的概念和术语，图的邻接矩阵与邻接表两种存储方法。2.熟练掌握图的遍历的概念，图的DFS与BFS方法与算法。3.掌握最小生成树的概念，构造最小生成树的方法，求图的最小生成树的算法。4.掌握最短路径的概念，图的单源点最短路径的求解方法。了解单源点最短路径的算法；5.掌握拓扑排序和关键路径的方法,了解拓扑排序和关键路径的算法。教学目标教学目标数据结构数据结构-图图6.1 6.1 图的定义和术语图的定义和术语6.2 6.2 图的存储表示图的存储表示6.3 6.3 图的遍历图的遍历6.4 6.4 最小生成树最小生成树6.5 6.5 两点之间的最
2、短路径问题两点之间的最短路径问题6.6 6.6 拓扑排序拓扑排序6.7 6.7 关键路径关键路径教学内容教学内容数据结构数据结构-图图问题回顾问题回顾数据结构数据结构-图图数据结构数据结构-图图图的定义图的定义:图图是由一个是由一个顶点集顶点集 V 和一个和一个边边集集 E 构成的数据结构。构成的数据结构。G=(V,E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。若顶点若顶点v和和w之间的边没有方向，则称这条边为之间的边没有方向，则称这条边为无向边无向边，表示为，表示为(v,w)。相应的图称为。相应的图称为无向图无向图。若从顶点若从顶点v到到w的边有方向，则称这条边为
3、的边有方向，则称这条边为有向边有向边(又称为弧又称为弧)，表示为，表示为。相应的图称为。相应的图称为有向图有向图。6.1 图的定义和术语图的定义和术语数据结构数据结构-图图 AB E C D例如例如:G1=(V1,E1)是有向图有向图其中V1=A,B,C,D,EE1=,B CA D F E例如例如:G2=(V2,E2)为无向图V2=A,B,C,D,E,FE2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)数据结构数据结构-图图名词和术语名词和术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图
4、、强连通分量生成树、生成森林数据结构数据结构-图图ABECFAEFBBC设图G=(V,E)和图 G=(V,E),且 VV,EE,则称 G 为 G 的子图子图。1597211132 带权的图分别称作有向网有向网或无向网无向网。数据结构数据结构-图图假设图中有 n 个顶点，e 条边，则含有 e=n(n-1)/2 e=n(n-1)/2 条边的无向图称作完全图完全图；含有 e=n(n-1)e=n(n-1)条弧的有向图称作 有向完全图有向完全图；若边或弧的个数 e nloge nlogn n，则称作稀疏图稀疏图，否则称作稠密图稠密图。数据结构数据结构-图图 假若顶点v 和顶点w 之间存在一条边，则称顶点
5、v 和w 互为邻接点邻接点，ACDFE例如例如:TD(B)=3TD(A)=2 边(v,w)和顶点v 和w 相关联关联。和顶点v 关联的边的数目边的数目定义为顶点的度度。B对无向图来说对无向图来说，数据结构数据结构-图图顶点的出度出度:以顶点v为弧尾的弧的数目；ABECD对有向图来说对有向图来说，顶点的入度入度:以顶点v为弧头的弧的数目。顶点的度度(TD)=)=出度出度(OD)+)+入度入度(ID)例如例如:ID(B)=2OD(B)=1TD(B)=3数据结构数据结构-图图设图G=(V,E)中的一个顶点序列 u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)E,1jm,则称从顶点u
6、 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABECD如如:长度为3的路径A,B,C,D简单路径简单路径:序列中顶点不重复出现的路径。简单回路简单回路:序列中第一个顶点和最后一个顶点相同的路径。数据结构数据结构-图图若(右)图G中任意两个顶点之间都有路径相通，则称此图为连通图连通图；若(左)无向图为非连通图，则图中各个极大极大连通子图称作此图的连通分量连通分量。BACDFEBACDFE对无向图对无向图数据结构数据结构-图图 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECDABECD对有向图，对有向图，否则，其各个强连通子图称作它的强连通
7、分量强连通分量。数据结构数据结构-图图 假设一个连通图连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小极小连通子图（生成树生成树）。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森生成森林林。BACDFE数据结构数据结构-图图结构的建立结构的建立对顶点的操作对顶点的操作插入和删除弧插入和删除弧遍历遍历部分操作部分操作数据结构数据结构-图图CreatGraph(&G,V,E)/按定义(V,VR)构造图结构的建立结构的建立对顶点的操作对顶点的操作LocateVex(G,u);/若G中存在顶点u，则返回该顶点在图中“位置位置”InsertVex(&G,v
8、);/在图G中增添新顶点v。DeleteVex(&G,v);/删除G中顶点v及其相关的弧。数据结构数据结构-图图对弧的操作对弧的操作InsertArc(&G,v,w);/在G中增添弧，若G是无向的，则还增添对称弧。DeleteArc(&G,v,w);/在G中删除弧，若G是无向的，则还删除对称弧。遍历遍历DFSTraverse(G,v);/从顶点v开始深度优先深度优先遍历图G，并对访问每个顶点一次且仅一次。BFSTraverse(G,v);/从顶点v开始广广度优先度优先遍历图G，并对访问每个顶点一次且仅一次。数据结构数据结构-图图在线性结构中，数据元素之间仅具有线性关系；在线性结构中，数据元素之
9、间仅具有线性关系；在树结构中，结点之间具有层次关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比数据结构数据结构-图图在线性结构中，元素之间的关系为在线性结构中，元素之间的关系为前驱和后继前驱和后继；在树结构中，结点之间的关系为在树结构中，结点之间的关系为双亲和孩子双亲和孩子；在图结构中，顶点之间的关系为在图结构中，顶点之间的关系为邻接邻接。FECBAD线性结构线性结构ABCDEF树结构树结
10、构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比数据结构数据结构-图图名词和术语复习名词和术语复习网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林数据结构数据结构-图图6.2 图的存储表示图的存储表示一图的数组(邻接矩阵)存储表示二图的邻接（链）表存储表示数据结构数据结构-图图ABCDEFAij=0 (i,j)E1 (i,j)E一、一、图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为A B C D E F数据结构数据结构-图图无向图数组表示法
11、特点：无向图数组表示法特点：l无向图邻接矩阵是对称矩阵，同一条边表示了两次；l顶点v的度：等于二维数组对应行(或列)中1的个数；l判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；l在图中增加、删除边：只需对二维数组对应分量赋值1或清0；l占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；l对有向图的数组表示法可做类似的讨论数据结构数据结构-图图有向图有向图的邻接矩阵的邻接矩阵为非对称矩阵为非对称矩阵ABECDA B C D EA BCDE数据结构数据结构-图图struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。/无权图
12、：0或1，有权图：权值 InfoType *info;/该弧相关信息（可选）;enum GraphKindDG,DN,UDG,UDN;/有向图，有向网，无向图，无向网struct MGraph/图的定义图的定义 VertexType vexsMaxVN;/顶点信息 ArcCell arcsMaxVNMaxVN;/弧的信息 int vexnum,arcnum;/顶点数，弧数 enum GraphKind kind;/图的种类标志 ;数据结构数据结构-图图常见的简单描述如下：struct MGraph struct MGraph/图的定义图的定义intint matMaxVNMaxVN;/边、弧的
13、信息 intint vexnum;/顶点数 GraphKindGraphKind kind;/图的种类标志 ;数据结构数据结构-图图0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE二、图的邻接二、图的邻接 (链链)表表存储表示存储表示数据结构数据结构-图图有向图的邻接表有向图的邻接表1 4230 120 1 2 3 4 A B C D EABECF注意，在有向图的邻接表中不易找到指向该顶点的弧。数据结构数据结构-图图ABECD有向图的有向图的逆逆邻接表邻接表A B C D E 303420 01234在有向图的邻接表中，对每个顶点，链接的
14、是指向该顶点的弧。数据结构数据结构-图图struct ArcNode int adjvex(data);/该弧所指向的顶点的位置 ArcNode *nextarc(next);/指向下一条弧 InfoType *info;/该弧相关信息（可选）;adjvex info nextarc弧的结点结构弧的结点结构struct VNode VertexType data;/顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧 ;data firstarc顶点的结点结构顶点的结点结构数据结构数据结构-图图struct ALGraph /Adjacent List VNode vert
15、icesMaxVN;int vexnum,arcnum;enum GraphKind kind;/图的种类标志;图的定义图的定义数据结构数据结构-图图无向图邻接表的特点无向图邻接表的特点l在邻接表中，同一条边对应两个结点；l顶点v的度：等于v 对应的链表的长度；l判定两顶点v，w是否邻接：要看v对应的链表中有无对应的结点w（相反判断也行）；l增减边：要在两个单链表插入、删除结点；l占用存储空间与顶点数、边数均有关；适用于边稀疏的图数据结构数据结构-图图建立邻接表算法描述建立邻接表算法描述/初始化一个结点总数为num的图,k为图的类型，num 为结点总数void InitG(ALGraph G,
16、enum GraphKind k,int num)G.kind=k;G.vexnum=num;G.vertices=new VNodevexnum;for(int i=0;iG.verticesi.data;/输入结点信息/有向图（网）增加弧的算法,将弧(from,to,weight)加入图void InsertArc(ALGraph G,int from,int to,int weight)ArcNode*s=new ArcNode;s-weight=weight;s-adjvex=to;s-nextarc=G.verticesfrom.firstarc;/插到链表verticesfrom的
17、头 G.verticesfrom.firstarc=s;显然，对于无向图（网），只需交换from和to的位置，再进行一次增加弧的操作即可数据结构数据结构-图图课内练习课内练习1、分析并回答下列问题：1)图中顶点的度之和与边数之和的关系?2)有向图中顶点的入度之和与出度之和的关系?3)具有n个顶点的无向图，恰好有n-1条边时一定连通吗？4)具有n个顶点的无向图，至少应有多少条边（可能/一定）是一个连通图?5)具有n个顶点的有向图，至少应有多少条弧（可能/一定）是一个强连通图?数据结构数据结构-图图课内练习课内练习2、设一有向图G=(V,E)，其中V=a,b,c,d,e，E=,1)请画出该有向图，
18、并求各顶点的入度和出度。2)画出有向图的邻接链表。3)画出有向图的逆邻接链表。数据结构数据结构-图图小学生游戏 某天，无聊的小杰叫上几个同学玩游戏，其中有比较笨的小凤，比较傻的小雪，可爱的小鑫和自以为是的小练。他们去找聪明的小艺去给他们当裁判。判定谁取得游戏胜利。而这个游戏是：由小艺给出一个数 a，再给出一个数 b，经过规定的运算，使得数 a 变换成数 b，且使用最少的变换次数 n.谁先说对这个 n，谁就取得胜利。当然，因为都是小学生，所以假定如果n6，就算是没有答案。那么裁判小艺试图通过编程来使自己尽快的获得答案。请你帮帮他吧.问题描述：题目给出数a(a是一个正整数，不超过50位)，再给出目
19、标数b(同样是一个正整数，不超过50位)，数的运算有三种：1：使当前数加上19854292：使当前数加上20063：使当前数乘2 课内思考课内思考数据结构数据结构-图图例如：小艺给出数a=1，给出数b=1987437那么最快我们经过3次指定运算可以使1变成19874371*2=2；（第3种变换）2+1985429=1985431；（第1种变换）1985431+2006=1987437；（第2种变换）再例如：小艺给出数a=1，给出数b=128那么最快我们经过7次指定运算可以使1变成1281*2*2*2*2*2*2*2=128（均采用第3种变换），但是因为n6，所以按题不符合要求。数据结构数据结构
20、-图图6.3 图的遍历图的遍历 从图中某个顶点出发，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。一一深度优先搜索深度优先搜索二二广度优先搜索广度优先搜索三三遍历应用举例遍历应用举例数据结构数据结构-图图 从图中某个顶点V0 出发，访问此顶点，然后依次从依次从V0的各个未被访问的邻的各个未被访问的邻接点出发深度优先搜索遍历图接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图一、深度优先搜索遍历图连通图连通图的深度优先搜索遍历的深度优先搜索遍历数据结构数据结构-图图Vw1SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG
21、2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V：foreach(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。w2w3w2数据结构数据结构-图图从上页的图解可见从上页的图解可见:1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志数组bool visitedvexnum”。2.如何判别V的邻接点是否被访问？数据结构数据结构-图图void DFS(Graph G,int v)/从顶点从顶点v出发，深度优先搜索遍历连通图出发，深度优先搜索遍历连通图 G visitedv=true;cout G.vertice
22、sv.data;for(w=FirstAdjVex(G,v);w存在;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w，递归调用DFS/DFS若采用邻接矩阵，则算法可写成右边的形式：void DFS(Graph G,int v)visitedv=true;cout G.verticesv.data;for(w=0;wG.vexnum;w+)if(matvw&!visitedw)DFS(G,w);/DFS数据结构数据结构-图图 先将每个顶点的访问标志设为 false,之后搜索图中每个顶点，若未被访问，则以该顶点为起始点，进行深度优先搜
23、索遍历，否则继续检查下一顶点。非连通图非连通图的深度优先搜索遍历的深度优先搜索遍历void DFSTraverse(Graph G)/深度优先遍历深度优先遍历 fill(visited,visited+G.vexnum,false);/访问标志数组初始化 for(v=0;vw1,V-w2,V-w8 的路径长度为1；V-w7,V-w3,V-w5 的路径长度为2；V-w6,V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w4数据结构数据结构-图图 从图中某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们按这些顶点被访
24、问的先后次序依次访问它们的邻接点的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。对于非连通图，可能此时尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。数据结构数据结构-图图void BFSTraverse(Graph G)fill(visited,visited+G.vexnum,false);/初始化visited数组 for(int v=0;vG.vexnum;+v)if(visitedv=true)continue;/v 已经访问visitedv=true;coutG.verticesv.data;EnQueue(Q,v);/
25、v入队列while(!Empty(Q)DeQueue(Q,u);/队头元素出队并置为u foreach(u的邻接点的邻接点w)if(visitedw=false)visitedw=true;Visit(w);EnQueue(Q,w);/BFSTraverse数据结构数据结构-图图void BFSTraverse(Graph G)fill(visited,visited+G.vexnum,false);/初始化visited数组 for(int v=0;vG.vexnum;+v)if(visitedv=false)EnQueue(Q,v);/v入队列while(!Empty(Q)DeQueue(
26、Q,u);/队头元素出队并置为u visitedu=true;cout G.verticesu.data;foreach(u的邻接点的邻接点w)if(visitedw=false)EnQueue(Q,w);/BFSTraverse也可写成：数据结构数据结构-图图三、遍历应用举例三、遍历应用举例1.求一条从顶点求一条从顶点 i 到顶点到顶点 s 的简单的简单路径路径2.求两个顶点之间的一条长度最短求两个顶点之间的一条长度最短的路径的路径数据结构数据结构-图图1.求一条从顶点求一条从顶点 i 到顶点到顶点 s 的简单路径的简单路径abchdekfg 求从顶点 b b 到顶点 k k 的一条简单路径
27、。从顶点 b b 出发进行深度优先搜索遍历。例如例如:假设找到的第一个邻接点是a a，则得到的结点访问序列可能为:b a d h c e k f g。假设找到的第一个邻接点是c c，则得到的结点访问序列可能为:b c h d a e k f g，数据结构数据结构-图图1.从顶点 i 到顶点 s,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s。2.遍历过程中搜索到的顶点不一定是路径上的顶点。结论结论:3.3.由它出发进行的深度优先遍历已经完成的顶点一定不是路径上的顶点。数据结构数据结构-图图stack Path;bool found;/从顶点v出发DFS遍历，求得一条从v到s
28、的简单路径，并记录在栈Path中void DFSearch(int v,int s)if(found=true)return;/若已成功，则不再继续if(v=s)found=true;output solution;return;foreach(v的邻接点的邻接点w)/类似迷宫问题的4个方向if(visitedw=false)visitedw=true;Path.Push(w);/顶点v加入路径 DFSearch(w,s);Path.Pop();/从路径上删除顶点 v 数据结构数据结构-图图2.求两个顶点之间的一条长度求两个顶点之间的一条长度最短的路径最短的路径 若两个顶点之间存在多条路径，则
29、其中必有一条路径长度最短的路径。如何求得这条路径?数据结构数据结构-图图abchdekfg因此，求路径长度最短的路径可以基于广度优先求路径长度最短的路径可以基于广度优先搜索遍历进行搜索遍历进行。深度优先搜索访问顶点的次序次序取决于图的存储存储结构结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。数据结构数据结构-图图例如:求下图中顶点 3 至顶点 5 的一条最短路径。321475689struct Elem int vertex;/顶点编号 int pre;/邻接顶点(在队列中的位置在队列中的位置),达到保存路径的效果 int step;/路径长度;vector Path;/由于常
30、规的队列在出队时将删除头元素，这里，我们用线性表线性表代替队列，移动元素位置就可以达到出队的效果。数据结构数据结构-图图int BFSearch(Graph G,int v,int s)/利用BFS，求v到s的最短路径，结果记录在线性表Path中 fill(visited,visited+G.vexnum,false);/初始化visited数组 visitedv=true;Elem e(v,-1,0);Path.push_back(e);/源点入队列 for(int i=0;iPath.size();i+)int u=Pathi.vertex;/从队列中取出头元素if(u=s)return
31、u.step;foreach(u的邻接点w)/类似迷宫的4个方向 if(visitedw=true)continue;Elem e(w,i,u.step+1);visitedw=true;Path.push_back(e);/邻接点入队列 3,-1 1,0 2,0 4,1 7,1 5,3 6,3 8,4 9,40 1 2 3 4 5 6 7 8Path:数据结构数据结构-图图14526396827553493 3、已、已知知无无向向图如图所示。图如图所示。写出相应的邻接矩阵表示。写出相应的邻接矩阵表示。写出从顶写出从顶点点1 1开开始的深度优先和广度优先遍历始的深度优先和广度优先遍历序列。序列
32、。画出从顶画出从顶点点1 1开开始的深度优先和广度优先生成始的深度优先和广度优先生成树。树。课内练习课内练习数据结构数据结构-图图利用宽度优先，对每一个数字做3种运算，在展开第6次之内求得结果，即为所用次数，否则不能在6次能得到结果小学生游戏的解决思路小学生游戏的解决思路 数据结构数据结构-图图小结小结1.图的概念和术语，图的邻接矩阵与邻接表两种存储方法。2.图的DFS与BFS两种遍历。数据结构数据结构-图图作业：作业：2.1.1,2.1.2,2.1.3 2.2.1,2.2.2,2.2.3(使用prim和kruscal方法)2.32.42.5.1,2.5.2,2.5.33.1.3,3.1.43.33.4数据结构数据结构-图图课后建议：课后建议：HLoj 1014（最小生成树Prim或Kruscal）HDoj 1874,1548（单源最短路径Dijkstra）HDoj 1869（任意两点间最短路径Floyd）HDoj 1285（拓扑排序）HLoj 1019,1023,1205,1227（DFS或BFS）HLoj 1212（BFS）HDoj 1253,1072（BFS）
