第章图图的基本概念图的基本概念 图的基本运算图的基本运算 生成树与最小生成树生成树与最小生成树 拓扑排序拓扑排序 图的基本存储结构图的基本存储结构 最短路径最短路径关键路径关键路径 图的遍历图的遍历8.1图的基本概念一、图的定义图是由一个非空的顶点集合和一个描述顶点之间图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：它可以形式化地表示为：图（图（V V，E E）其中其中V=x|xV=x|x 某个数据对象集某个数据对象集 ，它是顶点的有，它是顶点的有穷非空集合；穷非空集合；E=E=（x x，y y）|x |x，y y VV或或E=xE=|xy|x，y y V V且且P P（x x，y y） ，它是顶点之间关系的有穷集，它是顶点之间关系的有穷集合，也叫做边集合，合，也叫做边集合，P P（x x，y y）表示从）表示从x x到到y y的一条的一条单向通路。单向通路。图的应用举例图的应用举例例例1 1 交通图（公路、铁路）交通图（公路、铁路） 顶点：地点顶点：地点 边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；交通图中的有单行道双行道，分别用有向边、无向边表示； V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3例例2 2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点 边：地点间的连线边：地点间的连线例例4 4 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系 通通常常，也也将将图图GG的的顶顶点点集集和和边边集集分分别别记记为为V V（GG）和和E E（GG）。E E（GG）可可以以是是空空集集，若若E E（GG）为为空空，则图则图GG只有顶点而没有边。只有顶点而没有边。若图若图GG中的每条边都是有方向的，则称中的每条边都是有方向的，则称GG为为有向有向图图。在有向图中，一条有向边是由两个顶点组成的有。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对序对，有序对通常用尖括号表示。例如，有序对v 表示一条由表示一条由v vi i到到v vj j的有向边。有向边又称为的有向边。有向边又称为弧弧，弧，弧的始点称为的始点称为弧尾弧尾，弧的终点称为，弧的终点称为弧头弧头。若图。若图GG中的每中的每条边都是没有方向的，则称条边都是没有方向的，则称GG为为无向图无向图。无向图中的。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。边均是顶点的无序对，无序对通常用圆括号表示。 图图8-18-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图8.18.1（a a）表表示示的的是是有有向向图图GG1 1，该该图图的的顶顶点点集集和和边集分别为：边集分别为：V V（GG1 1）=v=v1 1，v v2 2，v v3 3，v v4 4 E E（GG1 1）=v= ，v ，v ，v例例有序对有序对v ：用以为用以为v vi i起点、以起点、以v vj j为终点为终点的有向线段表示，称为有向的有向线段表示，称为有向边或弧；边或弧；例：图例：图8-18-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图8.18.1（b b）表表示示的的是是无无向向图图GG2 2，该该图图的的顶顶点点集集和和边集分别为：边集分别为：V V（GG2 2）=v=v1 1，v v2 2，v v3 3，v v4 4，v v5 5 E E（GG2 2）=（v vl l，v v2 2），（v v1 1，v v3 3），（v v1 1，v v4 4），（v v2 2，v v3 3），（），（v v2 2，v v5 5），（），（v v4 4，v v5 5） 无序对无序对(v(vi i,v,vj j) )：用连接顶点用连接顶点v vi i、v vj j的线段的线段表示，称为无向边；表示，称为无向边；在以后的讨论中，我们约定：在以后的讨论中，我们约定：（1 1）一一条条边边中中涉涉及及的的两两个个顶顶点点必必须须不不相相同同，即即：若若（v vi i，v vj j）或或v 是是E E（GG）中中的的一一条条边边，则则要要求求v vi ivvj j；（2 2）一对顶点间不能有相同方向的两条有向边；）一对顶点间不能有相同方向的两条有向边；（3 3）一一对对顶顶点点间间不不能能有有两两条条无无向向边边，即即只只讨讨论论简简单的图。单的图。 若用若用n n表示图中顶点的数目，用表示图中顶点的数目，用e e表示图中边的表示图中边的数目，按照上述规定，容易得到下述结论：对于一数目，按照上述规定，容易得到下述结论：对于一个具有个具有n n个顶点的无向图，其边数个顶点的无向图，其边数e e小于等于小于等于n n（n-n-1 1）/2/2，边数恰好等于，边数恰好等于n n（n-1n-1）/2/2的无向图称为的无向图称为无向无向完全图完全图；对于一个具有；对于一个具有n n个顶点的有向图，其边数个顶点的有向图，其边数e e小于等于小于等于n n（n-1n-1），边数恰好等于），边数恰好等于n n（n-1n-1）的有向）的有向图称为图称为有向完全图有向完全图。也就是说完全图具有最多的边。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。数，任意一对顶点间均有边相连。 二、完全图例：图例：图8-28-2v1v2v3v4v1v2v3v4（a a）无向完全图）无向完全图GG3 3（b b）有向完全图）有向完全图GG4 4 GG3 3与与GG4 4分别是具有分别是具有4 4个顶点的无向完全图和有向完全个顶点的无向完全图和有向完全图。图图。图GG3 3共有共有4 4个顶点个顶点6 6条边；图条边；图GG4 4共有共有4 4个顶点个顶点1212条条边。边。 若（若（v vi i，v vj j）是一条无向边，则称顶点）是一条无向边，则称顶点v vi i和和v vj j互为互为邻接点邻接点 。若若v 是一条有向边，则称是一条有向边，则称v vi i邻接到邻接到v vj j，v vj j邻邻接于接于v vi i，并称有向边，并称有向边v 关联于关联于v vi i与与v vj j，或称有向，或称有向边边v 与顶点与顶点v vi i和和v vj j相关联。相关联。 三、度、入度、出度在图中，一个顶点的在图中，一个顶点的度度就是与该顶点相关联的就是与该顶点相关联的边的数目，顶点边的数目，顶点v v的度记为的度记为D D（v v）。例如在图）。例如在图8.28.2（a a）所示的无向图）所示的无向图GG3 3中，各顶点的度均为中，各顶点的度均为3 3。若若GG为有向图，则把以顶点为有向图，则把以顶点v v为终点的边的数目为终点的边的数目称为顶点称为顶点v v的的入度入度，记为，记为IDID（v v）；把以顶点）；把以顶点v v为始为始点的边的数目称为点的边的数目称为v v的的出度出度，记为，记为ODOD（v v），有向），有向图中顶点的度数等于顶点的入度与出度之和，即图中顶点的度数等于顶点的入度与出度之和，即D D（v v）=ID=ID（v v）+OD+OD（v v）。）。 无无论论有有向向图图还还是是无无向向图图，图图中中的的每每条条边边均均关关联联于于两两个个顶顶点点，因因此此，顶顶点点数数n n、边边数数e e和和度度数数之之间间有有如如下下关系：关系：e=e=.（式（式8-18-1）四、子图给定两个图给定两个图GGi i和和GGj j，其中，其中GGi i= =（V Vi i，E Ei i），），GGj j= =（V Vj j，E Ej j），若满足），若满足V Vi i V Vj j，E Ei i E Ej j，则称，则称GGi i是是GGj j的的子子图图。 v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4子图示例子图示例（a a）无向图）无向图GG3 3的部分子图的部分子图 （b b）有向图）有向图GG4 4的部分子图的部分子图 五、路径 无无向向图图GG中中若若存存在在着着一一个个顶顶点点序序列列v v、v v1 1 、v v2 2 、v vmm 、u u，且且（v v，v v1 1 ）、（v v1 1 ，v v2 2 ）、（v vmm ，u u）均均属属于于E E（GG），则则称称该该顶顶点点序序列列为为顶顶点点v v到到顶顶点点u u的的一一条条路路径径，相相应应地地，顶顶点点序序列列u u、v vmm 、v vm-1m-1 、v v1 1 、v v是顶点是顶点u u到顶点到顶点v v的一条路径。的一条路径。 如如果果GG是是有有向向图图，路路径径也也是是有有向向的的，它它由由E E（GG）中中的的有有向向边边v、v、vu组成。组成。路径长度路径长度是该路径上边或弧的数目。是该路径上边或弧的数目。如果一条路径上除了起点如果一条路径上除了起点v v和终点和终点u u相同外，其余相同外，其余顶点均不相同，则称此路径为一条顶点均不相同，则称此路径为一条简单路径简单路径。起点和。起点和终点相同（终点相同（v=uv=u）的简单路径称为）的简单路径称为简单回路简单回路或或简单环简单环。 六、连通图与强连通图在无向图在无向图GG中，若从顶点中，若从顶点v vi i到顶点到顶点v vj j有路径，则有路径，则称称v vi i与与v vj j是连通的。若是连通的。若V V（GG）中任意两个不同的顶）中任意两个不同的顶点点v vi i和和v vj j都连通（即有路径），则称都连通（即有路径），则称GG为为连通图连通图。例。例如，图如，图8.18.1（b b）所示的无向图）所示的无向图GG2 2、图、图8.28.2（a a）所示）所示的无向图的无向图GG3 3是都是连通图。是都是连通图。 无向图无向图GG的极大连通子图称为的极大连通子图称为GG的的连通分量连通分量。根据连通分量的定义，可知任何连通图的连通分量根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。是其自身，非连通的无向图有多个连通分量。 例：非连通图及其连通分量示例例：非连通图及其连通分量示例（a a）非连通图）非连通图GG5 5（b b）GG5 5的两个连通分量的两个连通分量H H1 1和和H H2 2在有向图在有向图GG中，若对于中，若对于V V（GG）中任意两个不同的）中任意两个不同的顶点顶点v vi i和和v vj j，都存在从，都存在从v vi i到到v vj j以及从以及从v vj j到到v vi i的路径，则称的路径，则称GG是是强连通图。强连通图。V1V2V4V5V3V1V2V4V5V3有向图的极大强连通子图称为有向图的极大强连通子图称为GG的强连通分量。的强连通分量。根据强连通图的定义，可知强连通图的唯一强连通根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分分量是其自身，而非强连通的有向图有多个强连分量。例如，图量。例如，图8.28.2（b b）所示的有向图）所示的有向图GG4 4是一个具有是一个具有4 4个顶点的强连通图，图个顶点的强连通图，图8.58.5（a a）所示的有向图）所示的有向图GG6 6不是强连通图（不是强连通图（v v2 2、v v3 3、v v4 4没有到达没有到达v v1 1的路径），的路径），它的两个强连通分量它的两个强连通分量H H3 3与与H H4 4如图如图8.58.5（b b）所示。）所示。 v v1 1v v2 2v v3 3v v4 4v v1 1v v2 2v v3 3v v4 4（a a）非强连通图）非强连通图GG6 6（b b）GG6 6的两个强连通分量的两个强连通分量H H3 3和和H H4 4 七、网络有时在图的每条边上附上相关的数值，这种与有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫图的边相关的数值叫权权。 权可以表示两个顶点之间的距离、耗费等具有权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。称这种带权图为网络。 V0V1V3V234567825V0V2V1455064（a a）无向网络）无向网络GG7 7（b b）有向网络）有向网络GG8 8作业：作业：8.18.1对于无向图对于无向图8.298.29，试给出，试给出（1 1）图中每个顶点的度；）图中每个顶点的度；（2 2）该图的邻接矩阵；）该图的邻接矩阵；（4 4）该图的连通分量。）该图的连通分量。v0v3v4v2v1v5v6图图8.298.29无向图无向图8.2 8.2 给定有向图，试给出给定有向图，试给出（1 1）顶点）顶点D D的入度与出度；的入度与出度；（2 2）该图的出边表与入边表；）该图的出边表与入边表；（3 3）该图的强连通分量。）该图的强连通分量。 ABCDE图图8.308.30有向图有向图8.2图的基本运算 图图是是一一种种复复杂杂数数据据结结构构，由由图图的的定定义义及及图图的的一一组组基基本操作构成了图的抽象数据类型。本操作构成了图的抽象数据类型。ADTGraphADTGraph数数据据对对象象V V：V V是是具具有有相相同同特特性性的的数数据据元元素素的的集集合合，称称为顶点集。为顶点集。数据关系数据关系R R：R=vR=|vw|v，w w V V且且P P（v v，w w），P P（v v，w w）定定义义了边（或弧）（了边（或弧）（v v，w w）的信息）的信息 图的基本操作如下：图的基本操作如下：（1 1）creatgraphcreatgraph（&g&g） 创创建建一一个个图图的的存存储储结构。结构。（2 2）insertvertexinsertvertex（&g&g，v v） 在在图图g g中中增增加加一一个个顶顶点点v v。（3 3）deletevertexdeletevertex（&g&g，v v） 在在图图g g中中删删除除顶顶点点v v及所有和顶点及所有和顶点v v相关联的边或弧。相关联的边或弧。（4 4）insertedgeinsertedge（&g&g，v v，u u） 在在图图g g中中增增加加一一条条从从顶点顶点v v到顶点到顶点u u的边或弧。的边或弧。（5 5）deleteedgedeleteedge（&g&g，v v，u u） 在在图图g g中中删删除除一一条条从从顶点顶点v v到顶点到顶点u u的边或弧。的边或弧。（6 6）travetrave（g g）遍历图遍历图g g。（7 7）locatevertexlocatevertex（g g，v v） 求求顶顶点点v v在在图图g g中中的的位位序。序。（8 8）fiirstvertexfiirstvertex（g g，v v） 求求图图g g中中顶顶点点v v的的第第一个邻接点。一个邻接点。（9 9）degreedegree（g g，v v）求图求图g g中顶点中顶点v v的度数。的度数。（1010）nextvertexnextvertex（g g，v v，w w） 求求图图g g中中与与顶顶点点v v相相邻邻接接的的顶顶点点w w的的下下一一个个邻邻接接点点。即即求求图图g g中中顶顶点点v v的的某某个个邻邻接接点点，它它的的存存储储顺顺序序排排在在邻邻接接点点w w的的存存储储位位置之后。置之后。ADTGraphADTGraph图的基本存储结构 图的存储结构至少要保存两类信息：图的存储结构至少要保存两类信息： 1) 1)顶点的数据顶点的数据 2) 2)顶点间的关系顶点间的关系约定约定: : G=G=是图是图,V=v,V=v0 0,v,v1 1,v,v2 2,v,vn-1n-1,设顶点的设顶点的角标为它的编号角标为它的编号 如何表示顶点间的关系？如何表示顶点间的关系？ V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V38.3.1邻接矩阵及其实现给定图给定图G=G=（V V，E E），其中），其中V V（GG）=v=v0 0，v vi i，v vn-1n-1 ，GG的邻接矩阵（的邻接矩阵（AdacencyMatrixAdacencyMatrix）是）是具有如下性质的具有如下性质的n n阶方阵：阶方阵： 无向图的邻接矩阵是对称的，有向图的邻接矩无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。阵可能是不对称的。一、非网络的邻接矩阵一、非网络的邻接矩阵v0v1v3v2v3v1v0v2图的邻接矩阵示例图的邻接矩阵示例0111011110101010110111011010101001000100101010101100110001000100A1=A1=A2=A2=图图8.7 8.7 无向图无向图G G9 9及有向图及有向图G G1010的邻接矩阵表示的邻接矩阵表示 用邻接矩阵表示图，很容易判定任意两个顶点用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。对于之间是否有边相连，并求得各个顶点的度数。对于无向图，顶点无向图，顶点v vi i的度数是邻接矩阵中第的度数是邻接矩阵中第i i行或第行或第i i列值列值为为1 1的元素个数，即：的元素个数，即： D D（v vi i）=（8-28-2）对于有向图，邻接矩阵中第对于有向图，邻接矩阵中第i i行值为行值为1 1的元素个的元素个数为顶点数为顶点v vi i的出度，第的出度，第i i列值为列值为1 1的元素的个数为顶的元素的个数为顶点点v vi i的入度，即：的入度，即： ODOD（v vi i）=;ID=;ID（v vi i）=（8-8-3 3） 二、网络的邻接矩阵二、网络的邻接矩阵当当G=G=（V V，E E）是一个网络时，）是一个网络时，GG的邻接矩阵是具的邻接矩阵是具有如下性质的有如下性质的n n阶方阵：阶方阵： WWij ij 当（当（v vi i，v vj j）或）或v E E（GG）00当（当（v vi i，v vj j）或）或vEE（GG）且）且i=ji=j当（当（v vi i，v vj j）或）或vEE（GG）且）且ijijAiAi，j=j=其中其中WWij ij表示边上的权值；表示边上的权值； 表示一个计算机允表示一个计算机允许的、大于所有边上权值的数。许的、大于所有边上权值的数。 V0V1V3V234567825V0V2V1455064网络的邻接矩阵示例网络的邻接矩阵示例056347805634785605603402534025782507825000550 0045045640640A A3 3= =A A4 4= =（a a）GG7 7的邻接矩阵的邻接矩阵（b b）GG8 8的邻接矩阵的邻接矩阵图图8.88.8网络邻接矩阵示例网络邻接矩阵示例邻接矩阵存储结构邻接矩阵存储结构#defineFINITY5000/*#defineFINITY5000/*此处用此处用50005000代表无穷大代表无穷大*/ */#definem20/*#definem20/*最大顶点数最大顶点数*/ */typedefcharvertextype;/*typedefcharvertextype;/*顶点值类型顶点值类型*/ */typedefintedgetype;/*typedefintedgetype;/*权值类型权值类型*/ */typedefstructtypedefstructvertextypevexsm;/*vertextypevexsm;/*顶点信息域顶点信息域*/ */edgetypeedgesmm;/*edgetypeedgesmm;/*邻接矩阵邻接矩阵*/ */intn,e;/*intn,e;/*图中顶点总数与边数图中顶点总数与边数*/ */mgraph;/*mgraph;/*邻接矩阵表示的图类型邻接矩阵表示的图类型*/ */*/*/*/*/* 图图的的邻邻接接矩矩阵阵创创建建算算法法 */ */*/*文件名：文件名：c_ljjz.cc_ljjz.c函数名：函数名：creatmgraph1()*/creatmgraph1()*/*/*/*/#include#include#includemgraph.h#includemgraph.hvoidcreatmgraph1(mgraph*g)voidcreatmgraph1(mgraph*g)inti,j,k,w;/*inti,j,k,w;/*建立有向网络的邻接矩阵存储结构建立有向网络的邻接矩阵存储结构*/ */printf(pleaseinputnande:n);printf(pleaseinputnande:n); scanf(%d%d,&g-n,&g-e)scanf(%d%d,&g-n,&g-e);/*;/*输入图的顶点数与边数输入图的顶点数与边数*/ */getchar();/*getchar();/*取消输入的换行符取消输入的换行符*/ */printf(pleaseinputvexs:n);printf(pleaseinputvexs:n);for(i=0;in;i+)/*for(i=0;in;i+)/*输入图中的顶点值输入图中的顶点值*/ */g-vexsi=getchar();g-vexsi=getchar();for(i=0;in;i+)/*for(i=0;in;i+)/*初始化邻接矩阵初始化邻接矩阵*/ */for(j=0;jn;j+)for(j=0;jn;j+)if(i=j)g-edgesij=0;if(i=j)g-edgesij=0;elseg-edgesij=FINITY;elseg-edgesij=FINITY;printf(pleaseinputedges:n);printf(pleaseinputedges:n);for(k=0;ke;k+)/*for(k=0;ke;k+)/*输入网络中的边输入网络中的边*/ */scanf(%d%d%d,&i,&j,&wscanf(%d%d%d,&i,&j,&w); );g-edgesij=w;g-edgesij=w;/*/*若是建立无向网，只需在此加入语句若是建立无向网，只需在此加入语句g-edgesji=w;g-edgesji=w;即可即可*/ */说明说明: :当建立有向网时，边信息以三元组（当建立有向网时，边信息以三元组（i i，j j，w w）的形的形式输入，式输入，i i、j j分别表示两顶点的序号，分别表示两顶点的序号，w w表示边上的权。表示边上的权。对于每一条输入的边信息（对于每一条输入的边信息（i i，j j，w w），），只需将只需将g-g-edgesijedgesij赋值为赋值为w w。 creatmgraph2()creatmgraph2()是用于建立无向网络的函数，它与是用于建立无向网络的函数，它与creatmgraph1creatmgraph1() ()的区别在于对每一条输入的边信息（的区别在于对每一条输入的边信息（i i，j j，w w），），需需同时将同时将g-edgesijg-edgesij和和g-edgesjig-edgesji赋值为赋值为w w。当建立非网络的存储结构时，所有的边信息只需按当建立非网络的存储结构时，所有的边信息只需按二元组（二元组（i i，j j）的形式输入。的形式输入。 8.3.2邻接表及其实现 用邻接矩阵表示法存储图，占用的存储单元个用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。数只与图中顶点的个数有关，而与边的数目无关。一个含有一个含有n n个顶点的图，如果其边数比个顶点的图，如果其边数比n n2 2少得多，少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储那么它的邻接矩阵就会有很多空元素，浪费了存储空间。空间。 n n无向图的邻接表无向图的邻接表对于图对于图GG中的每个顶点中的每个顶点v vi i，该方法把所有邻接于该方法把所有邻接于v vi i的顶点的顶点v vj j链成一个带头结点的单链表，这个单链表就链成一个带头结点的单链表，这个单链表就称为顶点称为顶点v vi i的邻接表。单链表中的每个结点至少包含的邻接表。单链表中的每个结点至少包含两个域，一个为两个域，一个为邻接点域邻接点域（adjvexadjvex），），它指示与顶点它指示与顶点v vi i邻接的顶点在图中的位序，另一个为邻接的顶点在图中的位序，另一个为链域链域（nextnext），），它指示与顶点它指示与顶点v vi i邻接的下一个结点。邻接的下一个结点。 adjvex nextadjvex nextvertex firstdegevertex firstdege为了便于随机访问任一顶点的邻接表，可将所为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。放在一起来描述图的存储结构。 v0v1v3v2图图8.78.7无向图无向图GG9 91 2 3 0 2 0 1 3 0 2 V0V1V2V3图图8.9G8.9G9 9的邻接表的邻接表表头结点表头结点结构结构边结点结边结点结构构对于无向图，对于无向图，v vi i的邻接表中每个表结点都对应于的邻接表中每个表结点都对应于与与v vi i相关联的一条边；对于有向图来说，如果每一顶相关联的一条边；对于有向图来说，如果每一顶点点v vi i的邻接表中每个表结点都存储以的邻接表中每个表结点都存储以v vi i的为始点射出的为始点射出的一条边，则称这种表为有向图的的一条边，则称这种表为有向图的出边表出边表（有向图的（有向图的邻接表），反之，若每一顶点邻接表），反之，若每一顶点v vi i的邻接表中每个表结的邻接表中每个表结点都对应于以点都对应于以v vi i为终点的边（即射入为终点的边（即射入v vi i的边），则称的边），则称这种表为有向图的这种表为有向图的入边表入边表（又称逆邻接表）。（又称逆邻接表）。 v0v1v2v31 0 2 0 1 1 GG1010的出边表的出边表v0v1v2v3 1 2 0 2 1 3 GG1010的入边表的入边表v3v1v0v2图图8.7(b)8.7(b)有向图有向图GG1010在无向图的邻接表中，顶点在无向图的邻接表中，顶点v vi i的度为第的度为第i i个链表中个链表中结点的个数；而在有向图的出边表中，第结点的个数；而在有向图的出边表中，第i i个链表中个链表中的结点个数是顶点的结点个数是顶点v vi i的出度；为了求入度，必须对整的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为个邻接表扫描一遍，所有链表中其邻接点域的值为i i的结点的个数是顶点的结点的个数是顶点v vi i的入度。的入度。 1 2 3 0 2 0 1 3 0 2 V0V1V2V3V V0 0的度为的度为3 3v0v1v2v31 0 2 0 1 1 GG1010的出边表的出边表V V0 0的出度为的出度为1 1，入度为，入度为2 2邻接表的存储结构邻接表的存储结构/*/*/*/*/*邻接表存储结构邻接表存储结构文件名：文件名：adjgraph.h*/adjgraph.h*/*/*/*/#definem20/*#definem20/*预定义图的最大顶点数预定义图的最大顶点数*/ */typedefchardatatype;/*typedefchardatatype;/*顶点信息数据类型顶点信息数据类型*/ */typedefstructnode/*typedefstructnode/*边表结点边表结点*/ */intadjvex;/*intadjvex;/*邻接点邻接点*/ */structnode*next;structnode*next;edgenode;edgenode;adjvex nextadjvex next边结点结边结点结构构typedefstructvnode/*typedefstructvnode/*头结点类型头结点类型*/ */datatypevertex;/*datatypevertex;/*顶点信息顶点信息*/ */edgenode*firstedge;/*edgenode*firstedge;/*邻接链表头指针邻接链表头指针*/ */vertexnode;vertexnode;typedefstruct/*typedefstruct/*邻接表类型邻接表类型*/ */vertexnodeadjlistm;/*vertexnodeadjlistm;/*存放头结点的顺序表存放头结点的顺序表*/ */intn,e;/*intn,e;/*图的顶点数与边数图的顶点数与边数*/ */adjgraph;adjgraph;vertex firstdegevertex firstdege头结点结头结点结构构/*/*/*/*/* 无无向向图图的的邻邻接接表表创创建建算算法法 */ */*/*文件名文件名c_ljb.cc_ljb.c函数名：函数名：createadjgraph()*/createadjgraph()*/*/*/*/voidcreateadjgraph(adjgraph*g)voidcreateadjgraph(adjgraph*g)inti,j,k;inti,j,k;edgenode*s;edgenode*s;printf(Pleaseinputnande:n);printf(Pleaseinputnande:n);scanf(%d%d,&g-n,&g-e);scanf(%d%d,&g-n,&g-e);/* /*输入顶点数与边数输入顶点数与边数*/ */getchar();getchar();printf(Pleaseinput%dvertex:,g-n);printf(Pleaseinput%dvertex:,g-n);for(i=0;in;i+)for(i=0;in;i+)scanf(“%c”,&g-adjlisti.vertex);/*scanf(“%c”,&g-adjlisti.vertex);/*读入顶点信息读入顶点信息*/*/g-adjlisti.firstedge=NULL;/*g-adjlisti.firstedge=NULL;/*边表置为空表边表置为空表*/ */printf(Pleaseinput%dedges:,g-e);printf(Pleaseinput%dedges:,g-e);for(k=0;ke;k+)/*for(k=0;ke;k+)/*循环循环e e次建立边表次建立边表*/ */scanf(%d%d,&i,&j);/*scanf(%d%d,&i,&j);/*输入无序对（输入无序对（i,j i,j）*/ */s=(edgenode*)malloc(sizeof(edgenode);s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=j;/*s-adjvex=j;/*邻接点序号为邻接点序号为j*/j*/s-next=g-adjlisti.firstedge;s-next=g-adjlisti.firstedge; g-adjlisti.firstedge=s;g-adjlisti.firstedge=s; / /* *将将新新结结点点*s*s插插入入顶顶点点v vi i的边表头部的边表头部*/ */s=(edgenode*)malloc(sizeof(edgenode);s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=i;/*s-adjvex=i;/*邻接点序号为邻接点序号为i*/i*/s-next=g-adjlistj.firstedge;s-next=g-adjlistj.firstedge;g-adjlistj.firstedge=s;g-adjlistj.firstedge=s;/* /*将新结点将新结点*s*s插入顶点插入顶点v vj j的边表头部的边表头部*/ */算法算法8.28.2建立无向图的邻接表算法建立无向图的邻接表算法说明：一个图的邻接矩阵表示是唯一的，但其邻接表说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表结构中，各边表结点表示不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次的链接次序取决于建立邻接表的算法以及边的输入次序。序。 4 54 5ABCDABCD0 1 0 2 0 3 1 2 2 30 1 0 2 0 3 1 2 2 3ABDC例例: :若若需需建建立立下下图图所所示示的的无无向向图图邻邻接接表表存存储储结结构构, ,则则在执行程序时如果输入的信息为：在执行程序时如果输入的信息为：则将建立如下的邻接表存储结构。则将建立如下的邻接表存储结构。A 3-2-1A 3-2-1B 2-0B 2-0C 3-1-0C 3-1-0D 2-0D 2-08.3.3邻接多重表n n在邻接多重表中，每一条边只有一个边结点。为有关在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。边的处理提供了方便。边结点的结构边结点的结构 mark vexi linki vexj linkj 其中，其中，mark mark 是记录是否处理过的标记；是记录是否处理过的标记；vexivexi和和vexjvexj是依附于该边的两顶点位置。是依附于该边的两顶点位置。lnikilniki域是链接指针，域是链接指针，指向下一条依附于顶点指向下一条依附于顶点vexivexi的边；的边；linkjlinkj也是链接指针，也是链接指针，指向下一条依附于顶点指向下一条依附于顶点vexjvexj的边。需要时还可设置一的边。需要时还可设置一个存放与该边相关的权值的域个存放与该边相关的权值的域 cost cost。顶点结点的结构顶点结点的结构 存储顶点信息的结点表以顺序表方式组织，每存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，一个顶点结点有两个数据成员：其中，vertex vertex 存放存放与该顶点相关的信息，与该顶点相关的信息，firstedgefirstedge 是指示第一条依是指示第一条依附于该顶点的边的指针。附于该顶点的边的指针。 在邻接多重表中在邻接多重表中, , 所有依附于同一个顶点的所有依附于同一个顶点的边都链接在同一个单链表中。边都链接在同一个单链表中。 从顶点从顶点 i i 出发出发, , 可以循链找到所有依附于该顶可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。点的边，也可以找到它的所有邻接顶点。 vertex FirstedgeV0V1V3V234567825V0V1V2V356013402780325230123无向网络的邻接多重表示例无向网络的邻接多重表示例其中边表结点增加了一个存储权值的数据域其中边表结点增加了一个存储权值的数据域 。8.4图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组用一个辅助数组visitnvisitn作为对顶点的标记，当顶点作为对顶点的标记，当顶点vi vi未被访问，未被访问，visitivisiti值为值为0 0；当；当v vi i已被访问，则已被访问，则visitivisiti值为值为1 1。图的遍历与图的遍历与图的遍历与图的遍历与树的遍历有什么不同树的遍历有什么不同树的遍历有什么不同树的遍历有什么不同有两种遍历方法有两种遍历方法（它们对无向图，有向图都适用）它们对无向图，有向图都适用）深度优先遍历深度优先遍历广度优先遍历广度优先遍历从图中某顶点从图中某顶点v v出发：出发： 1 1）访问顶点）访问顶点v v；2 2）依次从）依次从v v的未被访问的邻接点出发，继续对图进行深的未被访问的邻接点出发，继续对图进行深度优先遍历；度优先遍历； 对对于于给给定定的的图图G=G=（V V，E E），首首先先将将V V中中每每一一个个顶顶点点都都标标记记为为未未被被访访问问，然然后后，选选取取一一个个源源点点v v V V，将将v v标标记记为为已已被被访访问问，再再递递归归地地用用深深度度优优先先搜搜索索方方法法，依依次次搜搜索索v v的的所所有有邻邻接接点点w w。若若w w未未曾曾访访问问过过，则则以以w w为为新新的的出出发发点点继继续续进进行行深深度度优优先先遍遍历历，如如果果从从v v出出发发有有路路的的顶顶点点都都已已被被访访问问过过，则则从从v v的的搜搜索索过过程程结结束束。此此时时，如如果果图图中中还还有有未未被被访访问问过过的的顶顶点点（该该图图有有多多个个连连通通分分量量或或强强连连通通分分量量），则则再再任任选选一一个个未未被被访访问问过过的的顶顶点点，并并从从这这个个顶顶点点开开始始做做新新的的搜搜索索。上上述述过过程程一一直进行到直进行到V V中所有顶点都已被访问过为止。中所有顶点都已被访问过为止。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4例例序列序列1 1：V0,V1,V3,V7,V4,V2,V5,V6深度优先遍历过程：深度优先遍历过程：由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，深度优先序列不是唯一的深度优先序列不是唯一的序列序列2 2：V0,V1,V4,V7,V3,V2,V5,V6c0c1c3c2c4c5c0c1c3c2c4c5DFSDFS序列：序列：c c0 0 cc1 1 cc3 3 cc4 4 cc5 5 cc2 2但是，当采用邻接表存储结构并且存储结构已确但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。定的情况下，遍历的结果将是确定的。采用邻接表存储结构的深度优先遍历算法实现：采用邻接表存储结构的深度优先遍历算法实现：/*/*/*/*/* 图图的的深深度度优优先先遍遍历历算算法法 */ */*/*文件名：文件名：dfs.cdfs.c函数名：函数名：dfs()dfs()、dfstraverse()*/dfstraverse()*/*/*/*/intvisitedm;intvisitedm;voiddfs(adjgraphg,inti)voiddfs(adjgraphg,inti)/*/*以以v vi i为出发点深度优先遍历顶点为出发点深度优先遍历顶点v vi i所在的连通分量所在的连通分量*/ */edgenode*p;edgenode*p;printf(visitvertex:%cn,g.adjlisti.vertex);/*printf(visitvertex:%cn,g.adjlisti.vertex);/*访问顶点访问顶点i*/i*/visitedi=1;visitedi=1;p=g.adjlisti.firstedge;p=g.adjlisti.firstedge;while(p)/*while(p)/*从从p p的邻接点出发进行深度优先搜索的邻接点出发进行深度优先搜索*/ */if(!visitedp-adjvex)if(!visitedp-adjvex)dfs(g,p-adjvex);/*dfs(g,p-adjvex);/*递归递归*/ */p=p-next;p=p-next; voiddfstraverse(adjgraphg)voiddfstraverse(adjgraphg)/*/*深度优先遍历图深度优先遍历图g*/g*/inti;inti;for(i=0;ig.n;i+)for(i=0;ig.n;i+)visitedi=0;/*visitedi=0;/*初始化标志数组初始化标志数组*/ */for(i=0;ig.n;i+)for(i=0;ihead)/*while(tailhead)/*当队列非空时，执行下列循环体当队列非空时，执行下列循环体*/ */j=queue+head;/*j=queue+head;/*出队出队*/ */p=g.adjlistj.firstedge;p=g.adjlistj.firstedge;while(p)/*while(p)/*广度优先搜索邻接表广度优先搜索邻接表*/ */if(visitedp-adjvex=0)if(visitedp-adjvex=0)printf(%c,g.adjlistp-adjvex.vertex);printf(%c,g.adjlistp-adjvex.vertex);queue+tail=p-adjvex;queue+tail=p-adjvex;visitedp-adjvex=1;visitedp-adjvex=1;p=p-next;p=p-next;intbfstraverse(adjgraphg,datatypev)intbfstraverse(adjgraphg,datatypev)inti,count=0;/*inti,count=0;/*广度优先遍历图广度优先遍历图g*/g*/for(i=0;ig.n;i+)visitedi=0;/*for(i=0;ig.n;i+)visitedi=0;/*初始化标志数组初始化标志数组*/ */i=loc(g,v);/*i=loc(g,v);/*寻找顶点寻找顶点v v在邻接表中的位序在邻接表中的位序*/ */if(i!=-1)if(i!=-1)count+;/*count+;/*连通分量个数加连通分量个数加1*/1*/bfs(g,i);bfs(g,i);for(i=0;ig.n;i+)for(i=0;ig.n;i+)if(!visitedi)/*vif(!visitedi)/*vi i未访问过未访问过*/ */printf(n);printf(n);count+;/*count+;/*连通分量个数加连通分量个数加1*/1*/bfs(g,i);/*bfs(g,i);/*从顶点从顶点i i出发广度优先遍历图出发广度优先遍历图g*/g*/returncount;/*returncount;/*返回无向图返回无向图g g中连通分量的个数中连通分量的个数*/ */ 算法算法8.48.4图的广度优先遍历算法（邻接表表示法）图的广度优先遍历算法（邻接表表示法）算法的时间复杂度与深度优先算法相同。算法的时间复杂度与深度优先算法相同。作业：作业：8.48.4图图8.318.31是某个无向图的邻接表，请是某个无向图的邻接表，请（1 1）画出此图；）画出此图；（2 2）写出从顶点）写出从顶点A A开始的开始的DFSDFS遍历结果。遍历结果。（3 3）写出从顶点）写出从顶点A A开始的开始的BFSBFS遍历结果。遍历结果。对于一个无向的连通图对于一个无向的连通图G=G=（V V，E E），设），设GG是是它的一个子图，如果它的一个子图，如果GG中包含了中包含了GG中所有的顶点中所有的顶点（即（即V V（GG）=V=V（GG）且）且GG是无回路的连通图，是无回路的连通图，则称则称GG为为GG一棵的生成树。一棵的生成树。 深度优先生成树：按深度优先遍历生成的生成树深度优先生成树：按深度优先遍历生成的生成树广度优先生成树：按广度优先遍历生成的生成树广度优先生成树：按广度优先遍历生成的生成树c0c1c3c2c4c5c0c1c3c2c4c5有向图的生成树有向图的生成树c0c1c3c2c4c5c6c0c1c3c2c4c5c6c0c1c3c2c4c5c6（a a）以）以c c0 0为根的有向图为根的有向图（b b）DFSDFS生成树生成树（c c）BFSBFS生成树生成树非连通图的生成森林非连通图的生成森林V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V8V7V9V6V5（a a）不连通的无向图）不连通的无向图GG1212（b b）图）图GG1212的一个的一个DFSDFS生成森林生成森林 （c c）图）图GG1212的一个的一个BFSBFS生成森林生成森林若有一个连通的无向图若有一个连通的无向图GG，有，有nn个顶点，并且个顶点，并且它的边是有权值的。在它的边是有权值的。在GG上构造生成树上构造生成树GG , ,使这使这n-1n-1条边的权值之和在所有的生成树中最小条边的权值之和在所有的生成树中最小 。例例 要要在在 nn个个城城市市间间建建立立交交通通网网，要要考考虑虑的的问问题题如如何何在在保保证证 nn点点连连通通的的前前题题下下最最节节省省经费经费?ABCDEF101015121287665上述问题即要使得生成树各上述问题即要使得生成树各边权值之各最小，即：边权值之各最小，即： 构造最小生成树的准则：构造最小生成树的准则：必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须使用且仅使用必须使用且仅使用n-1n-1条边来联接网络中的条边来联接网络中的n n个顶点；个顶点；不能使用产生回路的边。不能使用产生回路的边。 假设假设G=G=（V V，E E）是一个连通网，）是一个连通网，U U是顶点集是顶点集V V的的一个非空真子集，若（一个非空真子集，若（u u，v v）是满足）是满足u u U U，v v V-UV-U的边（称这种边为两栖边）且（的边（称这种边为两栖边）且（u u，v v）在所有的两栖）在所有的两栖边中具有最小的权值（此时，称（边中具有最小的权值（此时，称（u u，v v）为最小两栖）为最小两栖边），则必存在一棵包含边（边），则必存在一棵包含边（u u，v v）的最小生成树。）的最小生成树。MSTMST性质：性质：证明：证明：u uv vvvuuU UV-UV-U设（设（u,vu,v）是连接）是连接U U与（与（V-UV-U）之间所有边中的最小）之间所有边中的最小代价边（最小两栖边）。反证时假设代价边（最小两栖边）。反证时假设GG中的任何一中的任何一棵最小生成树都不含此最小两栖边。设棵最小生成树都不含此最小两栖边。设T T是连通网是连通网上的一棵最小生成树，当将（上的一棵最小生成树，当将（u,vu,v）加入到）加入到T T中时，中时，由生成树的定义，由生成树的定义，T T中必存在一条包含（中必存在一条包含（u,vu,v）的）的回路。另一方面，由于回路。另一方面，由于T T是生成树，则在是生成树，则在T T上必存上必存在另一条边（在另一条边（u,vu,v），其中），其中u u U,v U,v V- V-U,U,且且u u和和uu之间，之间，v v和和vv之间均有路径相通，删去之间均有路径相通，删去边（边（u,vu,v），便可消除上述回路，同时得到），便可消除上述回路，同时得到另一棵生成树另一棵生成树TT。因为（。因为（u,vu,v）的代价不高于）的代价不高于（u,vu,v），则），则TT的代价亦不高于的代价亦不高于T T，TT是包含是包含（u,vu,v）的一棵最小生成树。由此和假设矛盾。）的一棵最小生成树。由此和假设矛盾。n n普里姆算法的基本思想：普里姆算法的基本思想：(Prim)(Prim)算法算法和和(Kruskal)(Kruskal)算法算法是两个利用是两个利用MSTMST性质构性质构造最小生成树的算法。造最小生成树的算法。 从连通网络从连通网络 G = V, E G = V, E 中的某一顶点中的某一顶点 u u0 0 出出发，选择与它关联的具有最小权值的边发，选择与它关联的具有最小权值的边(u(u0 0, v), v)，将，将其顶点加入到生成树的顶点集合其顶点加入到生成树的顶点集合U U中。中。 以后每一步从一个顶点在以后每一步从一个顶点在U U中，而另一个顶点不中，而另一个顶点不在在U U中的各条边中选择权值最小的边中的各条边中选择权值最小的边(u, v)(u, v), ,把它的顶把它的顶点加入到点加入到集合集合U U中。如此继续下去，直到网络中的所中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合有顶点都加入到生成树顶点集合U U中为止。中为止。PrimPrim算法的基本步骤如下：算法的基本步骤如下：（1 1）初始化：）初始化：U=uU=u0 0 ，TREE=;TREE=;（2 2）如如果果U=VU=V（GG），则则输输出出最最小小生生成成树树T T，并并结结束算法；束算法；（3 3）在在所所有有两两栖栖边边中中找找一一条条权权最最小小的的边边（u u，v v）（若若候候选选两两栖栖边边中中的的最最小小边边不不止止一一条条，可可任任选选其其中中的的一一条条），将将边边（u u，v v）加加入入到到边边集集TREETREE中中，并并将将顶点顶点v v并入集合并入集合U U中。中。（4 4）由由于于新新顶顶点点的的加加入入，U U的的状状态态发发生生变变化化，需需要要对对U U与与V-UV-U之间的两栖边进行调整。之间的两栖边进行调整。（5 5）转步骤（）转步骤（2 2）ABCDEF101015121287665 （a a）无向网）无向网5ABCDEF107610（e e）选取（）选取（B B、F F）ABCDEF101512（b b）初始状态）初始状态5ABCDEF101576（c c）选取（）选取（A A、B B）5ABCDEF101576（d d）选取（）选取（B B、D D） 5ABCDEF107610（f f）选取（）选取（B B、C C）5ABCDEF107610（g g）选取（）选取（E E、F F）PrimPrim算法实现：算法实现：1 1、连通图用邻接矩阵、连通图用邻接矩阵netnet表示：表示：edgesij=edgesij=WWij ij 当（当（vi,vjvi,vj） E E（GG）且权为）且权为WWij ij否则否则 0 0 当当i=ji=j2 2、边、边treetree（生成树）（生成树） edge treen-1 edge treen-1typedef struct edgedatatypedef struct edgedata int beg,en; /*beg,en int beg,en; /*beg,en是结点序号是结点序号*/*/ int length; /* int length; /*边长边长*/*/ edge; edge;begbegenenlengthlengthtree 0 1 2 3 4tree 0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 1 2 3 4 5 1010 12 12 15 15 (a)(a)初始态初始态K=0 m=1K=0 m=1K=0 K=0 begbegenenlengthlengthtree 0 1 2 3 4tree 0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 1 2 3 4 5 1010 12 12 15 15 (b)(b)最小两栖边（最小两栖边（0 0，1 1） PrimPrim算法构造最小生成树的过程算法构造最小生成树的过程K=1 K=1 begbegenenlengthlengthtree 0 1 2 3 4tree 0 1 2 3 4 0 1 1 0 1 0 1 1 0 1 1 2 3 4 5 1 2 3 4 5 1010 7 7 5 5 15 15 6 6 (c)(c)最小两栖边（最小两栖边（0 0，3 3） K=2 K=2 begbegenenlengthlengthtree 0 1 2 3 4tree 0 1 2 3 4 0 1 1 0 1 0 1 1 0 1 1 3 2 4 5 1 3 2 4 5 1010 5 5 7 15 7 15 6 6 (d)(d)最小两栖边（最小两栖边（1 1，5 5） K=3 K=3 begbegenenlengthlengthtree 0 1 2 3 4tree 0 1 2 3 4 0 1 1 5 1 0 1 1 5 1 1 3 5 4 2 1 3 5 4 2 1010 5 5 6 6 10 10 7 7 (e)(e)最小两栖边（最小两栖边（1 1，2 2） begbegenenlengthlengthtree 0 1 2 3 4tree 0 1 2 3 4 0 1 1 1 5 0 1 1 1 5 1 3 5 2 4 1 3 5 2 4 1010 5 5 6 6 7 7 1010 (f) tree(f) tree中存储了最小生成树的边中存储了最小生成树的边 算法关键一步：算法关键一步：求第求第k k条轻边，将其加入条轻边，将其加入treetree中中1 1）求当前最小两栖边及应添加的点）求当前最小两栖边及应添加的点v vmin=treek.length;min=treek.length;s=k;s=k;for(j=k+1;j=g.n-2;j+)for(j=k+1;j=g.n-2;j+)if(treej.lengthmin)if(treej.lengthmin)min=treej.length;min=treej.length;s=j;s=j;v=trees.en;v=trees.en;/* *入选顶点为入选顶点为v*/v*/2 2）通过交换，将当前轻边加入）通过交换，将当前轻边加入treetree中中x=trees;x=trees;trees=treek;trees=treek;treek=x;treek=x;3 3）调整各剩余点对应的最小两栖边（由）调整各剩余点对应的最小两栖边（由v v加入引起）加入引起）for(j=k+1;j=g.n-2;j+)for(j=k+1;j=g.n-2;j+)d=g.edgesvtreej.en;d=g.edgesvtreej.en;if(dtreej.length)if(dtreej.length)treej.length=d;treej.length=d;treej.beg=v;treej.beg=v;算法总体控制：算法总体控制：1 1）初始化：建立初始入选点，并初始化生成树边）初始化：建立初始入选点，并初始化生成树边集集treetree。for(v=1;v=g.n-1;v+)for(v=1;v=g.n-1;v+)treev-1.beg=0;/*treev-1.beg=0;/*此处从顶点此处从顶点v v0 0开始求最小生成树开始求最小生成树*/*/treev-1.en=v;treev-1.en=v;treev-1.length=g.edges0v;treev-1.length=g.edges0v;2 2）依次求当前最小两栖边，并将其加入）依次求当前最小两栖边，并将其加入treetreefor (k=0;k=g.n-3;k+) for (k=0;k=g.n-3;k+) 执行关键一步执行关键一步一般来讲，一般来讲， 由于普里姆算法的由于普里姆算法的时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(nO(n2 2) )，则适于，则适于稠密图。稠密图。程序演示：程序演示：8.5.3最小生成树的克鲁斯卡尔算法KruskalKruskal算法基本思想：算法基本思想： 为使生成树上边的权值之和最小，显然，其中为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含的做法就是：先构造一个只含n n个顶点的子图个顶点的子图SGSG，然后从权值最小的边开始，若它的添加不使然后从权值最小的边开始，若它的添加不使SGSG中中产生回路，则在产生回路，则在SGSG上加上这条边，如此重复，直上加上这条边，如此重复，直至加上至加上n-1n-1条边为止。条边为止。克鲁斯卡尔算法需对克鲁斯卡尔算法需对e e条边按权值进行排序，其时条边按权值进行排序，其时间复杂度为间复杂度为O(eloge)O(eloge)，则适于稀疏图。，则适于稀疏图。算法：算法：（1 1）初始化，）初始化，TV=vTV=v0 0，v v1 1，v vn n ，TE=TE=；（2 2）如如果果TETE具具有有n-1n-1条条边边，则则输输出出最最小小生生成成树树T T，并结束算法。并结束算法。（3 3）在在有有序序的的E E（GG）边边表表序序列列中中，从从当当前前位位置置向向后后寻寻找找满满足足下下面面条条件件的的一一条条边边（u u，v v）：使使得得u u在在一一个个连连通通分分量量上上，v v在在另另一一个个连连通通分分量量上上，即即（u u，v v）是是满满足足此此条条件件权权值值最最小小的的边边，将将其其加加入入到到T T中中，合合并并u u与与v v所所在在的的两两个个连连通通分分量量为为一一个个连连通通分分量量。（4 4）转（）转（2 2）v v0 0v v1 1v v2 2v v3 3v v4 4v v5 56 65 51 15 55 54 42 23 36 66 6(a) (a) 无向网络图无向网络图KruskalKruskal算法动态演示：算法动态演示：1 15 54 42 23 3v v0 0v v1 1v v2 2v v3 3v v4 4v v5 5(b) (b) 最小生成树求解过程最小生成树求解过程5ABCDEF(a)(a)5ABCDEF6(b(b) )5ABCDEF67( (c)c)5ABCDEF6710( (d)d)5ABCDEF671010( (e)e)KruskalKruskal算法构造最小生成树的过程算法构造最小生成树的过程/*/*/*kruskal/*kruskal求解最小生成树算法求解最小生成树算法*/*/*/*文件名文件名kruskal.ckruskal.c函数名函数名kruskal()*/kruskal()*/*/*/voidkruskal(edgeadjlist,edgetree,intcnvx,intn)voidkruskal(edgeadjlist,edgetree,intcnvx,intn)intv=0,j,k;intv=0,j,k;for(j=0;jn;j+)for(j=0;jn;j+)cnvxj=j;/*cnvxj=j;/*设置每一个顶点的连通分量设置每一个顶点的连通分量*/*/for(k=0;kn-1;k+)/*for(k=0;kn-1;k+)/*树中共有树中共有n-1n-1条边条边*/ */while(cnvxadjlistv.beg=cnvxadjlistv.en)v+;while(cnvxadjlistv.beg=cnvxadjlistv.en)v+;/*/*找到属于两个连通分量权最小的边找到属于两个连通分量权最小的边*/ */treek=adjlistv;/*treek=adjlistv;/*将边将边v v加入到生成树中加入到生成树中*/ */for(j=0;jn;j+)/*for(j=0;jn;j+)/*两个连通分量合并为一个连通分量两个连通分量合并为一个连通分量*/ */if(cnvxj=cnvxadjlistv.en)if(cnvxj=cnvxadjlistv.en)cnvxj=cnvxadjlistv.beg;cnvxj=cnvxadjlistv.beg;v+;v+;printf(printf(最小生成树是：最小生成树是：n);n);for(j=0;jn-1;j+)for(j=0;jn-1;j+)printf(%3d%3d%6dn,treej.beg,treej.en,treej.length);printf(%3d%3d%6dn,treej.beg,treej.en,treej.length); 算法算法8.6Kruskal8.6Kruskal求解最小生成树求解最小生成树问题的提出：问题的提出：交交通通咨咨询询系系统统、通通讯讯网网、计计算算机机网网络络常常要要寻寻找找两两结结点点间最短路径；间最短路径；交通咨询系统：交通咨询系统：AA到到BB最短路径；最短路径；计计算算机机网网络络： 发发送送EmailEmail节节省省费费用用 A A到到B B沿沿最最短短路路径传送；径传送；路径长度：路径上边数路径长度：路径上边数路径上边的权值之和路径上边的权值之和最短路径：两结点间权值之和最小的路径；最短路径：两结点间权值之和最小的路径；ABDCFE2415288181013始点 终点 最短路径 路径长度A B （A，C，B） 19 C （A，C） 4 D （A，C，F，D） 25 E （A，C，B，E） 29 F （A，C，F） 124如何求从某源点如何求从某源点到其余各点的最短路径？到其余各点的最短路径？本节介绍求最短路径的两个算法本节介绍求最短路径的两个算法 求求从从某某个个源源点点到到其其他他各各顶顶点点的的最最短短路路径径（单单源源最最短短路径）。路径）。求每一对顶点之间的最短路径。求每一对顶点之间的最短路径。单单源源最最短短路路径径问问题题是是指指：对对于于给给定定的的有有向向网网G=G=（V V，E E），求源点），求源点v v0 0到其它顶点的最短路径。到其它顶点的最短路径。DijkstraDijkstra提出了一个按路径长度递增的顺序逐步产生提出了一个按路径长度递增的顺序逐步产生最短路径的方法，称为最短路径的方法，称为DijkstraDijkstra算法。算法。 DijkstraDijkstra算法的基本思想：算法的基本思想： 把把图图中中所所有有顶顶点点分分成成两两组组，第第一一组组包包括括已已确确定定最最短短路路径径的的顶顶点点，初初始始时时只只含含有有一一个个源源点点，记记为为集集合合S S；第第二二组组包包括括尚尚未未确确定定最最短短路路径径的的顶顶点点，记记为为V-SV-S。按按最最短短路路径径长长度度递递增增的的顺顺序序逐逐个个把把V-SV-S中中的的顶顶点点加加到到S S中中去去，直直至至从从v v0 0出出发发可可以以到到达达的的所所有有顶顶点点都都包包括括到到S S中中。在在这这个个过过程程中中，总总保保持持从从v v0 0到到第第一一组组（S S）各各顶顶点点的的最最短短路路径径都都不不大大于于从从v v0 0到到第第二二组组（V-SV-S）的的任任何何顶顶点点的的最最短短路路径径长长度度，第第二二组组的的顶顶点点对对应应的的距距离离值值是是从从v v0 0到到此此顶顶点点的的只只包包括括第第一一组组（S S）的的顶顶点点为为中中间间顶顶点点的的最最短短路路径径长长度度。对对于于S S中中任任意意一一点点j j，v v0 0到到j j的的路路径径长长度度皆皆小于小于v v0 0到（到（V-SV-S）中任意一点的路径长度。）中任意一点的路径长度。n n引入一个辅助数组引入一个辅助数组dd。它的每一个分量它的每一个分量didi表示当前表示当前找到的从找到的从源点源点v v0 0到到顶点顶点v vi i 的最短路径的长度。初始状的最短路径的长度。初始状态：态：若从源点若从源点v v0 0到顶点到顶点v vi i有边，则有边，则didi为该边上的权值为该边上的权值若从源点若从源点v v0 0到顶点到顶点v vi i 没有边，则没有边，则didi为为+ 。n n一般情况下，假设一般情况下，假设 S S 是已求得的最短路径的终点的集是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从合，则可证明：下一条最短路径必然是从v v0 0 出发，中出发，中间只经过间只经过S S中的顶点便可到达的那些顶点中的顶点便可到达的那些顶点v vx x ( (v vx x V-S V-S ) )的路径中的一条。的路径中的一条。n n每次求得一条最短路径之后，其终点每次求得一条最短路径之后，其终点v vk k 加入集合加入集合S S，然后然后对所有的对所有的v vi i V-SV-S，修改其修改其didi值。值。DijkstraDijkstra算法可描述如下：算法可描述如下：）初始化：把图中的所有顶点分成两组；初始化源初始化：把图中的所有顶点分成两组；初始化源点到各点的距离向量。点到各点的距离向量。 S S：已确定最短路径的点集，初始：已确定最短路径的点集，初始S S v v0 0 ; ; S S：尚未确定最短路径的点集，初始：尚未确定最短路径的点集，初始S S V V（GG）-V-V0 0 ; ; dj dj g.edgesv g.edgesv0 0j, j = 1, 2, , n-1;j, j = 1, 2, , n-1; / n / n为图中顶点个数为图中顶点个数） 求出求出S S与与S S间的最短路径，及相应的点间的最短路径，及相应的点v v dv dv min di , i min di , i V V（GG）- S ; - S ; S S S S U U v v ;v v0 0s sv vminmins sv v0 0s sv vs si iv v0 0s sv vminmins s）由于）由于v v的加入，修改的加入，修改S S中各结点与中各结点与S S中各点的最短中各点的最短距离：距离： di di min di, dv + edgesvi , min di, dv + edgesvi , 对于每一个对于每一个 i i V- S ; V- S ; ）判断：）判断： 若若S = V, S = V, 则算法结束，否则转）。则算法结束，否则转）。i iedgesviedgesviDijkstraDijkstra算法中各辅助数组的变化算法中各辅助数组的变化 如何从表中读取源点如何从表中读取源点0 0到终点到终点v v的最短路径？例如顶点的最短路径？例如顶点A A到到DD的最的最短距离是短距离是d3=25,d3=25,根据根据p3 =5 p3 =5 p5 =2 p5 =2 p2=0p2=0，反过来排，反过来排列，得到路径列，得到路径0, 2, 5,30, 2, 5,3（即（即A A、C C、F F、DD）。）。ABDCFE24152881810134算法实现如下：算法实现如下：/*/*/*/*单源最短路径算法单源最短路径算法文件名文件名:dijkstra.c*/:dijkstra.c*/*/*函数名函数名:spath_dij():spath_dij()、print_gpd()*/print_gpd()*/*/*/#includec_ljjz.c/*#includec_ljjz.c/*引入邻接矩阵创建程序引入邻接矩阵创建程序*/ */typedefenumFALSE,TRUEboolean;/*falsetypedefenumFALSE,TRUEboolean;/*false为为0,true0,true为为1*/1*/typedefintdistm;/*typedefintdistm;/*距离向量类型距离向量类型*/ */typedefintpathm;/*typedefintpathm;/*路径向量类型路径向量类型*/ */voidspath_dij(mgraphg,intv0,pathp,distd)voidspath_dij(mgraphg,intv0,pathp,distd)booleanfinalm;booleanfinalm;inti,k,j,v,min,x;inti,k,j,v,min,x;/*/*第第1 1步步 初始化集合初始化集合S S与距离向量与距离向量d*/d*/for(v=0;vg.n;v+)for(v=0;vg.n;v+)finalv=FALSE;finalv=FALSE;dv=g.edgesv0v;dv=g.edgesv0v; ifif(dvFINITY(dvFINITY&dv!=0)dv!=0)pv=v0;pv=v0; elseelse pv=-1;pv=-1; /*v/*v无前驱无前驱*/*/finalv0=TRUE;dv0=0;/*finalv0=TRUE;dv0=0;/*初始时初始时s s中只有中只有v v0 0一个顶点一个顶点*/ */*/*第第2 2步步 依次找出依次找出n-1n-1个结点加入个结点加入S S中中*/*/for(i=1;ig.n;i+)for(i=1;ig.n;i+)min=FINITY;min=FINITY; forfor(k=0;kg.n;+k)(k=0;kg.n;+k)/* /*找找最最小小边边及及对对应应的的入入选选顶顶点点*/ */ifif(!finalk(!finalk&dkmin)dkmin)v=k;min=dk;v=k;min=dk; /*/*!finalk!finalk表表示示k k还还在在V-SV-S中中*/*/printf(n%c-%dn,g.vexsv,min);printf(n%c-%dn,g.vexsv,min); /* /*输输出出本本次次入入选的顶点及距离选的顶点及距离*/ */if(min=FINITY)return;if(min=FINITY)return;finalv=TRUE;/*Vfinalv=TRUE;/*V加入加入S*/S*/* /*第第3 3步步 修改修改S S与与V-SV-S中各结点的距离中各结点的距离*/ */for(k=0;kg.n;+k)for(k=0;kg.n;+k)if(!finalk&(min+g.edgesvkdk)if(!finalk&(min+g.edgesvkdk)dk=min+g.edgesvk;dk=min+g.edgesvk;pk=v;pk=v;/*endfor*/*endfor*/voidprint_gpd(mgraphg,pathp,distd)voidprint_gpd(mgraphg,pathp,distd)/*/*输出有向图的最短路径输出有向图的最短路径*/ */intst20,i,pre,top=-1;/*intst20,i,pre,top=-1;/*定义栈定义栈stst并初始化空栈并初始化空栈*/ */for(i=0;ig.n;i+)for(i=0;i0)while(top0)printf(%2d,sttop-);printf(%2d,sttop-);voidmain()/*voidmain()/*主程序主程序*/ */mgraphg;/*mgraphg;/*有向图有向图*/*/pathp;/*pathp;/*路径向量路径向量*/*/distd;/*distd;/*最短路径向量最短路径向量*/*/intv0;intv0;creatmgraph1(&g);/*creatmgraph1(&g);/*创建有向网的邻接矩阵创建有向网的邻接矩阵*/ */print(g);/*print(g);/*输出图的邻接矩阵输出图的邻接矩阵*/ */printf(pleaseinputthesourcepointv0:);printf(pleaseinputthesourcepointv0:);scanf(%d,&v0);/*scanf(%d,&v0);/*输入源点输入源点*/ */spath_dij(g,v0,p,d);/*spath_dij(g,v0,p,d);/*求求v0v0到其他各点的最短距离到其他各点的最短距离*/ */print_gpd(g,p,d);/*print_gpd(g,p,d);/*输出输出V0V0到其它各点的路径信息及距离到其它各点的路径信息及距离*/ */n n问题的提法：已知一个各边权值均大于问题的提法：已知一个各边权值均大于0 0的带权有的带权有向图，对每一对顶点向图，对每一对顶点 vi vi vjvj，要求求出要求求出vi vi 与与vjvj之之间的最短路径和最短路径长度。间的最短路径和最短路径长度。 解解决决这这个个问问题题显显然然可可以以利利用用单单源源最最短短路路径径算算法法，具具体体做做法法是是依依次次把把有有向向网网GG中中的的每每个个顶顶点点作作为为源源点点，重重复复执执行行DijkstraDijkstra算算法法n n次次，即即执执行行循循环环体体：总总的的时时间复杂度为间复杂度为O(nO(n3 3) )。for for （v=0v=0；vg.nvg.n；v+v+） spath_dij spath_dij（g g，v v，p p，d d）；）； print_gpd print_gpd（g g，p p，d d）；）； 下面将介绍用弗洛伊德下面将介绍用弗洛伊德(Floyd)(Floyd)算法来实现此功算法来实现此功能能, ,时间复杂度仍为时间复杂度仍为O(nO(n3 3),),但该方法比调用但该方法比调用n n次迪杰斯次迪杰斯特拉方法更直观一些。特拉方法更直观一些。2 弗洛伊德算法的基本思想弗洛伊德算法的基本思想弗洛伊德算法仍然使用前面定义的图的邻接矩阵弗洛伊德算法仍然使用前面定义的图的邻接矩阵edgesNNedgesNN来存储带权有向图。算法的基本思想是来存储带权有向图。算法的基本思想是: :设置一个设置一个NxNNxN的矩阵的矩阵ANNANN，其中除对角线的元，其中除对角线的元素都等于素都等于0 0外，其它元素外，其它元素AijAij的值表示顶点的值表示顶点i i到顶点到顶点j j的的最短路径长度，运算步骤为：最短路径长度，运算步骤为：开始时，以任意两个顶点之间的有向边的权值作开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为为路径长度，没有有向边时，路径长度为 ，此时，此时,A,A ij=edgesij,ij=edgesij, 以以后后逐逐步步尝尝试试在在原原路路径径中中加加入入其其它它顶顶点点作作为为中中间间顶顶点点，如如果果增增加加中中间间顶顶点点后后，得得到到的的路路径径比比原原来来的的路路径径长长度度减减少少了了，则则以以此此新新路路径径代代替替原原路路径径，修修改矩阵元素。具体做法为：改矩阵元素。具体做法为： 第第一一步步，让让所所有有边边上上加加入入中中间间顶顶点点0 0，取取AijAij与与Ai0+A0jAi0+A0j中较小的值作中较小的值作AijAij的值的值. . 第第二二步步，让让所所有有边边上上加加入入中中间间顶顶点点1 1，取取AijAij与与Ai1+A1jAi1+A1j中中较较小小的的值值，完完成成后后得得到到AijAij，如如此此进进行行下下去去，当当第第n n步步完完成成后后，得得到到 AijAij, ,即即为为我我们们所所求结果求结果,A,A ijij表示顶点表示顶点i i到顶点到顶点j j的最短距离。的最短距离。因此，弗洛伊德算法可以描述为因此，弗洛伊德算法可以描述为: : A A(-1)(-1)ij=edgesij;ij=edgesij; /*edges/*edges为为图图的的邻邻接接矩阵矩阵*/ */ A A(k+1)(k+1)ij=minAij=minAk k ij,ij, A Ak k ik+1+Aik+1+Ak k k+1jk+1j其中其中k=-1,1,2,n-2k=-1,1,2,n-2下面给出下面给出FloydFloyd的算法实现。的算法实现。/*/*/*Floyd/*Floyd所有顶点对最短路径算法所有顶点对最短路径算法*/*/*/*文件名：文件名：floyd.cfloyd.c函数名：函数名：floyd1()*/floyd1()*/*/*/typedefintdistmm;/*typedefintdistmm;/*距离向量距离向量*/ */typedefintpathmm;/*typedefintpathmm;/*路径向量路径向量*/ */voidfloyd1(mgraphg,pathp,distd)voidfloyd1(mgraphg,pathp,distd)inti,j,k;inti,j,k;for(i=0;ig.n;i+)/*for(i=0;ig.n;i+)/*初始化初始化*/ */for(j=0;jg.n;j+)for(j=0;jg.n;j+)dij=g.edgesij;dij=g.edgesij;if(i!=j&dijFINITY)pij=i;elsepij=-1;if(i!=j&dijFINITY)pij=i;elsepij=-1; for(k=0;kg.n;k+)/*for(k=0;kg.n;k+)/*递推求解每一对顶点间的最短距离递推求解每一对顶点间的最短距离*/ */for(i=0;ig.n;i+)for(i=0;ig.n;i+)for(j=0;jg.n;j+)for(j=0;j(dik+dkj)dij(dik+dkj) )dij=dik+dkj;dij=dik+dkj;pij=k;pij=k;算法算法8.88.8求网络中每一对顶点之间的最短路径求网络中每一对顶点之间的最短路径 203168359142014014092092350835086060例例求下图中所在顶点对之间的最短路径。求下图中所在顶点对之间的最短路径。DD-1D0D1D2D301230123012301230123001 401 401 10 301 10 301931 092 092 092 12 092 11 0822350834073406340634063 60 60 609 10 609 10 60PP-1P0P1P2P301230123012301230123010 -1 0 -1 0 -1 0 -1 011 -1 011 -1 0311 -1 -1 11 -1 -1 11 -1 -1 112 -1 113 -1 31222 -1 220 -1 020 -1 120 -1 120 -1 13 -1 -1 3 -1 -1 -1 3 -1 -1 -1 3 -1 223 -1 223 -18.7拓扑排序有向无环图：没有回路的有向图有向无环图：没有回路的有向图 某工程可分为某工程可分为7 7个子工程，若用顶点表示子工程个子工程，若用顶点表示子工程（也称活动），（也称活动）， 用弧表示子工程间的顺序关系。工用弧表示子工程间的顺序关系。工程流程可用如下程流程可用如下AOVAOV网表示网表示AOVAOV网网(activityonvertexnet)(activityonvertexnet)用顶点表示活动，边表示活动的顺序关系的有向图用顶点表示活动，边表示活动的顺序关系的有向图称为称为AOVAOV网。网。应用：应用： 工程流程、生产过程中各道工序的流程、程序工程流程、生产过程中各道工序的流程、程序流程、课程的流程。流程、课程的流程。一一AOVAOV网网对工程问题，人们至少关心如下两类问题：对工程问题，人们至少关心如下两类问题：1 1）工程能否顺序进行，即工程流程是否）工程能否顺序进行，即工程流程是否“ “合理合理” ”？2 2）完成整项工程至少需要多少时间，哪些子工程是影响）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程？工程进度的关键子工程？二二AOVAOV网与拓扑排序网与拓扑排序拓扑排序拓扑排序 V V5 5 V V3 3 V V2 2 V V0 0 V V1 1 V V4 4 V V6 6例例11某工程可分为某工程可分为V V0 0、V V1 1、V V2 2、V V3 3、V V4 4、V V5 5、V V6 677个子工程，个子工程， 工程流程可用如下工程流程可用如下AOVAOV网表示。其中顶网表示。其中顶点：表示子工程（也称活动），点：表示子工程（也称活动）， 弧：表示子工程间弧：表示子工程间的顺序关系。的顺序关系。为求解工程流程是否为求解工程流程是否“ “合理合理” ”，通常用，通常用AOVAOV网的网的有向图表示工程流程。有向图表示工程流程。 V V5 5 V V3 3 V V2 2 V V0 0 V V1 1 V V4 4 V V6 6例例课程流程图课程流程图某校计算机专业课程流程可某校计算机专业课程流程可AOVAOV网表示。其中顶点：网表示。其中顶点：表示课程（也称活动），表示课程（也称活动）， 弧：表示课程间的先修关系；弧：表示课程间的先修关系；课程代号课程名称先修课程C0C1C2C3C4C5C6C7C8高等数学信息技术基础离散数学数据结构程序设计语言编译原理操作系统电子线路基础计算机组成原理无无C0，C1C2，C4C1C3，C4C3，C8C0C7C0C2C1C7C8C6C3C4C5如何安排施工计划？如何安排施工计划？如何安排教学计划？如何安排教学计划？两个可行的学习计划为：两个可行的学习计划为：C C0 0C C1 1C C2 2C C4 4C C7 7C C8 8C C3 3C C6 6C C5 5和和C C1 1C C0 0C C7 7C C8 8C C2 2C C4 4C C3 3C C5 5C C6 6可行的计划的特点：若在流程图中顶点可行的计划的特点：若在流程图中顶点v v是顶点是顶点uu的前趋，则在计划序列中顶点的前趋，则在计划序列中顶点vv也是也是u u的前趋。的前趋。拓扑序列拓扑序列：有向图：有向图D D的一个顶点序列称作一个拓扑序的一个顶点序列称作一个拓扑序列，如果该序列中任两顶点列，如果该序列中任两顶点vv、uu，若在，若在D D中中v v是是u u前前趋，则在序列中趋，则在序列中v v也是也是u u前趋。前趋。拓扑排序：拓扑排序： 就是将有向图中顶点排成拓扑序列。就是将有向图中顶点排成拓扑序列。拓扑排序的应用拓扑排序的应用 安排施工计划安排施工计划 判断工程流程的是否合理判断工程流程的是否合理 如何判断如何判断AOVAOV网（有向图）网（有向图）是否存在有向回路？是否存在有向回路？AOVAOV网（有向图）网（有向图）不存在有向回路不存在有向回路当且仅当能对当且仅当能对AOVAOV网网进行拓扑排序进行拓扑排序1) 1) 输入输入AOVAOV网络。令网络。令 n n 为顶点个数。为顶点个数。2) 2) 在在AOVAOV网络中选一个没有直接前驱（入度为网络中选一个没有直接前驱（入度为0 0）的顶点的顶点, , 并输出之并输出之; ; 3) 3) 从图中删去该顶点从图中删去该顶点, , 同时删去所有它发出的有向同时删去所有它发出的有向 边边; ;4) 4) 重复以上重复以上(2)(2)、(3)(3)步步, , 直到直到全部顶点均已输出，拓扑有序序列形成，拓扑全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或排序完成；或图中还有未输出的顶点，但已跳出处理循环。图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时驱，再也找不到没有前驱的顶点了。这时AOVAOV网络中必定存在有向环。网络中必定存在有向环。拓扑排序过程拓扑排序的过程C0C1C2C3C4C5(a) (a) 有向无环图有向无环图C1C2C5C3(c) (c) 输出顶点输出顶点C0C0C0C2C5C1C3(d) (d) 输出顶点输出顶点C3C3C0C1C2C3C4C5(b) (b) 输出输出C4C4C1C2C5(e) (e) 输出顶点输出顶点C2C2C5C1(f) (f) 输出顶点输出顶点C1C1C5(g) (g) 输出顶点输出顶点C5C5 最后得到的拓扑有序序列为最后得到的拓扑有序序列为 C C4 4 , C , C0 0 , C , C3 3 , , C C2 2 , C , C1 1 , C, C5 5 。它满足图中给出的所有前驱和后继。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如关系，对于本来没有这种关系的顶点，如C C4 4和和C C2 2，也排出了先后次序关系。也排出了先后次序关系。(h) (h) 拓扑排序完成拓扑排序完成AOVAOV网络及其邻接表表示网络及其邻接表表示 C0 C1 C2 C3 0 C4 C5 0012345id data firstedgeid data firstedge 130103 1 adjvex nxetadjvex nxet 3 0 5 1 5 0 0 1 5 0C0C1C2C3C4C5这种带入度的邻接表存储结构定义如下：这种带入度的邻接表存储结构定义如下：#definem20#definem20typedefcharvertextype;typedefcharvertextype;typedefstructnode/*typedefstructnode/*边结点类型定义边结点类型定义*/ */intadjvex;intadjvex;structnode*next;structnode*next;edgenode;edgenode;typedefstructde/*typedefstructde/*带顶点入度的头结点定义带顶点入度的头结点定义*/ */edgenode*firstedge;edgenode*firstedge;vertextypevertex;vertextypevertex;intid;intid;/* /*顶点的入度域顶点的入度域*/ */vertexnode;vertexnode;typedefstruct/*AOVtypedefstruct/*AOV网络的邻接表结构网络的邻接表结构*/ */vertexnodeadjlistm;vertexnodeadjlistm;intn,e;intn,e;aovgraph;aovgraph;基于这种存储结构，拓扑排序算法可描述为算法基于这种存储结构，拓扑排序算法可描述为算法8.98.9。/*/*/*/* 拓拓 扑扑 排排 序序 算算 法法 */ */*/*文件名文件名:topsort.c:topsort.c函数名函数名:topsort()*/:topsort()*/*/*/inttopsort(aovgraphg)/*inttopsort(aovgraphg)/*函数返回拓扑排序输出的顶点个数函数返回拓扑排序输出的顶点个数*/ */intk=0,i,j,v,flagm;intk=0,i,j,v,flagm;intqueuem;/*intqueuem;/*队列队列*/ */inth=0,t=0;inth=0,t=0;edgenode*p;edgenode*p;for(i=0;ig.n;i+)flagi=0;/*for(i=0;ig.n;i+)flagi=0;/*访问标记初始化访问标记初始化*/ */for(i=0;ig.n;i+)/*for(i=0;ig.n;i+)/*先将所有入度为先将所有入度为0 0的顶点进队的顶点进队*/ */if(g.adjlisti.id=0&flagi=0)if(g.adjlisti.id=0&flagi=0)queue+t=i;flagi=1;queue+t=i;flagi=1;while(ht)/*while(h,g.adjlistv.vertex);printf(%c-,g.adjlistv.vertex);k+;/*k+;/*计数器加计数器加1*/1*/p=g.adjlistv.firstedge;p=g.adjlistv.firstedge;while(p)/*while(p)/*将所有与将所有与v v邻接的顶点的入度减邻接的顶点的入度减1*/1*/j=p-adjvex;j=p-adjvex;if(-g.adjlistj.id=0&flagj=0)if(-g.adjlistj.id=0&flagj=0)/*/*若入度为若入度为0 0则将其进队则将其进队*/ */queue+t=j;flagj=1;queue+t=j;flagj=1;p=p-next;p=p-next;returnk;returnk; 算法算法8.98.9拓扑排序拓扑排序8.8关键路径n n如果在无有向环的带权有向图中如果在无有向环的带权有向图中 用有向边表示一个工程中的活动用有向边表示一个工程中的活动( (Activity)Activity) 用边上权值表示活动持续时间用边上权值表示活动持续时间( (Duration)Duration) 用顶点表示事件用顶点表示事件 ( (Event)Event)n n则这样的有向图叫做用边表示活动的网络，简称则这样的有向图叫做用边表示活动的网络，简称 AOE (Activity On Edges) AOE (Activity On Edges) 网络。网络。n nAOEAOE网络在某些工程估算方面非常有用。例如，网络在某些工程估算方面非常有用。例如，可以使人们了解：可以使人们了解： (1) (1) 完成整个工程至少需要多少时间完成整个工程至少需要多少时间( (假设网络假设网络中没有环中没有环)? )? (2) (2) 为缩短完成工程所需的时间为缩短完成工程所需的时间, , 应当加快哪些应当加快哪些活动活动? ? n n在在AOEAOE网络中网络中, , 有些活动顺序进行，有些活动并行有些活动顺序进行，有些活动并行进行。进行。n n从源点到各个顶点，以至从源点到汇点的有向路径从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。路径上所有活动都完成了，整个工程才算完成。n n因此，完成整个工程所需的时间取决于从源点到汇因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持点的最长路径长度，即在这条路径上所有活动的持续时间之和。续时间之和。这条路径长度最长的路径就叫做关键这条路径长度最长的路径就叫做关键路径路径( (Critical Path)Critical Path)。 要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。 关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径.例如，下图就是一个AOE网。V3V1a a4=34=3a a1=31=3a a2=22=2a a6=36=3a a5=45=4a a3=23=2a a7=27=2a a8=18=1顶点表示事件顶点表示事件边表示活动边表示活动事件事件VjVj发生表示发生表示 akj已结束已结束ak VjVi事件事件ViVi发生表示发生表示 ak可以开始可以开始 AOEAOE网网V2V4V5V6v0v1v2v4v3v6v7v8v5v9a0=8a1=6a2=7a3=3a4=10a5=9a6=9a7=13a11=2a10=8a9=19a8=4a13=14a12=6a14=10关键路径求解方法：关键路径求解方法：在在AOEAOE网中从源点网中从源点v v0 0到事件到事件v vi i的最长路径长度是的最长路径长度是事件事件v vi i的最早发生时间。这个时间决定了所有以的最早发生时间。这个时间决定了所有以v vi i为尾的弧表示的活动的最早开始时间。为尾的弧表示的活动的最早开始时间。 定义以下几个量：定义以下几个量：e e（i i）：）：表示活动表示活动a ai i的最早开始时间。的最早开始时间。l l（i i）：）：表示活动最迟开始时间的向量。表示活动最迟开始时间的向量。关键活动特征：关键活动特征：e e（i i）=l=l（i i）l l（j j）-e-e（j j）的值表示完成活动）的值表示完成活动a aj j的时间余量，提的时间余量，提前完成非关键活动并不能提高整个工程的进度。前完成非关键活动并不能提高整个工程的进度。 事件可能的最早开始时间事件可能的最早开始时间v ve e（i i）：）：对于某一事对于某一事件件v vi i，它可能的最早发生时间它可能的最早发生时间v ve e（i i）是从源点到是从源点到顶点顶点v vi i的最大路径长度。的最大路径长度。事件允许的最晚发生时间事件允许的最晚发生时间v vl l（i i）：）：对于某一事件对于某一事件v vi i，它允许的最晚发生时间是在保证按时完成整个工它允许的最晚发生时间是在保证按时完成整个工程的前提下，该事件最晚必须发生的时间程的前提下，该事件最晚必须发生的时间 vve e（0 0）=0=0；vve e（i i）=vi集合集合p p（i i）AOEAOE网网络络，可可按按其其中中的的一一个个拓拓扑扑序序列列（v v0 0、v v1 1、v v2 2、v v4 4、v v3 3、v v6 6、v v7 7、v v5 5、v v8 8、v v9 9）求解每个事件的最早开始时间：）求解每个事件的最早开始时间：v ve e（0 0）=0=0v ve e（1 1）=8=8，v ve e（2 2）=6=6，v ve e（4 4）=7=7；v ve e（3 3）=maxv=maxve e（1 1）+len+len（a a3 3），），v ve e（2 2）+len+len（a a4 4）=16=16；v ve e（6 6）=maxv=maxve e（2 2）+len+len（a a5 5），），v ve e（4 4）+len+len（a a6 6）=16=16；v ve e（7 7）=maxv=maxve e（6 6）+len+len（a a1111），），v ve e（4 4）+len+len（a a7 7）=20=20；v ve e（5 5）=v=ve e（3 3）+len+len（a a8 8）=20=20；v ve e（8 8）=maxv=maxve e（3 3）+len+len（a a9 9），v ve e（6 6）+len+len（a a1010），v ve e（7 7）+len+len（a a1212）=35=35；v ve e（9 9）=maxv=maxve e（5 5）+len+len（a a1313），），v ve e（8 8）+len+len（a a1414）=45=45； ee（k k）=v=ve e（i i）；）；ll（k k）=v=vl l（j j）-len-len（v ）；）； 求求每每一一个个顶顶点点i i的的最最晚晚允允许许发发生生时时间间v vl l（i i）可可以以沿沿图图中中的的汇汇点点开开始始，按按图图中中的的逆逆拓拓扑扑序序逐逐个个递递推推出出每个顶点的每个顶点的v vl l（i i）。）。vvl l（n-1n-1）=v=ve e（n-1n-1）；）；vvl l（i i）=vi集合集合s s（i i）AOEAOE网网，按按照照（8-78-7）式式求求得得的的各各个个事事件件允允许许的的最最晚晚发发生生时时间间如如下：下：v vl l（9 9）=v=ve e（9 9）=45=45v vl l（8 8）=v=vl l（9 9）-len-len（v ）=45-10=35=45-10=35v vl l（5 5）=v=vl l（9 9）-len-len（v ）=45-14=31=45-14=31v vl l（7 7）=v=vl l（8 8）-len-len（v ）=35-6=29=35-6=29v vl l（ 6 6） =minv=minvl l（ 7 7） -len-len（ v ） ， v vl l（ 8 8） -len-len（ v ）=min27=min27，27=2727=27v vl l（ 3 3） =minv=minvl l（ 5 5） -len-len（ v ） ， v vl l（ 8 8） -len-len（ v ）=min27=min27，16=1616=16v vl l（ 4 4） =minv=minvl l（ 6 6） -len-len（ v ） ， v vl l（ 7 7） -len-len（ v ）=min18=min18，16=1616=16v vl l（ 2 2） =minv=minvl l（ 3 3） -len-len（ v ） ， v vl l（ 6 6） -len-len（ v ） =min=min66，18=618=6v vl l（1 1）=v=vl l（3 3）-len-len（v ）=13=13v vl l（0 0）=minv=minvl l（1 1）-8-8，v vl l（2 2）-6-6，v vl l（4 4）-7=min5-7=min5，0 0，9=09=0顶点vevl活动ell-e关键活动v0v1v2v3v4v5v6v7v8v90861672016203545013616163127293545a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14000866771616161620203550913618181627162727293135509501211911011119110作业：作业：8-98-98-108-108-118-11