数据结构教程与题解 (6)

1、第6章 图6.1 图的概念图的概念6.2 图的存储图的存储6.3 图的遍历图的遍历6.4 生成树生成树6.5 最小生成树最小生成树6.6* 最短路径最短路径6.7 有向无环图及其应用有向无环图及其应用结点之间关系任意，任何两点之间都可能相关，每个结点可有多结点之间关系任意，任何两点之间都可能相关，每个结点可有多个前趋和多个后继个前趋和多个后继(多对多多对多)。所有数据结构中最一般的形式，树。所有数据结构中最一般的形式，树形结构、线性结构和集合都可看成形式受限的图。形结构、线性结构和集合都可看成形式受限的图。 不考虑：不考虑：混和图混和图(有向有向+无向无向)；自循环边；自循环边；重复边；重复边

2、；6.1 图的概念图图(Graph)由若干顶点与若干边构成，准确定义：图由若干顶点与若干边构成，准确定义：图G由两个集合由两个集合V和和E组成，记为组成，记为G=(V, E)，其中，其中V是是顶点顶点(Vertex)的有穷非空集合，的有穷非空集合，E是是边边(Edge)的有穷集，边是的有穷集，边是V中顶点的偶对。中顶点的偶对。无向图无向图(Undigraph或或Undirected Graph)：所有边没有方向。：所有边没有方向。无向边用圆括号表示：无向边用圆括号表示：(vi, vj)。有向图有向图(Digraph或或Directed Graph)：所有边有方向。：所有边有方向。有向边用尖括号

3、表示：有向边用尖括号表示：。有向边也称为有向边也称为弧弧，起点称为弧尾，终点称为弧头。，起点称为弧尾，终点称为弧头。V0V1V2G1=V1=v0, v1, v2, v3, v4E1=(v0, v1), (v0, v3), (v1, v2), (v1, v4), (v2, v3), (v2, v4)V0V4V3V1V2G2=V2=v0, v1, v2, v3E2=,对无向边对无向边(vi, vj)，称顶点，称顶点vi和和vj互为互为邻接点邻接点(Neighbors)，或称或称vi和和vj相相邻接邻接(Adjacent)；对有向边对有向边，称顶点，称顶点vi邻接到邻接到vj，顶点，顶点vj邻接于邻

4、接于vi，或者称，或者称vj是是vi的的邻接点邻接点。不论边是否有向，都称该边不论边是否有向，都称该边关联关联(Incident)于两个端点，或称该边与于两个端点，或称该边与两个端点相关联。两个端点相关联。 完全图完全图：任两顶点之间均有边相连。：任两顶点之间均有边相连。无向完全图无向完全图(Undirected Complete Graph)：有：有n(n1)/2条边条边有向完全图有向完全图(Directed Complete Graph)：有：有n(n1) 条边条边完全图具有最多边数完全图具有最多边数无向图，无向图，0 e n(n1)/2；有向图，；有向图，0 e n(n1)。稀疏图稀疏图

5、(Sparse Graph)：边数远远小于：边数远远小于n2(即即en2)。稠密图稠密图(Dense Graph)：e接近接近n2，即无向图接近，即无向图接近n(n1)/2，有向图接近，有向图接近n(n1)。012142530度度(Degree)：关联于顶点的边的数目，记为：关联于顶点的边的数目，记为D(v)。入度入度(Indegree)：有向图中以顶点：有向图中以顶点v为终点的边的数目，记为为终点的边的数目，记为ID(v)；出度出度(Outdegree)，以顶点以顶点v为始点的边的数目，记为为始点的边的数目，记为OD(v)；有向图顶点的度等于入度和出度之和，即有向图顶点的度等于入度和出度之和

6、，即D(v)=ID(v)+OD(v)。有向边有向边也称为也称为vi的的出边出边或或vj的的入边入边。所有顶点度数之和等于边数的所有顶点度数之和等于边数的2倍：倍：D(v)=2e 对图对图G=(V,E)，从，从V中选出若干顶点组成子集中选出若干顶点组成子集V ，从，从E中选出与中选出与V 中顶点相关联的若干边组成子集中顶点相关联的若干边组成子集E ，则，则G =(V ,E )也是一个图，也是一个图，称其为称其为G的的子图子图(Subgraph)E 中边的端点要在中边的端点要在V 中中子图可多个子图可多个子图子图若图中存在顶点序列若图中存在顶点序列v1,v2,vk，使得，使得(vi,vi+1) E

7、，或，或 E（i=1,2,k-1), 则称该序列是从顶点则称该序列是从顶点v1到顶点到顶点vk的的一条一条路径路径(Path)，或称顶点，或称顶点v1到到vk有路径有路径 ；若若v1=vk，则称该序列为，则称该序列为回路回路或或环环(Cycle)。路径长度路径长度定义为该路径上边的数目。定义为该路径上边的数目。：ABAB简单路径简单路径1条条若一条路径上除了起点和终点可以相同外，其余顶点均不相同，若一条路径上除了起点和终点可以相同外，其余顶点均不相同，则称此路径为一条则称此路径为一条简单路径简单路径。起点和终点相同的简单路径称为起点和终点相同的简单路径称为简单回路简单回路或或简单环简单环。 连

8、通图连通图(Connected Graph)：任意两个不同顶点都连通。：任意两个不同顶点都连通。连通分量连通分量(Connected Component)：无向图的极大连通子图：无向图的极大连通子图连通图至少连通图至少n1条边；强通图至少条边；强通图至少n条边条边(或或0，只有，只有1个点时个点时)连通图的连通分量只一个，即自身，非连通有多个连通分量。连通图的连通分量只一个，即自身，非连通有多个连通分量。 强连通图强连通图：在有向图中，若任意两个不同的顶点：在有向图中，若任意两个不同的顶点vi和和vj，都存在，都存在从从vi到到vj以及从以及从vj到到vi的路径。的路径。强连通分量强连通分量：

9、有向图的极大强连通子图。：有向图的极大强连通子图。 网络网络（Network）：每条边赋权的图。：每条边赋权的图。权是有某种意义的数，如表示两点间的距离、耗费等。权是有某种意义的数，如表示两点间的距离、耗费等。有时顶点也可赋权。有时顶点也可赋权。 12546312543633181465162111331814651619带权无向图带权无向图带权有向图带权有向图96.2 图的存储以下约定：以下约定：顶点的编号从顶点的编号从1 1开始，数组下标从开始，数组下标从1 1开始使用。开始使用。 如何存储图？如何存储图？任一顶点都可能多个前趋、多个任一顶点都可能多个前趋、多个后继，无法通过顶点的存储次序

10、后继，无法通过顶点的存储次序反映逻辑关系，必须显式地存储反映逻辑关系，必须显式地存储顶点间的关系顶点间的关系(即边即边)信息。信息。 (1)值值(内容内容)(2)关系关系 如何表示关系？如何表示关系？邻接矩阵邻接矩阵(Adjacency Matrix)：表示顶点间邻接关系的：表示顶点间邻接关系的n阶矩阵阶矩阵: 0 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 0 0 01 0 0 06.2.1 邻接矩阵表示中的边。不是或若：中的边；是或若：G)(Ev,v)v,v( 0G)(Ev,v)v,v( 1jAi,jijijiji对称对称?多少多少1？度度=？对称？

11、对称？多少多少1？度度=?0 1 0 1 00 1 0 1 01 0 1 0 11 0 1 0 10 1 0 1 10 1 0 1 11 0 1 0 01 0 1 0 00 1 1 0 00 1 1 0 01 2 3 4 512345出度出度=?入度入度=?顺序储存？顺序储存？链式储存？链式储存？。或若：或；或若：G)(Ev,v)v,v( 0G)(Ev,v)v,v( wjAi,jijijijiij062400600530200705457051030506005160A362465327545751356516A406246053207545705135065160A5对网络：对网络：较常用较

12、常用3652157546无向图无向图有向图有向图邻接矩阵对称邻接矩阵对称不一定不一定邻接矩阵中邻接矩阵中1 1的个数的个数2e2ee eD(iD(i) )i i行行( (或或i i列列) )中中1 1的个数的个数ID(iID(i) )i i列中列中1 1的个数的个数OD(iOD(i) )i i行中行中1 1的个数的个数D(iD(i) ) i i列列 i i行中行中1 1的个数的个数判断两点是否有边判断两点是否有边(vi,vj(vi,vj) )或或vi,vj ，看矩阵元素，看矩阵元素Ai,jAi,j 是否是否为零为零 增、删边，只要修改对应的矩阵元素增、删边，只要修改对应的矩阵元素 找某点的邻接

13、点，只需检查矩阵对应行上的非零元。找某点的邻接点，只需检查矩阵对应行上的非零元。 增、删顶点，则增、删矩阵中对应的行与列。增、删顶点，则增、删矩阵中对应的行与列。 邻接矩阵一般用二维数组实现，但它只只表示了顶点间的相邻关邻接矩阵一般用二维数组实现，但它只只表示了顶点间的相邻关系，要完整地表示一个图，还要表示顶点本身的信息，这可另设系，要完整地表示一个图，还要表示顶点本身的信息，这可另设一个顺序表来完成。一个顺序表来完成。 const int nmax=100; /顶点数最大值，假设顶点数最大值，假设为为100typedef struct datatype datanmax+1;/顶点信息表，顶

14、点信息表，0号单号单元不用元不用 mattype adjmatnmax+1nmax+1; /邻接矩阵，邻接矩阵，0行行0列不用列不用 int n,e;/顶点数和边数顶点数和边数 mat_graph;S(n)=O(n2)，适合稠密图，适合稠密图例例6.2.2 邻接表表示邻接表邻接表(Adjacency List)：每个顶点的邻点作成单链表。每个头结点两：每个顶点的邻点作成单链表。每个头结点两个域：顶点数据、链表头指针；所有头结点顺序存放。个域：顶点数据、链表头指针；所有头结点顺序存放。类似于树的孩子链表类似于树的孩子链表头结点数组称头结点数组称顶点表顶点表邻接表称邻接表称边表边表下标下标 dat

15、a first边表边表(2e) 顶点表顶点表(n) V11V22V33V44V55m21212no next4334553例例有向图的邻接表称作有向图的邻接表称作出边表出边表逆邻接表逆邻接表：邻接表记录顶点的入边，称：邻接表记录顶点的入边，称入边表入边表逆邻接表逆邻接表 入边表入边表(e) 邻接表邻接表 出边表出边表(e) V11V22V33V44m2413V11V22V33V44m4113例例邻接表和逆邻接表可以组合起来邻接表和逆邻接表可以组合起来(同时有入边、出边，但可区分同时有入边、出边，但可区分)混合边表混合边表(2e) V11V22V33V44m23-4 -1 41-1 -3 对网络

16、：对网络：BACD69528A1B2C3D42546384229const int nmax=100; /顶点数的最大值，假设为顶点数的最大值，假设为100typedef struct node * pointer;struct node /边表结点边表结点 int no;/邻接点域邻接点域 int weight;/权域权域pointer next;/链域链域;typedef struct datatype data;/顶点信息顶点信息 pointer first;/边表头指针边表头指针 headtype; /顶点表结点类型顶点表结点类型typedef struct headtype adjl

17、istnmax+1;/顶点表，顶点表，0号单元不用号单元不用 int n,e;/顶点数和边数顶点数和边数 lk_graph;S(n,e)=O(n+e)，适合稀疏图，适合稀疏图无向图无向图有向图有向图邻接表不唯一邻接表不唯一结点总数结点总数n n2e2en ne eD(iD(i) )i i边表结点数边表结点数逆邻接表：逆邻接表：ID(iID(i) )i i边表结点边表结点数数邻接表：邻接表：OD(iOD(i) )i i边表结点数边表结点数判断两点是否有边判断两点是否有边(vi,vj(vi,vj) )或或vi,vj ，看第，看第i i边表边表增、删边增、删边(v(vi i,v,vj j) )，修改

18、，修改i i边表边表和和j j边表边表修改修改i i边表边表找某点的邻接点，只需检查相应边表中的结点。找某点的邻接点，只需检查相应边表中的结点。 增顶点，头结点数组中增加；增顶点，头结点数组中增加；删顶点，删头结点数组、边表中所有关联边。删顶点，删头结点数组、边表中所有关联边。 6.3 图的遍历图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。点仅访问一次。深度优先遍历深度优先遍历广度优先遍历广度优先遍历为避免重复访问，设标志数组为避免重复访问，设标志数组(图中可有图中可有回路回路，访问某顶点后，访问某顶点后可能又沿某

19、些边回到该顶点可能又沿某些边回到该顶点)。可从任一点开始遍历可从任一点开始遍历 深度优先搜索深度优先搜索(Depth First Search或或DFS)：任选一点：任选一点vi为初始出发点，首为初始出发点，首先访问出发点先访问出发点vi(并标记为已访问并标记为已访问)，然后依次搜索，然后依次搜索vi的每个邻接的每个邻接点点vj，若，若vj未访问过，则以未访问过，则以vj为新出发点继续进行深度优先搜索；为新出发点继续进行深度优先搜索；依此类推，直到访问完所有和依此类推，直到访问完所有和vi有路径的顶点。有路径的顶点。 6.3.1 深度优先遍历访问出发点，再递归地访问邻接于此点的所有顶点。访问出

20、发点，再递归地访问邻接于此点的所有顶点。 V1V1 V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2例例 V1V1 V2V2 V4V4 V3V3 V8V8 V7V7 V6V6 V5V5V1,V2,V4,V8,V5,V3,V6,V7从从V1出发，出发，DFS：V1,V2,V5,V8,V4,V3,V6,V7尽可能先对纵深方向搜索：沿某分支搜索到尽头，回溯，再沿尽可能先对纵深方向搜索：沿某分支搜索到尽头，回溯，再沿另一分支搜索。另一分支搜索。DFS序列不唯一序列不唯一类似于树的先根遍历，可认为是树的先根遍历的推广。类似于树的先根遍历，可认为是树的先根遍历的推广。1V5V2V3V6

21、V4V8V7V 1V5V2V3V6V4V8V7V12349105DFS(7)67814 11DFS(1)DFS(2)DFS(4)DFS(8)DFS(5)DFS(6)DFS(3)1213void DFS(graph g,int v) 访问访问v;visitedv=1; 找出找出g中中v的一个邻接点的一个邻接点w; while(w存在存在) if(w未访问过未访问过) DFS(g,w); w=g中中v的下一个邻接点的下一个邻接点; 1234567dfs ( 1 )用栈保存用栈保存刚访问的刚访问的顶点顶点void dfs(mat_graph *g,int v) /邻接矩阵上邻接矩阵上DFS遍历遍历

22、int j; coutv” ”;visitedv=1;/访问出发点访问出发点 for(j=1;jadjmatvj=1 & !visitedj) dfs(g,j);void dfsL(lk_graph *g,int v) /邻接表上邻接表上DFS遍历遍历 pointer p; coutvadjlistv.first; while(p!=NULL) /搜索邻点，未访问则递归搜索邻点，未访问则递归 if(!visitedpno) dfsL(g,pno); p=pnext; T=O(n2)S=O(n)T=O(n+e)S=O(n)练习：在邻接表上，练习：在邻接表上，从任一点出发，从任一点出发，DFSV1

23、V8V7V6V5V4V3V21V12V23V34V45V56V67V78V824688736 3 2 72 3 51 1 45 练习：在邻接矩阵上，练习：在邻接矩阵上，从任一点出发，从任一点出发，DFS0001110001001001000101000001100000111100010001110A123456712345671 2 3 4 5 6 76.3.2 广度优先遍历广度优先搜索广度优先搜索(Breadth/Width First Search或或BFS)：任选一点：任选一点vi为初始出发为初始出发点，首先访问出发点点，首先访问出发点vi (并标记为已访问并标记为已访问)，接着依次访

24、问，接着依次访问vi的邻的邻接点接点w1,w2,wt，然后，依次访问与，然后，依次访问与w1,w2,wt邻接的所有未邻接的所有未访问过的顶点，依此类推，直到访问完所有和访问过的顶点，依此类推，直到访问完所有和vi有路径的顶点。有路径的顶点。 V1V1 V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1 V1 V2V2 V4V4 V3V3 V8V8 V7V7 V6V6 V5V5例例从从V1出发，出发，BFSV1,V2,V3,V4,V5,V6,V7,V8尽可能先横向搜索：从出发点开始，尽可能先横向搜索：从出发点开始，“一层一层一层一层”地进行搜地进行搜索。索。 BFS序列不

25、唯一序列不唯一类似于树的层次遍历，可认为是树的层次遍历的推广。类似于树的层次遍历，可认为是树的层次遍历的推广。V1,V3,V2,V7,V6,V5,V4,V81234567bfs ( 1 )练习：在邻接表上，练习：在邻接表上，从任一点出发，从任一点出发，BFS1A2B3C4D5E6F7G2111222337 7 7 6 5 54 64 1234567void BFS(graph g,int v) 初始化队列初始化队列; 访问访问v;visitedv=1; v入队入队; while(队不空队不空) v出队出队; 找找v的第一个邻接点的第一个邻接点w; while(w存在存在) if(w未访问过未访

26、问过) 访问访问w;visitedw=1; w入队入队; 求求v的下一个邻接点的下一个邻接点w; 先访问的点其邻点也先访问，先访问的点其邻点也先访问，“先进先出先进先出”，BFS算法中用队列算法中用队列保存保存已访问已访问的顶点的顶点(不能像树那样不能像树那样保存待访问点？见课本保存待访问点？见课本)1234567QV6V5V4V3V2V1V7 V8V6V5V4V3V2V1V7 V8void bfs(mat_graph *g,int v) /邻接矩阵上邻接矩阵上BFS遍历遍历 int j,n; sqqueue Q;/假设采用顺序队列假设采用顺序队列 n=gn; init_sqqueue(&Q)

27、; coutv” ”;visitedv=1;/访问出发点访问出发点 en_sqqueue(&Q,v); while(!empty_sqqueue(&Q) de_sqqueue(&Q,&v); for(j=1;jadjmatvj=1 & !visitedj) coutj” ”;visitedj=1; en_sqqueue(&Q,j); T=O(n2)S=O(n)void bfsL(lk_graph *g,int v) /邻接表上邻接表上BFS遍历遍历 sqqueue Q;/假设采用顺序队列假设采用顺序队列 pointer p; init_sqqueue(&Q); coutvadjlistv.fi

28、rst; while(p!=NULL) if(!visitedpno) coutnono=1; en_sqqueue(&Q,pno); p=pnext; T=O(n+e)S=O(n)void traver(mat_graph *g) /邻接矩阵邻接矩阵,非连通非连通,DFS int i,count; for(i=1;i=n;i+) visitedi=0;/初始化标志数组初始化标志数组 count=0; for(i=1;i=n;i+) if(!visitedi) count+;cout”第第”count”个连通分量个连通分量:”; dfs(g,i); cout新的候选边新的候选边(v, i)，则

29、以则以(v, i)作为作为i新的最短边；否则新的最短边；否则i的最短边不变。的最短边不变。 连接连接U和和VU的边有的边有k(nk)条，运算量大，重复比较条，运算量大，重复比较候选集及其调整技术候选集及其调整技术UV-UUV-UUV-UUV-Uiv置置T为任意一个顶点为任意一个顶点;求初始候选边集求初始候选边集;while(T中结点数中结点数n) 从候选边集中选取最短边从候选边集中选取最短边(u,v); 将将(u,v)及顶点及顶点v，扩充到，扩充到T中中; 调整候选边集调整候选边集;时间复杂度为时间复杂度为O(n2)，与边数无关，对稠密图有利，与边数无关，对稠密图有利 abcdegf19514

30、1827168213ae12dcbgf7148531621生成树权值和生成树权值和= 14+8+3+5+16+21 = 67从从Ua开始：开始：6.5.2 Cruskal算法1）令初始状态只有令初始状态只有n个顶点而无边的非连通图个顶点而无边的非连通图T=(V, )，T中每中每个顶点自成一个连通分量。个顶点自成一个连通分量。2）以后按长度递增顺序从以后按长度递增顺序从E中选择最短边中选择最短边(u, v)，若其端点属于，若其端点属于两个连通分量，则将其加入到两个连通分量，则将其加入到T中，中，T1和和T2同时成一个连通分量；同时成一个连通分量；若属于同一个连通分量，则舍去若属于同一个连通分量，

31、则舍去(否则成回路否则成回路)。3）依次类推，直到依次类推，直到T中所有顶点都属于同一个连通分量为止，中所有顶点都属于同一个连通分量为止，T便是便是G的一棵最小生成树。的一棵最小生成树。 按边权递增次序生成最小生成树按边权递增次序生成最小生成树 中间结果为生成森林，最后合并成一棵树中间结果为生成森林，最后合并成一棵树。 如何判断边的两个端点在同一个连通分量中？如何判断边的两个端点在同一个连通分量中？ 方法方法1：设置标志数组，记录每个顶点的：设置标志数组，记录每个顶点的连通分量连通分量号，初始时号，初始时sets i =i。以后合并。以后合并(vi, vj)时，扫描数组时，扫描数组sets，将

32、其中一个，将其中一个连通分连通分量量中的所有点的中的所有点的连通分量连通分量号改为另一个，运算量为号改为另一个，运算量为O(n)。方法方法2：各连通分量用树来记录：开始时，每个树只有一个根；各连通分量用树来记录：开始时，每个树只有一个根；合并连通分量就是合并树，将其中一个树根成为另一个树根的孩合并连通分量就是合并树，将其中一个树根成为另一个树根的孩子即可。检查两点是否同分量，则检查树根是否相同。找根的效子即可。检查两点是否同分量，则检查树根是否相同。找根的效率取决于树高。率取决于树高。V2V0V3V5V4V13 36 65 52 21 16 65 55 54 46 6下标：下标：0 1 2 3

33、 4 5 setsV2V0V3V5V4V1sets10340112352345方法方法1：集合标志数组：集合标志数组401235下标：下标：0 1 2 3 4 5 0000方法方法2：用树表示集合：用树表示集合每点设置双亲指针，以便找根每点设置双亲指针，以便找根(双亲链表双亲链表)。结点数以负数形式记录在原双亲域中，约定双亲为负则树根。结点数以负数形式记录在原双亲域中，约定双亲为负则树根。合并时令结点数少的树作另一个树的子树，可获得较小的树高，合并时令结点数少的树作另一个树的子树，可获得较小的树高，高度为高度为O(log2n)。314576231576423157642集合集合S1, S2和和

34、S3的双亲链表的双亲链表parent - -4 5 - -3 3 - -3 3 1 1 1 51 2 3 4 5 6 7 8 9 1018792105346- -4- -3- -3T=(V,);while(T中所含边数中所含边数新路径长度，即新路径长度，即DjDk+边边的权的权则将则将Dj修改为此长度。修改为此长度。 Pkj若不从若不从k直接经边直接经边到待求点到待求点j，则距离不可能变短，则距离不可能变短 vkj旧已求点集S新已求点源点待求点 x 12534209060603012534101253412534(a)(b)(c)(d)10109010901030407060103040501

35、0101253412534(e)(f)1030405010304050101010100000010源点源点1到终点最短路径取法以（到终点最短路径取法以（1，5）为例）为例:P5 = 3，P3 = 4，P4 = 1路径为：路径为：53416030V1V5V2V3V42060101090D1.n记录各点最短路径值记录各点最短路径值P1.n记录各点最短路径上的记录各点最短路径上的前趋前趋V2V3V4V5 D 40 10 50 P1413记后继？记后继？VzViVxVy6.6.2 所有点对之间最短路径所有点对所有点对(Allpairs)之间的最短路径问题是：对于给定的有向网络之间的最短路径问题是：对

36、于给定的有向网络G=(V, E)，对，对G中任意两个不同的顶点中任意两个不同的顶点v、w(vw)，找出，找出v到到w的的最短路径。最短路径。 依次取每个顶点作源点，重复执行依次取每个顶点作源点，重复执行dijkstra算法算法n次，就可求得次，就可求得每对顶点间的最短路径，时间复杂度为每对顶点间的最短路径，时间复杂度为O(n3)。Floyd算法更直接算法更直接弗洛伊德(Floyd)算法若若i到到j有边，则是有边，则是i到到j的一条路径，长度为的一条路径，长度为Aij。但不一定是最。但不一定是最短路径，可能存在中间经过其它顶点的路径。短路径，可能存在中间经过其它顶点的路径。 1）首先，考虑首先，

37、考虑i到到j是否有中间点序号是否有中间点序号不大于不大于1的最短路径：的最短路径：i, 1, j，若有，则路径长度为，若有，则路径长度为Ai1+A1j，比较路径，比较路径i, j和和i, 1, j的长度，取较短者为当前最短路径。的长度，取较短者为当前最短路径。2）其次，考虑其次，考虑i到到j是否有中间点序号是否有中间点序号不大于不大于2的最短路径：的最短路径：i,2,j，若没有，则当前最短路径不变；若有，则路径长度为，若没有，则当前最短路径不变；若有，则路径长度为路径路径i,2的长度的长度+路径路径2,j的长度，而这两条路径就是前一步的长度，而这两条路径就是前一步求出的中间点序号不大于求出的中

38、间点序号不大于1的最短路径。将新的路径长度和原来的最短路径。将新的路径长度和原来的路径长度作比较，取较短者为当前最短路径。的路径长度作比较，取较短者为当前最短路径。3）然后，考虑从然后，考虑从i到到j是否有中间点序号是否有中间点序号不大于不大于3的最短路径。的最短路径。依次类推，直到考虑到中间点序号依次类推，直到考虑到中间点序号不大于不大于n的最短路径后，便考的最短路径后，便考虑完了中间点为任何点的可能性，故最终得到虑完了中间点为任何点的可能性，故最终得到i到到j的最短路径。的最短路径。关键：关键：保留每一步求得的所有顶点对之间的当前最短路径长度。保留每一步求得的所有顶点对之间的当前最短路径长

39、度。需要需要nn的方阵序列的方阵序列Ai1.n1.n（i=0,1,n），其中），其中Akij表表示从示从i到到j中间点序号不大于中间点序号不大于k（0kn）的最短路径长度。）的最短路径长度。 A0就是就是G的邻接矩阵，的邻接矩阵，中间不经过任何点中间不经过任何点 为了得到最短路径本身，设置一个路径矩阵为了得到最短路径本身，设置一个路径矩阵path1.n1.n，它迭代产生，它迭代产生，pathkij存放存放i到到j的的中间点序号不大于中间点序号不大于k的最短路径上顶点的最短路径上顶点i的的后继后继顶点。顶点。若已知若已知Ak1，如何求，如何求Ak？中间点序号不大于中间点序号不大于k，两种可能：，

40、两种可能： 1)中间不经过中间不经过k，则，则Akij=Ak1ij2)中间经过中间经过k：i,k,j，则，则Akij=Ak1ikAk1kjA0ij=AijAkij=min(Ak1ij，Ak1ikAk1kj) 在第在第k次迭代时，次迭代时，k列列k行不变：行不变：Ak1ik、Ak1kj不需矩阵序列，可在同一个矩阵中迭代。不需矩阵序列，可在同一个矩阵中迭代。记前趋？记前趋？0600301006002090100A05432154321543215432154321path0060030100110306002090100A15432154321543211132154321path10400301

41、007030600205010400A45432134321543213132144421path412534209060603010100：11：12(无路径无路径)40：14310：1450：143520：210：2260：2330：21470：2356.7 有向无环图及其应用有向无环图有向无环图(Directed Acyclic Graph或或DAG)：无回路的有向图：无回路的有向图 描述一项工程或系统进行过程：描述一项工程或系统进行过程： （1）整个工程能否顺利进行？）整个工程能否顺利进行？（2）完成整个工程的最短时间是多少？哪些活动是影响整个）完成整个工程的最短时间是多少？哪些活动是

42、影响整个工程进度关键？工程进度关键？例例 某工程分为某工程分为V1、V2、V3、V4、V5、V6、V7子工程，工程子工程，工程流程可用如下流程可用如下AOV网表示。其中，网表示。其中，顶点：表示子工程顶点：表示子工程(活动活动)， 弧：表示子工程间的顺序关系。弧：表示子工程间的顺序关系。6.7.1 AOV网与拓扑排序顶点活动网顶点活动网(Activity On Vertex network，AOV网网)：顶点表示活动，边表示：顶点表示活动，边表示活动之间先后关系的有向图活动之间先后关系的有向图例例 课程流程图课程流程图 某校计算机专业课程流程可某校计算机专业课程流程可AOV网表示。其中，网表示

43、。其中，顶点：表示课程（活动），顶点：表示课程（活动）， 弧：表示课程间的先修关系；弧：表示课程间的先修关系；c1c2c3c4c5c6c7c8c9c10c11c12程序设计程序设计离散数学离散数学数据结构数据结构汇编语言汇编语言算法分析算法分析计算机体系计算机体系编译方法编译方法操作系统操作系统高等数学高等数学线性代数线性代数电子电路电子电路数值分析数值分析无无 c1c1,c2c1c3,c4c11c5,c3c3,c6无无c9c9c9,c10,c1课程编号课程编号 课程名称课程名称 先决条件先决条件 c4c1c2c3c12c9c10c11c6c7c8c5一个可行施工计划：一个可行施工计划：V1,

44、 V2, V3, V5, V4, V6, V7一个可行学习计划：一个可行学习计划：c1, c9, c4, c2, c10, c11, c12, c3, c6, c5, c7, c8可行计划的特点：若在流程图中顶点可行计划的特点：若在流程图中顶点v是顶点是顶点u 的前趋，则在计划的前趋，则在计划序列中顶点序列中顶点v 也是也是u的前趋。的前趋。如何安排施工计划？如何安排施工计划？如何安排教学计划？如何安排教学计划？c4c1c2c3c12c9c10c11c6c7c8c5拓扑序列拓扑序列：有向图的一个顶点序列，满足：若顶点：有向图的一个顶点序列，满足：若顶点vi到到vj有路径有路径，则在序列中，则在

45、序列中vi排在排在vj之前，否则之前，否则vi与与vj的次序任意。的次序任意。 拓扑排序：拓扑排序： 就是将有向图中顶点排成拓扑序列。就是将有向图中顶点排成拓扑序列。拓扑排序拓扑排序(Topological Sorting)：构造拓扑序列的操作：构造拓扑序列的操作并非任何有向图都可进行拓扑排序，若存在有向回路就没有。并非任何有向图都可进行拓扑排序，若存在有向回路就没有。有回路意味着：某些活动的开工将以自己的完成为先决条件，有回路意味着：某些活动的开工将以自己的完成为先决条件，这种现象称为这种现象称为死锁死锁，此项工程是不可行的。，此项工程是不可行的。可用拓扑排序检查有向图是否存在回路可用拓扑排

46、序检查有向图是否存在回路2V5V1V3V4V7V6V （1）从图中选择一个入度为）从图中选择一个入度为0的顶点且输出之。的顶点且输出之。（2）从图中删掉此顶点及其所有出边。）从图中删掉此顶点及其所有出边。反复执行这两步，直至所有顶点都已输出，此时整个拓扑排序反复执行这两步，直至所有顶点都已输出，此时整个拓扑排序完成；或者直到图中剩余顶点的入度都不为完成；或者直到图中剩余顶点的入度都不为0时终止，此时图中时终止，此时图中存在回路，拓扑排序不能再进行下去。存在回路，拓扑排序不能再进行下去。7C3C1C6C5C4C2C7C3C6C5C4C6C5C7C6C5C4C5C(a)初态(b)输出C 后(c)输

47、出C 后(f)输出C 后(g)输出C 后7C6C5C(e)输出C 后7C6C5C(d)输出C 后2341761C1C1C为便于考察入度，顶点表中增加为便于考察入度，顶点表中增加入度域入度域in，指示当前各点入度，指示当前各点入度R初始入度值在邻接表的生成过程中累计得到；初始入度值在邻接表的生成过程中累计得到；以后动态修改。以后动态修改。7c123434451c2c3c4datafirstnonextin 56756c5c6c7 0012211顶点表边表7C3C1C6C5C4C2C 为避免每次重复找入度为为避免每次重复找入度为0的点，设置的点，设置栈栈保存入度为保存入度为0的点，则的点，则选入度

48、为零的点时，从栈顶取出。选入度为零的点时，从栈顶取出。R拓扑排序前，对顶点表扫描一遍，所有初始入度为零的点入栈拓扑排序前，对顶点表扫描一遍，所有初始入度为零的点入栈 R排序中出现新的入度为排序中出现新的入度为0的点，就将其入栈。的点，就将其入栈。void topsort(graph g) 扫描顶点表，建立入度为零的顶点栈扫描顶点表，建立入度为零的顶点栈; while(栈不空栈不空) 弹出栈顶弹出栈顶v并输出之并输出之; 检查检查v的出边表，将其每条出边的终点的出边表，将其每条出边的终点w的入度减的入度减1， 若变为零，则若变为零，则w入栈入栈; 若输出的顶点数小于若输出的顶点数小于n，则输出，则输出“有回路有回路”， 否则拓扑排序正常结束否则拓扑排序正常结束;也可用也可用队列队列保存当前入度为保存当前入度为0的点的点 C1C2C3C4C5C6C5C1C4C3C2C6拓扑序列：拓扑序列：入度入度0的栈：的栈：C3C5C1C4C2C6动态演示动态演示(用栈保存入度为用栈保存入度为0的顶点的顶点)：如