《《数据结构图》PPT课件》由会员分享，可在线阅读，更多相关《《数据结构图》PPT课件（110页珍藏版）》请在金锄头文库上搜索。
1、第7章 图陈守孔陈守孔 孟佳娜孟佳娜 陈卓陈卓1东普鲁士的七桥问题东普鲁士的七桥问题七桥问题的数学模型A BD C 图的应用历史w东普鲁士的七桥问题东普鲁士的七桥问题w要求从某一地出发，经过每座桥恰巧一次，最后仍要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。回到原地。w1736年欧拉将陆地作顶点，将桥作边，从而将这个年欧拉将陆地作顶点，将桥作边，从而将这个实际问题抽象成图的模型。实际问题抽象成图的模型。w“一笔划问题一笔划问题”：当两个顶点的度为偶数，其余顶：当两个顶点的度为偶数，其余顶点的度为奇数时，可以从一个偶数顶点出发，经过点的度为奇数时，可以从一个偶数顶点出发，经过每条边一次，
2、最后到达另一偶数顶点。每条边一次，最后到达另一偶数顶点。w“欧拉回路问题欧拉回路问题”：只有所有的顶点的度都是偶数，：只有所有的顶点的度都是偶数，才能从一个顶点出发，经过每条边一次，最后回这才能从一个顶点出发，经过每条边一次，最后回这个顶点。个顶点。w欧拉证明欧拉证明七桥问题无解七桥问题无解。清华大学2001设在设在4地（地（A，B，C，D）之间架设有）之间架设有6座桥，如图所示：座桥，如图所示： 要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。（1）试就以上图形说明：此问题有解的条件是什么？）试就以上图形说明：此问题有解的条件是什么
3、？（5分）分）（2）设图中的顶点数为）设图中的顶点数为n,试用试用C或或PASCAL描述与求解此问题有关描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。（的数据结构并编写一个算法，找出满足要求的一条回路。（10分）分）本章目录w7.1图的定义和术语图的定义和术语w7.2图的存储结构图的存储结构n7.2.1数组表示法数组表示法n7.2.2邻接表邻接表（*7.2.3十字链表十字链表*7.2.4邻接多重表邻接多重表）w7.3图的遍历图的遍历n7.3.1深度优先搜索深度优先搜索n7.3.2广度优先搜索广度优先搜索w7.4图的连通性问题图的连通性问题n7.4.1图的连通分量和生成树
4、图的连通分量和生成树n7.4.2最小生成树最小生成树w7.5有向无环图及其应用有向无环图及其应用n7.5.1拓扑排序拓扑排序n*7.5.2关键路径关键路径w7.6最短路径最短路径（*7.7算法设计举例）算法设计举例）n7.6.1从某个源点到其它各顶点的最短路径从某个源点到其它各顶点的最短路径n7.6.2每一对顶点之间的最短路径每一对顶点之间的最短路径主要内容w知识点知识点n1图的定义，概念、术语及基本操作。图的定义，概念、术语及基本操作。n2图的存储结构，特别是邻接矩阵和邻接表。图的存储结构，特别是邻接矩阵和邻接表。n3图的深度优先遍历和宽度优先遍历。图的深度优先遍历和宽度优先遍历。n4图的应
5、用（连通分量，最小生成树，拓扑排序，关键路经，图的应用（连通分量，最小生成树，拓扑排序，关键路经，最短路经）。最短路经）。w重点难点重点难点n1基本概念中，完全图、连通分量、生成树和邻接点是重点。基本概念中，完全图、连通分量、生成树和邻接点是重点。n2建立图的各种存储结构的算法。建立图的各种存储结构的算法。n3图的遍历算法及其应用。图的遍历算法及其应用。n4通过遍历求出连通分量的个数，深（宽）度优先生成树。通过遍历求出连通分量的个数，深（宽）度优先生成树。n5最小生成树的生成过程。最小生成树的生成过程。n6拓扑排序的求法。关键路经的求法。拓扑排序的求法。关键路经的求法。n7最短路径的手工模拟。
6、最短路径的手工模拟。图的示例（有向图与无向图）V1V4V2V3V5V4V3V2V1结点之间的关系：多对多，任两个结点之间结点之间的关系：多对多，任两个结点之间都都可能可能有关系存在有关系存在v图(Graph)图G是由两个集合是由两个集合V(G)和和E(G)组成成 的的,记为G=(V,E)其中：其中：V(G)V(G)是顶点的非空有限集是顶点的非空有限集 E(G)E(G)是边的有限集合，边是顶点的无序对或有是边的有限集合，边是顶点的无序对或有序对序对v有向有向图有向有向图G是由两个集合是由两个集合V(G)和和E(G)组成成 V(G)V(G)是顶点的非空有限集，是顶点的非空有限集，E(G)E(G)是
7、有向边（也称弧）的有是有向边（也称弧）的有限集合，弧是顶点的有序对，记为限集合，弧是顶点的有序对，记为 ，vi,vjvi,vj是顶点，是顶点，vivi为弧尾，为弧尾，vjvj为弧头为弧头v无向无向图无向无向图G是由两个集合是由两个集合V(G)和和E(G)组成成 V(G)V(G)是顶点的非空有限集，是顶点的非空有限集，E(G)E(G)是边的有限集合，边是顶是边的有限集合，边是顶 点的无序对，记为（点的无序对，记为（vi,vjvi,vj）或（或（vj,vi)vj,vi)，并且并且（vi,vjvi,vj)=()=(vj,vivj,vi) )图的概念（的概念（1）例例G1图图G1中：中：V(G1)=v
8、1,v2,v3,v4E(G1)=,G2图图G2中：中：V(G2)=v1,v2,v3,v4E(G2)=(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)v1v2v3v4v1v2v3v4图的示例图的示例v有向完全图有向完全图: :n n个顶点的有向图最大边数是个顶点的有向图最大边数是n(n-1)n(n-1)v无向完全图无向完全图: :n n个顶点的无向图最大边数是个顶点的无向图最大边数是n(n-1)/2n(n-1)/2v邻接点邻接点: :若若( (vi,vjvi,vj) )是是一条无向一条无向边，则称边，则称vivi和和vjvj互为互为 v关联关联: :
9、vivi和和vjvj互为邻接点，称互为邻接点，称边边( (vi,vjvi,vj) )关联于顶点关联于顶点vivi和和vjvjv顶点的度顶点的度v无向图中，顶点的度为与每个顶点相连的边数无向图中，顶点的度为与每个顶点相连的边数,记为记为D(v)v有向图中，顶点的度分成入度与出度，其中入度是以该顶有向图中，顶点的度分成入度与出度，其中入度是以该顶点为头的弧的数目，记为点为头的弧的数目，记为ID(v)。出度是以该顶点为尾的弧出度是以该顶点为尾的弧的数目的数目,记为记为OD(v)。顶点的度为入度和出度的和，即顶点的度为入度和出度的和，即D(v)=ID(v)+OD(v)。v1v3v4v2v1v2v3v4
10、图的概念（图的概念（2 2）v子图子图如果图如果图G(V,E)G(V,E)和图和图G(V,E),G(V,E),满足：满足：VV V V，EE E E 则称则称GG为为G G的子图的子图24513635621v1v3v4v2v1v3v2v3v4图的概念（图的概念（3 3）1573246路径：路径：1，2，3，5，6，3路径长度：路径长度：5简单路径：简单路径：1，2，3，5回路：回路：1,2,3,5,6,3,1简单回路：简单回路：3，5，6，3v路径是顶点的序列是顶点的序列V=Vp,ViV=Vp,Vi1 1,ViVin n,Vq,Vq ，满足满足( (Vp,ViVp,Vi1 1), ), ( (
11、ViVi1 1,Vi,Vi2 2), , ), , ( (ViVin n,Vq,Vq) ) E (G),E (G),则称则称vpvp到到vqvq存在存在路径路径. .v路径长度路径长度沿路径边的数目或沿路径各边权值之和沿路径边的数目或沿路径各边权值之和. .v回路回路第一个顶点和最后一个顶点相同的路径叫回路第一个顶点和最后一个顶点相同的路径叫回路v简单路径简单路径序列中顶点不重复出现的路径叫简单路径序列中顶点不重复出现的路径叫简单路径v简单回路简单回路除了第一个顶点和最后一个顶点外，其余顶点不除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路重复出现的回路叫简单回路路径：路径：
12、1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，1245136图的概念（图的概念（4 4）v连通连通从顶点从顶点ViVi到顶点到顶点vjvj有一条路径，则说有一条路径，则说ViVi和和vjvj是连通是连通的的v连通图连通图图中任意两个顶点都是连通的图叫图中任意两个顶点都是连通的图叫连通图连通图v连通分量连通分量无向图中的无向图中的最大最大( (含的边和顶点最多含的边和顶点最多) )连通连通子子图图v强连通图强连通图有向图中，如果对每一对有向图中，如果对每一对Vi,VjVi,Vj
13、V V, , ViVi VjVj, ,从从ViVi到到VjVj 和从和从VjVj到到 ViVi都存在路径，则称都存在路径，则称G G是是强连通图强连通图强连通图35621536强连通分量连通图245136245136非强连通图图的概念（图的概念（5 5）连通分量及强连通分量示例连通分量及强连通分量示例ABDCEFABCDEFv3v2v1G3的强连通分量的强连通分量G4及其两个连通分量及其两个连通分量v权权与图的边或弧相关的数叫与图的边或弧相关的数叫权权v网网( (络）络）带权的图叫带权的图叫网网v1v2v4v5v33111024865图的概念（图的概念（6 6）w一一个个连连通通图图的的生生成
14、成树树是是一一个个极极小小连连通通子子图图，它它含含有有图图中中全全部部顶顶点点，但但只只有有足足以以构构成成一一棵棵树的树的n-1条边。条边。w一棵有一棵有n个顶点的生成树有且仅有个顶点的生成树有且仅有n-1条边。条边。图的概念（7）15732461573246连通图生成树（自由树）树或自由树或无根树w无回路的图称为树或自由树或无根树图的概念（8）w有向树：有向树：只有一个顶点的入度为只有一个顶点的入度为0，其余，其余顶点的入度为顶点的入度为1的有向图。的有向图。V1V4V2V3有向树是有向树是弱弱连通连通的的抽象数据类型图的定义ADTGraph 数据对象数据对象V：V是具有相同特性的数据元
15、素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。数据关系数据关系R：R=VRVR=|v,w V|v,w V且且P(v,wP(v,w),表示从表示从v v到到w w的弧，的弧，谓词谓词P(v,wP(v,w)定义了弧定义了弧的意义或信息的意义或信息 基本操作基本操作P：GraphCreat(G,，V，VR)；GraphDestory(G)；GraphLocateVertex(G，v)；GraphGetVertex(G，v)；GraphFirstAdj(G，v)；GraphNextAdj(G，v，w)；GraphInsertVertex(G，v)；GraphDeleteVertex
16、(G，v)；GraphInsertArc(G，v，w)；GraphDeleteArc(G，v，w)；DFSTtraverse(G，v，Visit()；BFSTtraverse(G，v，Visit()；ADTGraph图的主要操作GraphLocateVertex(G，v)；GraphGetVertex(G，v)；GraphFirstAdj(G，v)；GraphNextAdj(G，v，w)；图的存储结构:数组表示w数据结构的存储表示，既要表示数据结构的存储表示，既要表示数据元素数据元素（值），又要表示数据元素之间的（值），又要表示数据元素之间的关系关系；w图的任意两个结点（顶点）之间都可能有关图
17、的任意两个结点（顶点）之间都可能有关系，因此用二维数组来表示；系，因此用二维数组来表示；w二维数组中元素二维数组中元素aij=0表示表示vi和和vj没有关系，没有关系，即即vi和和vj不邻接不邻接（或没有（或没有vi邻接到邻接到vj）w对于网，可以用对于网，可以用aij表示表示权权。若。若vi和和vj不邻接不邻接（或没有（或没有vi邻接到邻接到vj），则可以用无限大），则可以用无限大表表示权。示权。图的存贮结构_数组表示w#define MAXNODE 64 图中顶点的最大个数图中顶点的最大个数 wtypedef char VertexType; 顶点的数据类型顶点的数据类型wtypedef
18、int EdgeType; 边或弧的类型边或弧的类型wtypedef struct w VertexType vexsMAXNODE; 顶点向量顶点向量w EdgeType arcsMAXNODEMAXNODE; w 邻接矩阵邻接矩阵w int vexnum,arcnum; 图的顶点数和弧数图的顶点数和弧数w MGraph; 图的存贮结构：邻接矩阵 若若顶顶点点只只是是编编号号信信息息，边边上上信信息息只只是是有有无无（边边），则则数组表示法可以简化为如下的邻接矩阵表示法数组表示法可以简化为如下的邻接矩阵表示法: : typedef int AdjMatrixMAXNODEMAXNODE; t
19、ypedef int AdjMatrixMAXNODEMAXNODE; * *有有n n个顶点个顶点的图的图G=(V,R)G=(V,R)的邻接矩阵为的邻接矩阵为n n阶方阵阶方阵A,A,其定其定义如下：义如下： 图的存储结构：数组表示v3v2v4v1v3v2v1v1v3v2v432457图的邻接矩阵表示法的特点w对于对于无向图无向图： 邻接矩阵一定是一个对称矩阵邻接矩阵一定是一个对称矩阵 行（列）非零元素个数，表示度行（列）非零元素个数，表示度 w对于对于有向图有向图： 矩阵不一定是一个对称矩阵不一定是一个对称矩矩阵阵 行非零元素个数，表示出度行非零元素个数，表示出度 列非零元素个数，表示入度
20、列非零元素个数，表示入度u邻接矩阵的存储空间只和顶点个数有关，和邻接矩阵的存储空间只和顶点个数有关，和边数无关边数无关建立无向图的邻接矩阵存储结构void CreatAdjMatrix(AdjMatrixt g)/建立无向图的邻接矩阵存储结构建立无向图的邻接矩阵存储结构 int i,j,n;scanf(“%d”,&n); for (i=1;i=n;j+) for(j=1;j=n;j+) gij=0; scanf(&i,&j); while(i & j) /两顶点之一为两顶点之一为0表示结束表示结束 gij=1; gji=1; scanf(&i,&j); 邻接矩阵注释若图顶点信息复杂，除用二维数
21、组存储若图顶点信息复杂，除用二维数组存储顶点间关系的顶点间关系的邻接矩阵邻接矩阵外，还需要一个外，还需要一个具有具有n个元素的个元素的一维数组一维数组存储顶点信息，存储顶点信息，其中下标其中下标i的元素存储顶点的元素存储顶点vi的信息。的信息。图的存储结构：邻接表(adjacency list)w对图中每个顶点建立一个邻接关系的对图中每个顶点建立一个邻接关系的单单链表链表，并将，并将其表头指针用向量其表头指针用向量(一维数组一维数组)存储存储,该结构称为邻接该结构称为邻接表。表。w无向图的无向图的第第i i个链表个链表将图中将图中与顶点与顶点v vi i相邻接的所有顶相邻接的所有顶点链接起来点
22、链接起来，也就是链表中的表头结点到链表中的，也就是链表中的表头结点到链表中的每个结点表示了与表头结点每个结点表示了与表头结点vi相关的边。相关的边。w有向图的有向图的第第i i个链表个链表，链接了，链接了以顶点以顶点v vi i为尾（射出）为尾（射出）的所有（射入）顶点的所有（射入）顶点，也就是链表中的表头结点到，也就是链表中的表头结点到链表中的每个结点表示了图中关联到表头结点链表中的每个结点表示了图中关联到表头结点vi的的所有弧所有弧。 邻接表中的结点结构adjvexnextinfo表结点头结点firstarcdata邻接表的类型定义#define MAXNODE 64 图中顶点的最大个数图
23、中顶点的最大个数 typedef char VertexType; 顶点的数据类型顶点的数据类型typedef struct ArcNode 边表结点边表结点 int adjvex; 邻接点在顶点向量中的下标邻接点在顶点向量中的下标 struct ArcNode *next;指向下一邻接点的指针指向下一邻接点的指针 InfoType *info; 和弧和弧(或边或边)相关的信息指针相关的信息指针 ArcNode;typedef struct 顶点结点顶点结点 VertexType vertex; 顶点信息顶点信息 ArcNode *firstarc; 指向第一邻接点的指针指向第一邻接点的指针
24、VerNode;typedef struct VerNode verticesMAXNODE; 邻接表邻接表 int vexnum，arcnum; 顶点和边的数目顶点和边的数目 AlGraph;邻接表示例（无向图）对于无向图，第对于无向图，第i i个顶点的度为第个顶点的度为第i i个链表的结点数个链表的结点数v3v2v4v10 v11 v22 v33 v4100022113332v3v2v10 v11 v22 v3102邻接表示例（有向图）图的存储结构：逆邻接表w若问题总对入度更关心，则可以把线性链表的若问题总对入度更关心，则可以把线性链表的表结点的数据域更改即可：由表尾改为表头：表结点的数据
25、域更改即可：由表尾改为表头：所有以头结点为表头的弧组成的线性链表。所有以头结点为表头的弧组成的线性链表。此时该邻接表称为此时该邻接表称为逆邻接表逆邻接表。v3v2v10 v11 v22 v3011建立有向图的邻接表存储结构(1)void CreatAdjList(AlGraph g)/建立有向图的邻接表存储结构建立有向图的邻接表存储结构 int n，m=0; scanf(“%d”,&n); /输入顶点个数输入顶点个数 for (i=1;iadjvex=j; p-i.firstarc; i. firstarc=p; m+; /弧的个数加弧的个数加1 scanf(&v1,&v2) /while g
26、.vexnum=n; g.arcnum=m;/CreatAdjList十字链表：有向图另一存储结构w邻接表和逆邻接表相结合的存储结构邻接表和逆邻接表相结合的存储结构w弧结点弧结点tvexhvexhlinktlinkinfo顶点结点顶点结点vertexfirstinfirstoutv3v2v4v1 1 2 0 1 0 2 2 3 0 v1 1 v2 2 v3 3 v4 1 3 0 3十字链表的定义w#define MAXNODE / 图中顶点的最大个数图中顶点的最大个数 wtypedef struct arc / 弧结点弧结点w int headvex,tailvex; w struct arc
27、 *headlink, *taillink; w ; / 和弧相关的信息和弧相关的信息 wOrArcNode;wtypedef struct / 顶点结点顶点结点w vertype vertex; / 顶点信息顶点信息 w OrArcNode *firstin, *firstout; wOrVerNode;wtypedef OrVerNode OrthListMAXNODE； / 十字链表十字链表邻接多重表：无向图另一存储结构w边结点边结点markivexjvexilinkjlink顶点结点顶点结点vertexfirstedge0 v11 v22 v33 v4 2 3 1 3 1 2 0 1
28、0 2 0 3 w#define MAXNODE / 图中顶点的最大个数图中顶点的最大个数 w/ 边结点边结点:wtypedef struct edgew int ivex,jvex; w struct edge *ilink, *jlink; w ; / 和边相关的信息和边相关的信息 wENode;w/ 顶点结点顶点结点:wtypedef struct w vertype vertex; / 顶点信息顶点信息 w ENode *firstedge; / 指向第一邻接点的指针指向第一邻接点的指针 wEVerNode;w/ 邻接多重表：邻接多重表：w typedef EVerNode AdjMu
29、ListMAXNODE； 图的遍历w图的遍历图的遍历（TravellingGraph）:从图中某从图中某一个顶点出发，访问图中的其余顶点，使一个顶点出发，访问图中的其余顶点，使每个顶点被访问一次且仅被访问一次。每个顶点被访问一次且仅被访问一次。w方法方法：n深度优先搜索深度优先搜索n广度优先搜索广度优先搜索w设访问标志数组设访问标志数组visited图的遍历深度优先搜索：深度优先搜索：V1-V2-V4-V8-V5-V6-v3-v7广度优先搜索广度优先搜索V1-V2-V3-V4-v5-v6-v7-v8v2v4v1v5v3v6v7v8若不确定存储结构，若不确定存储结构，遍历结果不唯一。遍历结果不唯
30、一。一种可能的遍历序列一种可能的遍历序列如下：如下：图的遍历:深度优先搜索w深度优先搜索深度优先搜索（DepthFirstSearch）1从任一个顶点从任一个顶点v出发，访问该顶点；出发，访问该顶点；2然后依次从然后依次从v的未被访问的邻接点出发深度优的未被访问的邻接点出发深度优先遍历图，直至图中所有和先遍历图，直至图中所有和v有路径相通的顶有路径相通的顶点都被访问到；点都被访问到；3此时若图中尚有顶点未被访问，则另选中下此时若图中尚有顶点未被访问，则另选中下一个未被访问的顶点作起始点，访问该顶点，一个未被访问的顶点作起始点，访问该顶点，继续过程继续过程2，直到所有顶点都被访问完。，直到所有顶
31、点都被访问完。深度优先搜索示例v2v4v1v5v3v6v7v8v2v4v1v5v3v6v7v8深度优先搜索示例v2v4v1v5v3v6v7v8v2v4v1v5v3v6v7v8v2v4v1v5v3v6v7v8图的遍历:深度优先搜索intvisitedMAXNODEMAXNODE/访问标志数组访问标志数组voidDFSTDFSTraverse(GraphG)/深度优先遍历图深度优先遍历图Gfor(v=1；v；v+)visitedv=0；/初初始始访访问问数数组组置置未未访问标志访问标志for(v=1；vG. .vernum；v+)if(!visitedv)DFSDFS(G,v)；/对对未未访访问问
32、过过的的顶顶点点调调用用DFS/DFSTDFSTraversevoidDFSDFS(GraphG,intv)/从从顶点顶点v出发递归地深度优先遍历图出发递归地深度优先遍历图Gvisitv；visitedv=1；/访问访问v顶点（输出顶点（输出v）for(w=GraphFirstAdj(G,v);w;w=GraphNextAdj(G,v,w)if(!visitedw)DFS(G,w)；/DFSDFS图的遍历:广度优先搜索w广度优先搜索广度优先搜索1从图中某顶点从图中某顶点v出发，在访问出发，在访问v之后，之后，2依次访问依次访问v的各个的各个未曾被访问过的邻接点未曾被访问过的邻接点，然，然后分别
33、从这些邻接点出发依次访问它们的后分别从这些邻接点出发依次访问它们的未未被访问的邻接点被访问的邻接点，并使，并使“先被访问的顶点的先被访问的顶点的邻接点邻接点”先于先于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问，直至图中所有已经被访问的顶点的被访问，直至图中所有已经被访问的顶点的邻接点都被访问到；邻接点都被访问到；3若图中尚有顶点未曾被访问，则另选图中一若图中尚有顶点未曾被访问，则另选图中一个未曾被访问的顶点作起点，访问该顶点，个未曾被访问的顶点作起点，访问该顶点，继续过程继续过程2，直至所有顶点被访问完毕。，直至所有顶点被访问完毕。广度优先搜索示例v2v4v1v5v3v6v7v8v
34、2v4v1v5v3v6v7v8图的遍历:广度优先搜索void BFSTraverse( Graph G， int v) for(v=0;v; v+) visitedv=0;/访问数组初始化访问数组初始化 QueueInit(Q)；/队列初始化队列初始化 for(v=0；vV2-V4-V8-V5-V6-v3-v7广度优先搜索V1-V2-V3-V4-v5-v6-v7-v8v2v4v1v5v3v6v7v8假定以邻接表存储，邻接假定以邻接表存储，邻接点按编号升序排列。遍历点按编号升序排列。遍历序列如下：序列如下：已知邻接矩阵求遍历序列深度优先搜索：V1-V2-V3-V4-V5宽度优先搜索：V1-V2-
35、V3-V4-V5已知邻接表求遍历序列V1143V2V3V4V5V6245352012345深度优先遍历：V1-V2-V3-V6-V5-V4宽度优先遍历：V1-V2-V5-V4-V3-V6图的遍历的时间复杂度w邻接矩阵为存储结构: O(n2)w邻接表为存储结构: O(n+e)w空间复杂度均为: O(n)图的连通性问题w图的连通分量w生成树和生成森林w最小生成树图的连通分量CABDEFBDEFCA调调用用两两次次DFSDFS（分分别别从从A、D出出发发），得得到到的的顶顶点点访问序列分别为：访问序列分别为：A,B,CD,E,F问题：问题：如何求出连通分量的个数如何求出连通分量的个数生成树 设设G=
36、(V，E)是个连通图，则从图中任一顶点出发遍历图时，必是个连通图，则从图中任一顶点出发遍历图时，必将将E(G)分成两个集合分成两个集合T(G)和和B(G)。其中。其中T(G)是遍历图时所经过的边是遍历图时所经过的边集，集，B(G)是剩余的边集。考虑图是剩余的边集。考虑图G=(V，T)，由于，由于V(G)=V(G)，E(G)E(G)，则，则G是是G的连通子图，它包括的连通子图，它包括G的的所有顶点和足以构所有顶点和足以构成一棵树的成一棵树的n-1n-1条边，称为条边，称为G的生成树的生成树v3v2v1v4v3v2v1v4v3v2v1v4v3v2v4v1生成树不唯一生成树不唯一深度和广度优先生成树
37、 采用采用DFSDFS遍历遍历图所得到的生成树称为图所得到的生成树称为深度优先生成树深度优先生成树，采用采用BFSBFS遍历遍历图所得到的生成树称为图所得到的生成树称为广度优先生成树广度优先生成树 v2v4v1v5v3v6v7v8v2v4v1v5v3v6v7v8深度优先生成树v2v4v1v5v3v6v7v8广度优先生成树深度优先（广度优先）生成树举例v1v2v3v4v5v6135204105440235124生成森林w当图中包括多个连通分量时，在遍历图时，当图中包括多个连通分量时，在遍历图时，每个连通分量是一棵生成树，生成树的不每个连通分量是一棵生成树，生成树的不相交集合形成生成森林相交集合形
38、成生成森林。生成森林算法wvoid DFSForest( Graph G, CSTree &T)w / 建立无向图建立无向图G的深度优先生成森林的（最左）孩子（右）兄弟链表的深度优先生成森林的（最左）孩子（右）兄弟链表Tw T=NULL；w for(v=0；v; +v) visitedv=FALSE；w for(v=0; vnextsibling=p; / 是其它生成树的根是其它生成树的根(前一棵的根的前一棵的根的“兄兄弟弟”)w q=p； / q 指示当前生成树的根指示当前生成树的根w DFSTree(G, v, p)； / 建立以建立以p为根的生成树为根的生成树w / ifw / DFSF
39、orest生成森林算法(续)wvoid DFSTree(Graph G, int v, CSTree &t) w/ 建立以建立以t为根生成树为根生成树w visitedv=true; first=true;w for(w=GraphFirstAdj(G,v);w;w=GraphNextAdj(G,v,w)w if(!visitedw)w p=(CSTree)malloc(sizeof(CSNode);w *p=GraphGetVertex(G,w),null,null;w if(first)w t-firstchild=p;first=false;w else q-nextsibling=p;
40、w q=p;w DFSTree(G, w, q)/w w/ DFSTree最小生成树 w实际问题实际问题：假设连通图假设连通图G的顶点表示城市，边表示连接两的顶点表示城市，边表示连接两个城市之间的通信线路。若有个城市之间的通信线路。若有n个城市，连接这个城市，连接这n个城市最少个城市最少需需n-1条边，则图的生成树就表示所有可行的通信线路。条边，则图的生成树就表示所有可行的通信线路。 w最最小小生生成成树树：n个个顶顶点点网网络络的的生生成成树树有有n个个结结点点，n-1条条分分枝枝。假假设设网网络络中中有有m条条边边(mn-1)，用用MST表表示示许许多多可可能能的的生生成成树树的的集集合合
41、，每每棵棵树树中中n-1条条分分枝枝上上的的权权之之和和用用WG(T)表示，则使得表示，则使得WG(Tmin)=MinWG(T)|TMST的生成树的生成树Tmin便是网络的便是网络的最小生成树最小生成树。 w算法算法：Prim算法算法和和Kruskal算法算法MST性质性质假设假设N=（V，E）是一个连通网，）是一个连通网，U是顶点集是顶点集V的一个非空子集。若（的一个非空子集。若（u，v）是一条具有最小权值的边，其中是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边（，则必存在一棵包含边（u，v）的最小生成树的最小生成树。用反证法证明用反证法证明Prim算法 w算法思想算法思想：假
42、设假设N=(V，|E|)是连通图，是连通图，TE是是N上最小生成树中边的集合。算法从上最小生成树中边的集合。算法从U=u0(u0V)，TE=开始，重复执行下述开始，重复执行下述操作：在所有操作：在所有uU，vVU的的边边(u,v)中找一条代价最小的边中找一条代价最小的边(u0,v0)并入集合并入集合TE，同时同时v0并入并入U，直至直至U=V为止。此时，为止。此时，TE中必有中必有n-1条边，则条边，则T=(V，TE)为为N的的最小生成树。最小生成树。void MinSpanTree_Prime(Graph G, vertype u) / 从第从第 u个顶点出发构造网个顶点出发构造网G的最小生
43、成树的最小生成树T,输出输出T的各条边的各条边 struct verType adjvex； / 最小代价边依附的顶点最小代价边依附的顶点 VRType lowcost； / 最小代价最小代价 closedgeMAXNODE； k=GraphLocateVertex(G, u)； for(j=0；j；j+) if(j!=k) closedgej=u, kj.adj/ adjvex, lowcost closedgek.lowcost=0； / 初始初始 U=u for(i=1；i；i+) k=minnum(closedge)； / 表示求出表示求出T的下一个结点的第的下一个结点的第k个顶点个顶
44、点 printf(closedgek.adjvex, k)； closedgek.lowcost=0； / 第第k个顶点并入个顶点并入U集集 for(j=0；j；j+) if(kj.adjclosedgej.lowcost) closedgej=k, kj.adj； / for / MinSpanTree_ Prime最小生成树举例最小生成树举例v2v4v1v5v3v616211114336191865v2v4v1v5v3v6iv2v4v1v5v3v616211114336191865closedgeAdjvexlowcostAdjvexlowcostAdjvexlowcostAdjvexlo
45、wcostAdjvexlowcostiAdjvexlowcost2345UVU1v116v119v121v1v2,v3,v4,v5,v6v3,v4,v5,v6v1,v20v25v26v119v211v1,v2,v3v4,v5,v600v26v119v211v1,v2,v3,v4v5,v6000v418v211v1,v2,v3,v4,v6v5000v4180v1,v2,v3,v4,v6,v500000Kruskal 算法v2v4v1v5v3v616211114336191865试画出从顶点v1开始利用Prim算法得到的最小生成树V2V3V1V4V58112102549利用Kruskal算法得到的
46、最小生成树1235461425483234567最小生成树最小生成树wPrim算法时间复杂度为O(n2),适用于稠密图。wKruskal算法时间复杂度为O(eloge),适用于稀疏图。有向无环图 及应用w有向无环图的定义有向无环图的定义无环的有向图叫有向无环图，简称无环的有向图叫有向无环图，简称DAG图。图。w用用DAG图描述带公共子式的表达式图描述带公共子式的表达式(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e)w有向图中是否有环的检查有向图中是否有环的检查w有向无环图的应用有向无环图的应用: :l 工程能否顺利进行工程能否顺利进行拓扑排序拓扑排序l 估算完成工程的最短时间估
47、算完成工程的最短时间关键路径关键路径拓扑排序 w拓扑排序拓扑排序是对有向无环图的顶点的一种排序 。w概念：概念：nAOV网络网络：若有向图中，顶点表示活动或任务，边：若有向图中，顶点表示活动或任务，边表示活动或任务间的优先关系，则此有向图称为顶表示活动或任务间的优先关系，则此有向图称为顶点表示活动的网络，即点表示活动的网络，即AOV-网络网络 n拓扑有序：拓扑有序：在在AOV网络中，若将顶点排成一个序列，网络中，若将顶点排成一个序列，若顶点若顶点i到顶点到顶点j有路径，序列中顶点有路径，序列中顶点i就排在顶点就排在顶点j的的前面，则称此序列为拓扑有序。前面，则称此序列为拓扑有序。 n拓扑排序拓
48、扑排序：构造拓扑有序的操作称拓扑排序。：构造拓扑有序的操作称拓扑排序。拓扑排序 w对对V V进行进行拓扑排序，拓扑排序，直观上说，就是直观上说，就是将将V V的顶点排成一个序列，的顶点排成一个序列，V Vi1i1,V,Vi2i2,V,Vinin( (其中其中i i1 1,i,i2 2,i,in n是是1,2,n1,2,n的一种排列。的一种排列。) )且使得任何且使得任何V A, A,则在序列中则在序列中V Vikik排在排在V Vijij之前之前。拓扑排序 课程编号 课程名称先修课程C1程序设计导论无C2高等数学无C3程序设计基础C1、C2C4离散数学C2、C3C5数据结构C3、C4C6高级语
49、言程序设计C3C7编译原理C5、C6C8操作系统C5、C10C9普通物理C2C10计算机原理C9表示教学计划（课程之间）的优先关系有向图表示教学计划（课程之间）的优先关系有向图拓扑排序 C1C2C6C5C3C4C8C10C9C7拓扑排序的方法 AOVAOV网进行拓扑排序的网进行拓扑排序的方法和步骤方法和步骤是：是：w在在网网络络中中选选一一个个没没有有前前驱驱顶顶点点的的顶顶点点，且输出；且输出；w从从网网络络中中删删去去该该顶顶点点，且且同同时时删删去去以以该该顶点为尾的所有有向边；顶点为尾的所有有向边；w重重复复以以上上两两步步，直直到到没没有有可可输输出出的的顶顶点点为止。为止。w若全部
50、顶点已输出，拓扑排序成功；若全部顶点已输出，拓扑排序成功；w否则，拓扑排序失败否则，拓扑排序失败。 v2v4v1v5v3v6(a)网v2v4v1v5v3v6(b)v2v4v1v5v3v6(c)v5v2v4v1v3v6(d)v2v4v1v3v6v5(e)一个AOV-网的拓扑排序(f)v4v1v3v6v5v2TopologicalSort(AlGraph G)FindIndegree(G, indegree);/求入度求入度indegree0.vexnum-1 StackInit(S)； / 建建0入度顶点栈入度顶点栈S for(i=0; inext) k=p-adjvex； /对对i号顶点的每个
51、邻接点的入度减号顶点的每个邻接点的入度减1 if(!(-indegreek) push(S,k)/若入度为若入度为0,进栈进栈 /for / while if(count) return error； else return ok/ TopologicalSort 拓扑排序 v2v4v1v5v3v6一个AOV-网的拓扑排序v2v4v1v5v3v6V1V2V5V6V0V3V4写出有向图的所有拓扑排序，并指出应用教材中的算写出有向图的所有拓扑排序，并指出应用教材中的算法求得的是哪个序列，设邻接表的边表结点中的邻接法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。点序号是递增的。关键路径
52、关键路径w1956年，美国杜邦公司提出关键年，美国杜邦公司提出关键路径法，并于路径法，并于1957年首先用于年首先用于1000万万美圆化工厂建设，工期比原计划缩短美圆化工厂建设，工期比原计划缩短了了4个月。杜邦公司在采用关键路径个月。杜邦公司在采用关键路径法的一年中，节省了法的一年中，节省了100万美圆。万美圆。AOE网网AOE网网w用顶点表示事件，弧表示活动，弧用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有上的权值表示活动持续的时间的有向图叫向图叫AOE（ActivityOnEdgeNetwork）网）网。wAOE网常用于估算工程完成时间。网常用于估算工程完成时间。AOE网研究
53、的问题网研究的问题n完成整个工程至少需要多少时间；完成整个工程至少需要多少时间；n哪些活动是影响工程的关键。哪些活动是影响工程的关键。AOE网网术语术语n关键路径关键路径从源点到汇点的路径长度从源点到汇点的路径长度最长的路最长的路径径叫关键路径。叫关键路径。n活动开始的最早时间活动开始的最早时间e(i)n活动开始的最晚时间活动开始的最晚时间l(i)定义定义e(i)=l(i)的活动的活动叫叫关键活动关键活动。n事件开始的最早时间事件开始的最早时间ve(i)n事件开始的最晚时间事件开始的最晚时间vl(i)活动开始时间w e(i)=ve(j) l(i)=vl(k)-dut() jkai活动的最早最晚
54、时间活动的最早最晚时间n求求ve(i)和和vl(j)分两步分两步：n从从ve(0)=0开始向前递推开始向前递推nve(j)=Maxve(i)+dut()nT,1=j=n-1n其中，其中，T是所有以是所有以j为弧头的弧的集合。为弧头的弧的集合。n从从vl(n-1)=ve(n-1)开始向后递推开始向后递推nvl(i)=Minvl(j)-dut()nS,0=i=n-2n其中，其中，S是所有以是所有以i为弧尾的弧的集合。为弧尾的弧的集合。n两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。求关键路径示例v2v4v1v5v3v6v9v7v8a1=6a2=
55、4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4关键路径算法关键路径算法w（1）输入）输入e条弧条弧，建立，建立AOE网的存储结构网的存储结构w（2）从源点）从源点v0出发，令出发，令ve0=0，按拓扑有序求其余，按拓扑有序求其余各顶点的最早发生时间各顶点的最早发生时间vei（1in-1）。若拓扑排序）。若拓扑排序失败，算法终止，否则（失败，算法终止，否则（3）w（3）从汇点）从汇点vn出发，令出发，令vn-1=ven-1，按逆拓扑有，按逆拓扑有序求其余各顶点的最迟发生时间序求其余各顶点的最迟发生时间vli（2in-2）w（4）根据各顶点的）根据各顶点的ve和和v
56、l值，求每条弧值，求每条弧s的最早开始的最早开始时间时间e(s)和最迟开始时间和最迟开始时间l(s)。若有。若有e(s)=l(s)，则为关键，则为关键活动。活动。关键路径算法关键路径算法wTopologicalOrder(AlGraph G, Stack T)w FindIndegree(G, indegree)；/ 建零入度顶点栈建零入度顶点栈 Sw StackInit(T);count=0;ve0.vexnum-1=0;/ 初始化初始化w while(!StackEmpty(S)w pop(S,j);push(T,j);+count;/ j号顶点入栈并计数号顶点入栈并计数w for(j.f
57、irstarc；p；p=p-next)w k=p-adjvex； / 邻接点的入度减邻接点的入度减1w if(-indegreek=0) push(S,k)；/ 入度为零入栈入度为零入栈w if(vej+p-infovek) vek=vej+p-info；w /forw /whilew if(countnext)w k=p-adjvex；dut=p-info；w if(vlk-dutvlj) vl j=vlk-dut；w /forw for(j=0；jnext)w k=p-adjvex；dut=p-info)；w ee=vej；el=vk-dut；w tag=(ee=el) ? *： ；w p
58、rintf(j, k, dut, ee, el, tag)；/ 输出关键活动输出关键活动w / forw / CriticalPath 求关键路径注意事项求关键路径注意事项w1、只有减少关键活动的时间只有减少关键活动的时间才才可能可能缩短工期缩短工期w2、只有减少所有关键路径上共有的只有减少所有关键路径上共有的关键活动的关键活动的时间才时间才可能可能缩短工期缩短工期w3、只有在不改变关键路径的前提下只有在不改变关键路径的前提下减少关键活减少关键活动的时间才动的时间才可能可能缩短工期缩短工期w“虚活动虚活动”仅表示前后活动间的逻辑关系和指明仅表示前后活动间的逻辑关系和指明活动前进方向，其权值为活
59、动前进方向，其权值为0。顶点顶点表示城市表示城市边边表示城市间的交通联系表示城市间的交通联系权权表示此线路的长度或沿此线路运输所花的表示此线路的长度或沿此线路运输所花的时间或费用等时间或费用等源点源点路径的开始顶点路径的开始顶点终点终点路径的最后一个顶点路径的最后一个顶点问题：从某顶点出发，沿图的边到达另一顶点所问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径经过的路径中，各边上权值之和最小的一条路径最短路径最短路径用带权的有向图表示一个交通运输网，图中用带权的有向图表示一个交通运输网，图中最短路径最短路径的问题 w从某个源点到其它各顶点的最短路径从某个源点
60、到其它各顶点的最短路径: : DijkstraDijkstra 算法算法 w每一对顶点之间的最短路径每一对顶点之间的最短路径: : FloyedFloyed 算法算法 最短路径示例201531050v2v1v5v3v4v0202010301545v0-v210v0-v2-v325v0-v2-v3-v145v0-v445迪杰斯特拉(Dijkstra)算法思想v方法方法：把把V分成两组分成两组1.S：已求出最短路径的顶点的集合已求出最短路径的顶点的集合2.V-S：尚未确定最短路径的顶点集合尚未确定最短路径的顶点集合,将将V-S中顶点按最短路径递增的次序加入到中顶点按最短路径递增的次序加入到S中中基
61、本思想基本思想：按按路径长度递增的次序路径长度递增的次序来产生最短路来产生最短路径算法径算法2015031050v2v1v5v3v4v0202010301545Dijkstra Dijkstra 算法手工模拟算法手工模拟初值初值5010 45 45 1v0v25025452v0,v2v345453v0,v2,v3v1454v0,v2,v3,v1v45v0, v2, v3, v1,v4迭代迭代集合集合Sv0选择选择顶点顶点distD1D2D3D4D5Dijkstra Dijkstra 算法思想算法思想步骤步骤：（：（1）邻接矩阵）邻接矩阵arcs来表示带权的有向图，来表示带权的有向图，arcsi
62、j表表示示上的权值。若上的权值。若E，则置，则置arcsij=。S为已找到从为已找到从v出发的最短路径的终点集合，初态为空。出发的最短路径的终点集合，初态为空。（2）选择）选择vj，使得，使得Dj=minDi|viVSvj就是当前求得的一条从就是当前求得的一条从v出发的最短路径，并令出发的最短路径，并令S=Sj（3）从）从v出发到集合出发到集合V-S上任一顶点上任一顶点vk可达的最短路径，有可达的最短路径，有Dk=minDk，Dj+arcsik（4）重复（）重复（2）、（）、（3）直到）直到S=V。14321010050206030510初值初值10 30 100 30 10011260301
63、0021,24509031,2,4360451,2,4,31,2,4,3,55迭代迭代集合集合S选择选择顶点顶点arcsD2D3D4D5举例Dijkstra Dijkstra 算法算法voidShortestPath(GraphG,intv0,PathMatrixP,ShortPathTableD)/求从求从v0到其余各顶点到其余各顶点v的最短路径的最短路径for(v=0；v；v+)finalv=0；Dv=G.arcsv0v；/forDv0=0；finalv0=1；/初始化初始化,v0顶点属于顶点属于S集集Dijkstra Dijkstra 算法（续）算法（续）/开始主循环开始主循环,每次求得
64、每次求得v0到某个顶点的最短路经到某个顶点的最短路经,并将并将v加入到加入到S集集for(i=1；iGvexnum；i+)min=INTMAX；/当前所知离当前所知离v0顶点的最近距离顶点的最近距离for(w=0；wGvexnum；w+)if(!finalw)if(Dwmin)v=w；min=Dw；/w离离v0最近最近finalv=1；/离离v0最近的最近的v加入到加入到S集集for(w=0；wGvexnum；w+)/更新当前最短路径及距离更新当前最短路径及距离if(!finalw&(min+G.arcsvwDw)Dw=min+G.arcsvw；/修改修改Dw和和PwwVS/if/for/Sh
65、ortestPath v方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n)v方法二：弗洛伊德(Floyd)算法每一每一对顶点之点之间的最短路径的最短路径算法思想：算法思想：逐个顶点试探法逐个顶点试探法求最短路径步骤求最短路径步骤初始时设置一个初始时设置一个n阶方阵，令其对角线元素为阶方阵，令其对角线元素为0，若存，若存在弧在弧，则对应元素为权值；否则为则对应元素为权值；否则为 逐步试着在原直接路径中增加中间顶点，若加入逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值中间点后路径变短，则修改之；否则，维持原值所有顶点试探完毕，算
66、法结束所有顶点试探完毕，算法结束(1)(1)首先考虑从首先考虑从i i到到j j是否有以顶点是否有以顶点0 0为中间点的路径：为中间点的路径：i,0, ji,0, j，即即G G中是否有边中是否有边和和，若有则新路径，若有则新路径i,0,ji,0,j的长度是的长度是Cj-10Cj-10和和C0j-1C0j-1之和，比较路径之和，比较路径i,ji,j和和i,0,ji,0,j的长度，以的长度，以较短者为当前所求得的最短路径。该路径是中间点序号不大于较短者为当前所求得的最短路径。该路径是中间点序号不大于0 0的最短路径。的最短路径。(2)(2)其次考虑从其次考虑从i i到到j j是否有以顶点是否有以
67、顶点1 1为中间点的路径：为中间点的路径：i,1, i,1, , j, j，若没有则当前最短路径仍是（，若没有则当前最短路径仍是（1 1）所求得的，若有则新）所求得的，若有则新路径路径i,1, , ji,1, , j可分解为可分解为i,1i,1和和1,j 1,j ，将这两条路径，将这两条路径长度相加就得到长度相加就得到i,1, , ji,1, , j的长度，将该长度和前一次求出的长度，将该长度和前一次求出的长度，以较短者为当前所求得的最短路径。该路径是中间点的长度，以较短者为当前所求得的最短路径。该路径是中间点序号不大于序号不大于1 1的最短路径。的最短路径。（3 3）依次类推，直到考虑了顶点
68、）依次类推，直到考虑了顶点n n1 1加入当前的从加入当前的从i i到到j j最短路最短路径后，选出从径后，选出从i i到到j j的中间顶点序号不大于的中间顶点序号不大于n n1 1的最短路径。至此的最短路径。至此以考虑了所有顶点作为中间顶点的可能性，因此它必是从以考虑了所有顶点作为中间顶点的可能性，因此它必是从i i到到j j的的最短路径。最短路径。FLOYD算法wvoid ShortestPath_Floyed (Graph G, PathMatrix P , DistanceMatrix D)w /用用Floyed 算法求有向图算法求有向图G中各对顶点中各对顶点v和和w之间最短路经之间最
69、短路经w /Pvw,及其带权路径长度及其带权路径长度Dvw。若。若Pvwu为真，为真，w /则则u是从是从v到当前求得最短路经上的顶点到当前求得最短路经上的顶点w for(v=0；v；v+)w for(w=0；w；w+)w Dvw=G.arcsvw；w for(u=0；u；u+)w for(v=0；v；v+)w for(w=0；w；w+)w if(Dvu+DuwDvw) / 从从v经经u到到w一条路径更短一条路径更短w Dvw=Dvu+Duw；w /ShortestPath_Floyed6311v2v1v024Floyed算法 D(-1)0 01 12 20 04 411116 60 02 2
70、3 30 0P(-1)0 01 12 2V V0 0V V1 1V V0 0V V2 2V V1 1V V0 0V V1 1V V2 2V V2 2V V0 0 D(0)0 01 12 20 04 411116 60 02 23 37 70 0P(0)0 01 12 2V V0 0V V1 1 V V0 0V V2 2V V1 1V V0 0V V1 1V V2 2V V2 2V V0 0V V2 2V V0 0V V1 1Floyed算法 Floyed算法 D(1)0 01 12 20 04 46 66 60 02 23 37 70 0P(1)0 01 12 2V V0 0V V1 1V V
71、0 0V V1 1V V2 2V V1 1V V0 0V V1 1V V2 2V V2 2V V0 0V V2 2V V0 0V V1 1 D(2)0 01 12 20 04 46 65 50 02 23 37 70 0P(2)0 01 12 2V V0 0V V2 2V V0 0V V1 1V V2 2V V1 1V V2 2V V0 0V V1 1V V2 2V V2 2V V0 0V V2 2V V0 0V V1 103211010050206030410D(-1)=010301000500102006000 1 2 3 401234D(1)=01060301000500102006000 1 2 3 401234D(2)=010603070050010200300600 1 2 3 401234D(3)=010503070050010200300600 1 2 3 401234
