数据结构案例教程（CC++版）第2版 课件 第7章 图

第7章图导学问题11.构造最小造价通信网【问题1描述】假设要在n个城市之间建立一个通信网络，且每两个城市之间架设一条通信线路的成本不尽相同。要连通n个城市只需要架设n-1条通信线路，请设计一个施工方案使得总造价最小。导学问题22.设计一个简单的旅游交通费用查询系统【问题描述】某城市中n个旅游景点间有旅游交通线相连，所花费的代价不尽相同。请设计一个简单的旅游线路查询系统，便于游客查询从任一个景点到另一个景点之间的最少交通花费。其他问题中国主干公路网最短路径查询校园问路系统排课、运动会秩序册7.1知识学习——图的基本概念图的定义图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)G表示一个图V是图G中顶点的集合E是图G中顶点之间边的集合。如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为<vi,vj>。如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V1V2V3V4V5V1V2V3V47.1知识学习——图的基本概念在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比7.1知识学习——图的基本术语图的基本术语无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。V1V2V3V1V2V3V4含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？V1V2V3V1V2V3V47.1知识学习——图的基本术语含有n个顶点的无向完全图有n×(n-1)/2条边含有n个顶点的有向完全图有n×(n-1)条弧V1V2V3V1V2V3V47.1知识学习——图的基本术语7.1知识学习——图的基本术语图的基本术语顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。V1V2V3V4V5在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？å==niievTD12)(7.1知识学习——图的基本术语V1V2V3V4在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii==åå==11)()(nn7.1知识学习——图的基本术语7.1知识学习——图的基本术语图的基本术语权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。V1V2V3V427857.1知识学习——图的基本术语图的基本术语路径：V1V2V3V4V5一般情况下，图中的路径不惟一。V1到V4的路径：V1V4

V1V2V3V4V1V2V5V3V47.1知识学习——图的基本术语图的基本术语路径长度：非带权图——路径上边的个数带权图——路径上各边的权之和V1V2V3V4V5V1V4：长度为V1V2V3V4：长度为V1V2V5V3V4：长度为1347.1知识学习——图的基本术语图的基本术语路径长度：非带权图——路径上边的个数带权图——路径上各边的权之和V1V4：长度为V1V2V3V4：长度为V1V2V5V3V4：长度为V1V2V3V4V525632887157.1知识学习——图的基本术语图的基本术语回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。V1V2V3V4V5V1V2V3V47.1知识学习——图的基本术语图的基本术语子图：若图G=（V，E），G'=（V'，E'），如果V'

V

且E'

E，则称图G'是G的子图。V1V2V3V4V5V1V2V3V4V5V1V3V47.1知识学习——图的基本术语图的基本术语连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。1.含有极大顶点数；2.依附于这些顶点的所有边。如何求得一个非连通图的连通分量?连通分量1

V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量2连通分量是对无向图的一种划分。7.1知识学习——图的基本术语7.1知识学习——图的基本术语图的基本术语强连通图：在有向图中，对图中任意一对顶点vi和vj

(i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。如何求得一个非连通图的连通分量?V1V2V3V4强连通分量1

强连通分量2V1V3V4V27.1知识学习——图的基本术语7.1知识学习——图的基本术语图的基本术语生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。多——构成回路少——不连通含有n-1条边如何理解极小连通子图?V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成森林7.1知识学习——图的存储结构是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。7.1知识学习——图的存储结构1.邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：arcs[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它7.1知识学习——图的存储结构1.邻接矩阵（数组表示法）类型定义：enumGraphType{DG,UG,DN,UN};typedefcharVertexType;typedefstruct{ VertexTypevexs[MAX];//顶点表 intarcs[MAX][MAX];//邻接矩阵 intvexnum,arcnum;

//顶点数和边数 GraphTypekind;//图的类型}MGraph;无向图的邻接矩阵的特点？无向图的邻接矩阵V1V3V4V2V1V2V3V4vexs=0101101101001100arcs=V1V2V3V4V1V2V3V4主对角线为0且一定是对称矩阵。7.1知识学习——图的存储结构如何求顶点i的度？V1V3V4V2V1V2V3V4vexs=0101101101001100arcs=V1V2V3V4V1V2V3V4邻接矩阵的第i行（或第i列）非零元素的个数。无向图的邻接矩阵7.1知识学习——图的存储结构如何判断顶点i和j之间是否存在边？V1V3V4V2V1V2V3V4vexs=0101101101001100arcs=V1V2V3V4V1V2V3V4测试邻接矩阵中相应位置的元素arcs[i][j]是否为1。无向图的邻接矩阵7.1知识学习——图的存储结构如何求顶点i的所有邻接点？V1V3V4V2V1V2V3V4vexs=0101101101001100arcs=V1V2V3V4V1V2V3V4将数组中第i

行元素扫描一遍，若arcs[i][j]为1，则顶点j

为顶点i的邻接点。无向图的邻接矩阵7.1知识学习——图的存储结构V1V2V3V4V1V2V3V4vexs=0110000000011000arcs=V1V2V3V4V1V2V3V4有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。有向图的邻接矩阵7.1知识学习——图的存储结构V1V2V3V4V1V2V3V4vexs=0110000000011000arcs=V1V2V3V4V1V2V3V4如何求顶点i的出度？邻接矩阵的第i行元素之和。有向图的邻接矩阵7.1知识学习——图的存储结构V1V2V3V4V1V2V3V4vexs=0110000000011000arcs=V1V2V3V4V1V2V3V4如何求顶点i的入度？邻接矩阵的第i列元素之和。有向图的邻接矩阵7.1知识学习——图的存储结构V1V2V3V4V1V2V3V4vexs=0110000000011000arcs=V1V2V3V4V1V2V3V4如何判断从顶点i到顶点j是否存在边？测试邻接矩阵中相应位置的元素arcs[i][j]是否为1。有向图的邻接矩阵7.1知识学习——图的存储结构网图的邻接矩阵可定义为：

arcs[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V1V2V3V42785025∞∞0∞

∞

∞

∞087∞∞0arcs=7.1知识学习——图的存储结构7.1知识学习——图的存储结构无向网的邻接矩阵构造voidCreateMGraph(MGraph&G){

inti,j,va,vb; G.kind=UG;

cout<<"请输入图的顶点数：";

cin>>G.vexnum;

cout<<"请输入图的边数：";

cin>>G.arcnum;

cout<<"请输入顶点的信息："; for(i=0;i<G.vexnum;i++)

cin>>G.vexs[i];

for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) G.arcs[i][j]=0; cout<<"请输入边的信息：";

for(i=0;i<G.arcnum;i++)

{

cin>>va>>vb;G.arcs[va][vb]=1;G.arcs[vb][va]=1;}}7.1知识学习——图的存储结构1.邻接矩阵（数组表示法）图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？假设图G有n个顶点e条边，则存储该图需要O(n2)。7.1知识学习——图的存储结构V1V3V4V2将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表103∧23∧1∧01∧V1V2

V3V401232.邻接表7.1知识学习——图的存储结构datafirstedge顶点表结点data：数据域，存放顶点信息。

firstedge：指针域，指向边表中第一个结点。

typedefstruct{

VertexTypedata;

EdgeListfirstedge;}VexNode;103∧23∧1∧01∧V1V2

V3V401237.1知识学习——图的存储结构边表结点adjvex：邻接点域，边的终点在顶点表中的下标next：指针域，指向边表中的下一个结点typedefstructEdgeNode{

intadjvex;

EdgeNode*next;}*EdgeList;adjvexnext103∧23∧1∧01∧V1V2

V3V40123V1V3V4V2无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。103∧23∧1∧01∧V1V2

V3V40123V1V3V4V2如何求顶点i的度？顶点i的边表中结点的个数。无向图的邻接表103∧23∧1∧01∧V1V2

V3V40123如何判断顶点i和顶点j之间是否存在边?测试顶点i的边表中是否存在终点为j的结点。V1V3V4V2无向图的邻接表103∧23∧1∧01∧V1V2

V3V40123V1V2V3V412∧3∧0∧V1V2

V3V40123∧如何求顶点i的出度？顶点i的出边表中结点的个数。有向图的邻接表V1V2V3V4如何求顶点i的入度？各顶点的出边表中以顶点i为终点的结点个数。有向图的邻接表12∧3∧0∧V1V2

V3V40123∧V1V2V3V4如何求顶点i的所有邻接点？遍历顶点i的边表，该边表中的所有终点都是顶点i的邻接点。有向图的邻接表12∧3∧0∧V1V2

V3V40123∧V1V2V3V4278521V1V2

V3V40123datafirstedge∧52∧83∧70∧网图的邻接表邻接表逆邻接表V1V2V3V412∧3∧0v1v2v3v4∧01231∧3∧0∧2∧v1v2v3v4012303∧7.1知识学习——图的存储结构邻接表的类型定义enumGraphType{DG,UG,DN,UN};//图的类型定义：有向图，无向图，有向网，无向网typedefcharVertexType;typedefstructEdgeNode//边表的结点类型{

intadjvex;//邻接点存储位置

EdgeNode*next;//指向下一个邻接点}*EdgeList;typedefstruct//顶点表的元素类型{

VertexTypedata;//顶点信息

EdgeListfirstedge;//边表的头指针}VexNode;typedefstruct{

VexNodeadjlist[MAX];//顶点表

intvexnum,arcnum;//顶点数和边数

GraphTypekind;//图的类型}ALGraph;7.1知识学习——图的存储结构邻接表的构建1.确定图的顶点个数和边的个数；2.

初始化顶点表；3.依次输入每条边创建邻接表；

3.1输入边依附的两个顶点的序号i,j；

3.2创建新结点，在表头插入；(注意无向图、无向网、有向图、有向网的区别)O(n2)O(n+e)O(n2)O(n+e)空间性能时间性能适用范围唯一性邻接矩阵邻接表稠密图稀疏图唯一不唯一图的存储结构的比较——邻接矩阵和邻接表图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。

抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。下面仅讨论从某顶点出发遍历图的算法。7.1知识学习——

图的遍历7.1知识学习——图的遍历图的遍历操作要解决的关键问题1因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历因回路而陷入死循环。解决方案：附设访问标志数组visited[n]2在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？解决方案：深度优先遍历和广度优先遍历。7.1知识学习——图的遍历1.深度优先遍历DFS(MGraphG,intv)基本思想：⑴访问顶点v；⑵从v的未被访问的邻接点中选取一个顶点i，

从i出发进行深度优先遍历；⑶重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。cout<<G.vexs[v];//访问第v个顶点visited[v]=true;//设置访问标志为1（已访问）for(inti=0;i<G.vexnum;i++)if(G.arcs[v][i]!=0&&!visited[i])

DFS(G,i);//连通图的深度优先遍历递归算法boolvisited[MAX]={false};voidDFS(MGraphG,intv){ cout<<G.vexs[v]; visited[v]=true; for(inti=0;i<G.vexnum;i++) { if(G.arcs[v][i]!=0&&!visited[i]) DFS(G,i); }}深度优先遍历7.1知识学习——图的遍历2.广度优先遍历基本思想：⑴访问顶点v；⑵依次访问v的各个未被访问的邻接点w1,w2,…,wt；⑶分别从w1，w2，…，wt出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。voidBFSTraverse(MGraphG,intv){ bool*visited=newbool[G.vexnum]; SeqQueueq;

inti,j,u; InitQueue(q); for(i=0;i<G.vexnum;i++)

visited[i]=false;

for(i=0;i<G.vexnum;i++)

{

if(!visited[i])

{

cout<<G.vexs[i]<<""; visited[i]=true; EnQueue(q,i); while(!QueueEmpty(q))

{

u=DeQueue(q); for(j=0;j<G.vexnum;j++)

{

if(G.arcs[u][j]==1&&!visited[j])

{

cout<<G.vexs[j]<<"";

visited[j]=true;

EnQueue(q,j); } } } } } delete[]visited;}广度优先遍历图的遍历算法的应用无向图的连通性的判断要想判定一个无向图是否为连通图，或有几个连通分量，通过对无向图遍历即可得到结果。连通图：仅需从图中任一顶点出发，进行深度优先搜索（或广度优先搜索），便可访问到图中所有顶点。非连通图：需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。7.1知识学习——最小生成树有向图的连通性的判断⑴从某顶点出发进行深度优先遍历，并按其所有邻接点都访问（即出栈）的顺序将顶点排列起来。⑵从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历。若不能访问到所有顶点，则从余下的顶点中最后访问的那个顶点出发，继续作逆向的深度优先遍历，直至有向图中所有顶点都被访问到为止。⑶每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集。（a）深度优先生成树（b）广度优先生成树V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V87.1知识学习——最小生成树7.1知识学习——最小生成树由深度优先遍历得到的为深度优先生成树，由广度优先遍历得到的为广度优先生成树。一个连通图的生成树可能不唯一，由不同的遍历次序、从不同顶点出发进行遍历都会得到不同的生成树。对于非连通图，通过图的遍历，将得到的是生成森林。7.1知识学习——最小生成树生成树的代价：设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？7.1知识学习——最小生成树

U={A}V-U={B,C,D,E,F}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)022(C)053(D)044(E)0INFINIT5(F)0INFINITU={A,B}V-U={C,D,E,F}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)022(C)053(D)044(E)0INFINIT5(F)0INFINIT04511U={A,B,C}V-U={D,E,F}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)002(C)143(D)044(E)155(F)0INFINIT33022U={A,B,C,E}V-U={D,F}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)002(C)103(D)044(E)235(F)2INFINIT104U={A,B,C,E,F}V-U={D}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)002(C)103(D)044(E)205(F)410U={A,B,C,E,F,D}V-U={}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)002(C)103(D)044(E)205(F)400Prim算法的关键：如何找到连接U和V-U的最短边。可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。Prim算法Prim算法引入一个辅助数组miniedges[]，用于存放集合V

U中的各顶点到集合U中顶点的最小交叉边及其权值，miniedges[]数组的元素类型定义如下：typedefstruct{VertexTypevex; floatlowcost; }Edge;

1.初始化辅助数组miniedges[]；2.输出顶点v，将顶点v加入集合U中；3.重复执行下列操作n-1次

3.1选取出权值最小的候选交叉边，取对应的顶点序号k；3.2将顶点k加入集合U中；

3.3调整数组miniedges[]；Prim算法Kruskal算法Kruskal算法基本思想：设无向连通网为G＝(V,E)，令G的最小生成树为T＝(U,TE)，其初态为U＝V，TE＝{}，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路。如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。连通分量＝{A},{B},{C},{D},{E},{F}Kruskal算法342465713ABEDCF5ABEDCF连通分量＝{A},{B},{C},{D},{E,F}Kruskal算法342465713ABEDCF5ABEDCF1连通分量＝{A,B},{C},{D},{E,F}Kruskal算法342465713ABEDCF5ABEDCF12连通分量＝{A,B},

{D},{C,E,F}Kruskal算法342465713ABEDCF5ABEDCF123连通分量＝{A,B,D},{C,E,F}Kruskal算法342465713ABEDCF5ABEDCF1234连通分量＝{A,B,C,D,E,F}Kruskal算法342465713ABEDCF5ABEDCF123441.初始化：U=V；TE={}；2.循环直到T中的连通分量个数为12.1在E中寻找最短边(u，v);2.2如果顶点u、v位于T的两个不同连通分量，则

2.2.1将边(u，v)并入TE；

2.2.2将这两个连通分量合为一个；

2.3在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；Kruskal算法7.1知识学习——最短路径在非网图中，最短路径是指两顶点之间经历的边数最少的路径。在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。7.1知识学习——最短路径单源点最短路径问题

问题描述：给定带权有向图G＝(V,E)和源点v∈V，求从v到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。BAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)100Dijkstra算法AEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)100Dijkstra算法BAEC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)90Dijkstra算法BDAE105030101002060S={A,B,

D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60Dijkstra算法BDCA105030101002060S={A,B,

D,

C,E}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,D,C,E)60Dijkstra算法BDCE图的存储结构：带权的邻接矩阵存储结构数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。数组path[n]：保存从源点到各顶点的。path[i]中保存了从源点到终点vi的最短路径上该顶点的前驱顶点的序号。数组s[n]：记录已求出最短路径的顶点集合S，s[i]为true表示顶点vi已在集合S中。Dijkstra算法1.初始化数组dist、path和s；2.while(s中的元素个数<n)2.1在dist[n]中求最小值，其下标为k；

2.2将顶点vk添加到数组s中；

2.3修改数组dist和path；

Dijkstra算法——伪代码每一对顶点之间的最短路径问题描述：给定带权有向图G＝(V,E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。方法1：每次以一个顶点为源点，调用Dijkstra算法n次。显然，时间复杂度为O(n3)。方法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。04116023∞0有向网图邻接矩阵acb346112Floyd算法acb346112dist-1

=04116023∞0path-1

=

abacbabcca初始化Floyd算法acb346112dist-1

=04116023∞0path-1

=

abacbabcca第1次迭代dist0

=0411602370path0

=

abacbabccacab

Floyd算法acb346112第2次迭代dist0

=0411602370path0

=

abacbabccacabdist1

=046602370path1

=

ababc

babccacabFloyd算法acb346112第3次迭代dist2

=046502370path2

=

ababcbcabccacabdist1

=046602370path1

=

ababcbabccacabFloyd算法图的存储结构：带权的邻接矩阵存储结构数组D[n][n]：存放在迭代过程中求得的最短路径长度。数组path[n][n]：path[i][j]中存放的是从顶点vi到顶点vj中间顶点序号不大于k的最短路径上的顶点vi的后继顶点的序号。

设计数据结构导学问题1的实现：

导学问题1就是构造连通网的最小生成树的问题。导学问题2的实现：

导学问题2就是求两个顶点间最短路径的问题。7.2知识应用

7.3知识拓展——AOV网与拓扑排序什么AOV网？AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。AOV网中出现回路意味着什么？7.3知识拓展——AOV网与拓扑排序AOV网特点：1.AOV网中的弧表示活动之间存在的某种制约关系。2.AOV网中不能出现回路。编号课程名称先修课C1高等数学无C2计算机导论无C3离散数学C1C4程序设计C1,C2C5数据结构C3，C4C6计算机原理C2，C4C7数据库原理C4，C5，C6C1C2C3C4C6C5C7AOV网拓扑排序拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序。拓扑排序基本思想：⑴从AOV网中选择一个没有前驱的顶点并且输出；⑵从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；⑶重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。C1C2C3C4C6C5C7拓扑序列：C1,拓扑排序C2C3C4C6C5C7拓扑序列：C1,C2,拓扑排序C3C4C6C5C7拓扑序列：C1,C2,C3,拓扑排序C4C6C5C7拓扑序列：C1,C2,C3,C4,拓扑排序C6C5C7拓扑序列：C1,C2,C3,C4,C5,拓扑排序C6C7拓扑序列：C1,C2,C3,C4,C5,C6,拓扑排序C7拓扑序列：C1,C2,C3,C4,C5,C6,C7,拓扑排序设计数据结构1.图的存储结构：宜采用邻接表存储。2.为便于算法执行过程中考察每个顶点的入度，即查找没有前驱的顶点，可引入一个存放各顶点入度的数组indegree[]。3.为了避免每一步选入度为0的顶点时重复扫描数组indegree，可设置一个队列（或栈）来存储所有入度为0的顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为0的顶点都排入队列中，一旦排序过程中出现新的入度为0的顶点，也同样将其排入队列中。

(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedgeA

B

C

D

E

F

G∧

2

4

5

4∧

6∧ABGDEF拓扑排序C

3

4

6∧

5∧

4∧

6∧

3(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedge0A0B1C2D4E2F

3

G∧

2

4

5

4∧

6∧ABGDEF拓扑排序C

3

4

6∧

5∧

4∧

6∧

3AB(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedge0A0B1C2D4E2F

3

G∧

2

4

5

4∧

6∧ABGDEF拓扑排序C

3

4

6∧

5∧

4∧

6∧

3132AB(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedge0A0B1C1D3E2F

2

G∧

2

4

5

4∧

6∧BGDEF拓扑排序C

3

4

6∧

5∧

4∧

6∧

3021BAC(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedge0A0B0C1D2E1F

2

G∧

2

4

5

4∧

6∧GDEF拓扑排序C

3

4

6∧

5∧

4∧

6∧

301CADB(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedge0A0B0C0D1E1F

2

G∧

2

4

5

4∧

6∧GDEF拓扑排序

3

4

6∧

5∧

4∧

6∧

30DAEBC(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedge0A0B0C0D0E1F

2

G∧

2

4

5

4∧

6∧GEF拓扑排序

3

4

6∧

5∧

4∧

6∧

31EAFBCD0(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedge0A0B0C0D0E0F

1

G∧

2

4

5

4∧

6∧GF拓扑排序

3

4

6∧

5∧

4∧

6∧

3FAGBCD0E(a)一个AOV网(b)AOV网的邻接表存储0123456

indgreevertexfirstedge0A0B0C0D0E0F

0

G∧

2

4

5

4∧

6∧G拓扑排序

3

4

6∧

5∧

4∧

6∧

3GABCDEF1.队列s初始化；累加器c初始化；2.扫描顶点表，将没有前驱的顶点入队；3.当队列s非空时:

3.1顶点i出队，并输出；累加器加1；

3.2将顶点i的各个邻接点的入度减1；

3.3将新的入度为0的顶点入队；4.if(c<图的顶点个数)输出“有回路”信息；拓扑排序算法——伪代码事件事件含义

v1开工

v2

活动a1完成，活动a4可以开始

v3活动a2完成，活动a5可以开始

…………v9活动a10

和a11完成，整个工程完成v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=47.3知识拓展——AOE网与关键路径v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=47.3知识拓展——AOE网与关键路径AOE网可以回答下列问题：1.完成整个工程至少需要多少时间?2.为缩短完成工程所需的时间,应当加快哪些活动?v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=47.3知识拓展——AOE网与关键路径从始点到终点的路径可能不止一条，只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的最短时间取决于从始点到终点的最长路径长度，即这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。关键路径：在AOE网中，从始点到终点