数据结构 第7章 图.ppt

n n图的定义和术语图的定义和术语n n图的存储结构图的存储结构n n图的遍历与连通性图的遍历与连通性 n n最小生成树最小生成树n n活动网络活动网络n n最短路径最短路径 7.1 图的定义和术语图的定义和术语n n图形结构的形式定义图形结构的形式定义图形结构的形式定义图形结构的形式定义 图是由顶点集合图是由顶点集合图是由顶点集合图是由顶点集合(vertex)及顶及顶及顶及顶点间的关系集合组成的一种数据结构点间的关系集合组成的一种数据结构点间的关系集合组成的一种数据结构点间的关系集合组成的一种数据结构：GraphGraph(V V,R R)其中：其中：其中：其中：V V=x x|x x 某个数据对象某个数据对象某个数据对象某个数据对象 ，是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；RR边的边的边的边的有限集合有限集合有限集合有限集合R R=(=(x x,y y)|)|x x,y y V V 无向图无向图无向图无向图 或或或或R R=y|x x,y y V V&PathPath(x x,y y)有向图有向图有向图有向图 是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)edge)集合。集合。集合。集合。PathPath(x x,y y)表示从表示从表示从表示从 x x 到到到到 y y 的一条单向通路的一条单向通路的一条单向通路的一条单向通路,它是有方向它是有方向它是有方向它是有方向的。的。的。的。x x弧尾，弧尾，弧尾，弧尾，y y弧头弧头弧头弧头 n n有向图与无向图有向图与无向图有向图与无向图有向图与无向图 1.1.有向图中：边用有向图中：边用有向图中：边用有向图中：边用 x,y表示，且表示，且表示，且表示，且x x与与与与y y是有序的。是有序的。是有序的。是有序的。a.a.有向图中的边称为有向图中的边称为有向图中的边称为有向图中的边称为“弧弧弧弧”b.xb.x弧尾或弧尾或弧尾或弧尾或初始点初始点初始点初始点 yy弧头或终端点弧头或终端点弧头或终端点弧头或终端点vv无向图：边用无向图：边用无向图：边用无向图：边用(x,y)x,y)表示，且顶表示，且顶表示，且顶表示，且顶x x与与与与 y y是无序的。是无序的。是无序的。是无序的。n n完全图完全图完全图完全图vv 在具有在具有在具有在具有n n 个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为 n n(n n-1)-1)vv 在具有在具有在具有在具有n n 个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为 n n(n n-1)/2-1)/2n n顶点的度顶点的度顶点的度顶点的度vv无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目vv有向图有向图有向图有向图：入度入度入度入度ID(ID(v v)：以该顶点为头的弧的数目以该顶点为头的弧的数目以该顶点为头的弧的数目以该顶点为头的弧的数目 出度出度出度出度OD(OD(v v)：以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目 在在有有向向图图中中,顶顶点点的的度度等等于于该该顶顶点点的的入入度度与与出出度之和。度之和。n n邻接点邻接点vv 无无无无向图：两顶点之间有条边，则两顶点互为邻接点向图：两顶点之间有条边，则两顶点互为邻接点向图：两顶点之间有条边，则两顶点互为邻接点向图：两顶点之间有条边，则两顶点互为邻接点 x y (x,y)x y (x,y)vv 有向图有向图有向图有向图：从：从x到到y有有一条弧，则一条弧，则y是是x的的邻接点，邻接点，但但x不是不是y的邻接点的邻接点 x y n n权权 某某些些图图的的边边具具有有与与它它相相关关的的数数,称称之之为为权权。这种带权图叫做网络。这种带权图叫做网络。n n子子图图 设设有有两两个个图图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。n n路径路径路径路径 在图在图在图在图 GG(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 v vi i 出发出发出发出发,沿一些边沿一些边沿一些边沿一些边经过一些顶点经过一些顶点经过一些顶点经过一些顶点 v vp p1 1,v vp p2 2,v vpmpm，到达顶点到达顶点到达顶点到达顶点v vj j。则称顶点则称顶点则称顶点则称顶点序列序列序列序列 (v vi i v vp p1 1 v vp p2 2.v vpm pm v vj j )为从顶点为从顶点为从顶点为从顶点v vi i 到顶点到顶点到顶点到顶点 v vj j 的路径的路径的路径的路径。它经过的边它经过的边它经过的边它经过的边(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)应是属应是属应是属应是属于于于于E E的边。的边。的边。的边。n n路径长度路径长度路径长度路径长度 uu非带权图的路径长度是指此路径上边非带权图的路径长度是指此路径上边非带权图的路径长度是指此路径上边非带权图的路径长度是指此路径上边/弧的条数。弧的条数。弧的条数。弧的条数。uu带权图的路径长度是指路径上各边带权图的路径长度是指路径上各边带权图的路径长度是指路径上各边带权图的路径长度是指路径上各边/弧的权之和。弧的权之和。弧的权之和。弧的权之和。n n简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均不互均不互相重复相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。n n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶点与最后一个顶点vm 重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。n n连通图与连通分量连通图与连通分量 在无向图中在无向图中,若从顶点若从顶点v1到到顶点顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通的。如果是连通的。如果图中任意一对顶点都是连通的图中任意一对顶点都是连通的,则称此图是连通则称此图是连通图。非连通图的极大连通子图叫做连通分量。图。非连通图的极大连通子图叫做连通分量。n n强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中在有向图中在有向图中,若对于每一对顶若对于每一对顶若对于每一对顶若对于每一对顶点点点点v vi i和和和和v vj j,都存在一条从都存在一条从都存在一条从都存在一条从v vi i到到到到v vj j和从和从和从和从v vj j到到到到v vi i的路径的路径的路径的路径,则称此则称此则称此则称此图是强连通图。非强连通图的极大强连通子图叫做强图是强连通图。非强连通图的极大强连通子图叫做强图是强连通图。非强连通图的极大强连通子图叫做强图是强连通图。非强连通图的极大强连通子图叫做强连通分量。连通分量。连通分量。连通分量。n n生成树生成树生成树生成树 一个连通图的生成树是它的极小连通子图，在一个连通图的生成树是它的极小连通子图，在一个连通图的生成树是它的极小连通子图，在一个连通图的生成树是它的极小连通子图，在n n个顶点的情形下，有个顶点的情形下，有个顶点的情形下，有个顶点的情形下，有n n-1-1条边。条边。条边。条边。vv 生成树是对指连通图来而言的生成树是对指连通图来而言的生成树是对指连通图来而言的生成树是对指连通图来而言的vv 是连同图的极小连同子图是连同图的极小连同子图是连同图的极小连同子图是连同图的极小连同子图vv 包含图中的所有顶点包含图中的所有顶点包含图中的所有顶点包含图中的所有顶点vv 有且仅有有且仅有有且仅有有且仅有n-1n-1条边条边条边条边n n本章不予本章不予本章不予本章不予 讨论的图讨论的图讨论的图讨论的图7.2 图的存储表示图的存储表示n n顶点表顶点表:一个一个记录各个顶点信息记录各个顶点信息的一维数组，的一维数组，n n邻接矩阵：邻接矩阵：一个一个表示各个顶点之间的关系（边表示各个顶点之间的关系（边或弧）或弧）的二维数组。的二维数组。n n设图设图 G=(V,E)是一个有是一个有 n 个顶点的图，则图的个顶点的图，则图的邻接矩阵邻接矩阵G.arcsnn 定义为：定义为：n nG.arcsij=1 若若 或或(Vi,Vj)EEn n 0 反之反之1.邻接矩阵邻接矩阵(Adjacency Matrix)表示法表示法（数组表示法）（数组表示法）1）类型定义）类型定义#define MAX_VERTEX_NUM 20/最大顶点数最大顶点数typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵类型邻接矩阵类型typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点表顶点表AdjMatrix arcs;/邻接矩阵邻接矩阵int vexnum,arcnum;/图的顶点数和弧数图的顶点数和弧数 MGraph;n n无向图的邻接矩阵是以主对角线对称的，有向无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。图的邻接矩阵可能是不对称的。n n在有向图中：在有向图中：第第 i 行行 1 的个数就是顶点的个数就是顶点 i 的出度，的出度，第第 j 列列 1 的个数就是顶点的个数就是顶点 j 的入度。的入度。n n在无向图中在无向图中,第第 i 行行(列列)1 的个数就是顶点的个数就是顶点i 的的度。度。网的邻接矩阵网的邻接矩阵G.arcsij=Wi,j若若 或或(Vi,Vj)E 反之反之int LocateVex(MGraph G,char u)int i;for(i=0;iG.vexnum;i+)if(u=G.vexsi)return i;if(i=G.vexnum)printf(Error u!n);exit(1);return 0;2）建立邻接矩阵算法7.1,7.2,p162163void CreateMGraph(MGraph&G)int i,j,k,w;char v1,v2;printf(Input vexnum&arcnum:);scanf(%d,%d,&G.vexnum,&G.arcnum);printf(Input Vertices:);scanf(%s,G.vexs);/for(i=0;iG.vexnum;i+)/scanf(%c,&G.vexsi);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij=0;for(k=0;kG.arcnum;k+)printf(Input Arcs(v1,v2&w):n);scanf(%c%c,%d,&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcsij=w;/G.arcsji=w;return;void PrintMGraph(MGraph G)int i,j;printf(Output Vertices:);printf(%s,G.vexs);printf(n);printf(Output AdjMatrix:n);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)printf(%4d,G.arcsij);printf(n);return;邻接表邻接表(Adjacency List)一种链式存储结构一种链式存储结构n 把同一个顶点发出的边链接在同一个边链表把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结中，链表的每一个结点代表一条边，叫做表结点（边结点），邻接点域点（边结点），邻接点域adjvex保存与该边相保存与该边相关联的另一顶点的顶点下标关联的另一顶点的顶点下标，链域链域nextarc存存放指向同一链表中下一个表结点的指针放指向同一链表中下一个表结点的指针，数，数据域据域info存放边的权。边链表的表头指针存放存放边的权。边链表的表头指针存放在头结点中。在头结点中。头结点以顺序结构存储，其数据头结点以顺序结构存储，其数据域域data存放顶点信息，链域存放顶点信息，链域firstarc指向链表指向链表中第一个顶点。中第一个顶点。表结点表结点头结点头结点adjvex nextarc infodatafirstarc存储表示存储表示typedeftypedef structstruct ArcNodeArcNode intint adjvexadjvex;structstruct ArcNodeArcNode*nextarcnextarc;intint info;info;ArcNodeArcNode;/;/边结点类型边结点类型边结点类型边结点类型typedeftypedef structstruct VNodeVNode VertexTypeVertexType data;data;ArcNodeArcNode*firstarcfirstarc;VNodeVNode,AdjListAdjListMAX_VERTEX_NUM;MAX_VERTEX_NUM;typedeftypedef structstruct AdjListAdjList vertices;/vertices;/邻接表邻接表邻接表邻接表intint vexnumvexnum,arcnumarcnum;ALGraphALGraph;n n有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表n n在有向图的邻接表中，第在有向图的邻接表中，第 i 个链表中结点的个个链表中结点的个数是数是顶点顶点Vi的出度的出度。n n在有向图的逆邻接表中，第在有向图的逆邻接表中，第 i 个链表中结点的个链表中结点的个数是个数是顶点顶点Vi 的入度的入度。n n带权图的边结点中带权图的边结点中info保存该边上的权值保存该边上的权值。n n顶点顶点 Vi 的边链表的头结点存放在下标为的边链表的头结点存放在下标为 i 的顶的顶点数组中。点数组中。n n在邻接表的边链表中，在邻接表的边链表中，各个边结点的链入顺序各个边结点的链入顺序任意，视边结点输入次序而定。任意，视边结点输入次序而定。n n设图中有设图中有 n 个顶点，个顶点，e 条边，则条边，则用邻接表表示用邻接表表示无向图时无向图时，需要，需要 n 个顶点结点，个顶点结点，2e 个边结点；个边结点；用用邻接表表示有向图时邻接表表示有向图时，若不考虑逆邻接表，若不考虑逆邻接表，只需只需 n 个顶点结点，个顶点结点，e 个边结点。个边结点。n n建立邻接表的时间复杂度为建立邻接表的时间复杂度为O(n*e)。若顶点信若顶点信息即为顶点的下标，则时间复杂度为息即为顶点的下标，则时间复杂度为O(n+e)。网络网络(带权图带权图)的邻接表的邻接表int LocateVex(ALGraph G,char u)int i;for(i=0;iG.vexnum;i+)if(u=G.verticesi.data)return i;if(i=G.vexnum)printf(Error u!n);exit(1);return 0;void CreateALGraph_adjlist(ALGraph&G)int i,j,k,w;char v1,v2;ArcNode*p;printf(Input vexnum&arcnum:);scanf(%d,%d,&G.vexnum,&G.arcnum);printf(Input Vertices:);for(i=0;iG.vexnum;i+)scanf(%c,&G.verticesi.data);G.verticesi.firstarc=NULL;printf(Input Arcs(v1,v2&w):n);for(k=0;kadjvex=j;p-info=w;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;return;十字链表十字链表(Orthogonal List)有向图的另一种链式存储结构有向图的另一种链式存储结构n n可看作是将有向图的邻接表和逆邻接表结合可看作是将有向图的邻接表和逆邻接表结合的一种链表的一种链表headvextailvexhlinktlinkinfo弧结点弧结点firstindatafirstout顶点结点顶点结点tailvex弧尾，headvex弧头，hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧data顶点信息，firstin以该顶点为头的第一个弧结点，firstout以该结点为尾的第一个弧结点typedeftypedef structstruct ArcBoxArcBox intint headvexheadvex,tailvextailvex;structstruct ArcBoxArcBox*hlinkhlink,*,*tlinktlink;intint info;info;ArcBoxArcBox;typedeftypedef structstruct VexNodeVexNode VertexTypeVertexType data;data;ArcBoxArcBox*firstinfirstin,*,*firstoutfirstout;VexNodeVexNode;typedeftypedef structstruct VexNode xlistVexNode xlistMAX_VERTEX_NUM;MAX_VERTEX_NUM;intint vexnumvexnum,arcnumarcnum;OLGraphOLGraph;/图的十字链表表示图的十字链表表示图的十字链表表示图的十字链表表示uu十字链表的结构十字链表的结构图的遍历图的遍历n n从图中某一顶点出发访遍图中其余顶点，且使从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，就叫做每个顶点仅被访问一次，就叫做图的遍历图的遍历(Traversing Graph)。n n图的遍历算法是求解图的图的遍历算法是求解图的连通性问题连通性问题、拓扑排拓扑排序序和求和求 关键路径关键路径等算法的基础。等算法的基础。n n两条遍历图的路径：两条遍历图的路径：深度优先搜索深度优先搜索、广度优先广度优先搜索搜索n n图中可能存在回路，且图的任一顶点都可能与图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。沿着某些边又回到了曾经访问过的顶点。n n为了避免重复访问，可设置一个标志顶点是否为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组被访问过的辅助数组 visited ，它的初始状态它的初始状态为为 0，在图的遍历过程中，一旦某一个顶点，在图的遍历过程中，一旦某一个顶点 i 被被访问，就立即让访问，就立即让 visited i 为为 1，防止它被多次，防止它被多次访问。访问。深度优先搜索深度优先搜索DFS(Depth First Search)n n深度优先搜索的示例深度优先搜索的示例n nDFS 在访问图中某一起始顶点在访问图中某一起始顶点 v 后，由后，由 v 出发，出发，访问它的任一邻接顶点访问它的任一邻接顶点 w1；再从再从 w1 出发，访出发，访问与问与 w1邻邻 接但还没有访问过的顶点接但还没有访问过的顶点 w2；然后然后再从再从 w2 出发，进行类似的访问，出发，进行类似的访问，如此进行如此进行下去，直至到达所有的邻接顶点都被访问过的下去，直至到达所有的邻接顶点都被访问过的顶点顶点 u 为止。接着，退回一步，退到前一次刚为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。直到连通图中所有顶点都被访问过为止。n nDFS 的思路的思路（1）从图中的某个顶点）从图中的某个顶点V出发，访问之；出发，访问之；（2）依次从顶点）依次从顶点V的未的未被被访问过的邻接点出发，访问过的邻接点出发，深度优先遍历图，直到图中所有和顶点深度优先遍历图，直到图中所有和顶点V 有路径相通的顶点都被访问到；有路径相通的顶点都被访问到；（3）若此时图中尚有顶点未被访问到，则另选）若此时图中尚有顶点未被访问到，则另选 一个未被访问过的顶点作起始点，重复上一个未被访问过的顶点作起始点，重复上 述（述（1）（）（2）的操作，直到图中所有的顶）的操作，直到图中所有的顶 点都被访问到为止。点都被访问到为止。图的深度优先搜索算法图的深度优先搜索算法int visitedMAX_VERTEX_NUM;void DFS(ALGraph G,int v)ArcNode*p;printf(%c,G.verticesv.data);visitedv=1;p=G.verticesv.firstarc;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-nextarc;/从第v个顶点出发DFS整个图的DFS遍历void DFSTraverse(ALGraph G)for(int v=0;vG.vexnum;+v)visitedv=0;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);对于连通图，从一个顶点出发，调用DFS函数即可将所有顶点都遍历到。算法分析算法分析n n图中有图中有 n 个顶点，个顶点，e 条边。条边。n n如果用邻接表表示图，沿如果用邻接表表示图，沿 Firstarc nextarc 链可以找到某个顶点链可以找到某个顶点 v 的所有邻接顶点的所有邻接顶点 w。由由于总共有于总共有 2e 个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问而且对所有顶点递归访问1次，所以遍次，所以遍历图的时间复杂性为历图的时间复杂性为O(n+e)。n n如果用邻接矩阵表示图，则查找每一个顶点的如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为所有的边，所需时间为O(n)，则遍历图中所有则遍历图中所有的顶点所需的时间为的顶点所需的时间为O(n2)。广度优先搜索广度优先搜索BFS(Breadth First Search)n n广度优先搜索的示例广度优先搜索的示例 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树n n使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点 v 之后，之后，由由 v 出发，依次访问出发，依次访问 v 的各个未曾被访问过的的各个未曾被访问过的邻接顶点邻接顶点 w1,w2,wt，然后再顺序访问然后再顺序访问 w1,w2,wt 的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，有还未被访问过的邻接顶点，如此做下去，如此做下去，直到图中所有顶点都被访问到为止。直到图中所有顶点都被访问到为止。n n广度优先搜索是一种分层的搜索过程，每向前广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。是一个递归的过程，其算法也不是递归的。n nBFS 的思路的思路（1）从图中的某个顶点）从图中的某个顶点V出发，访问之；出发，访问之；（2）依次访问顶点）依次访问顶点V的各个未的各个未被被访问过的邻接访问过的邻接 点，将点，将V的全部邻接点都访问到；的全部邻接点都访问到；（3）分别从这些邻接点出发，依次访问它们的）分别从这些邻接点出发，依次访问它们的 未被访问过的邻接点，并使未被访问过的邻接点，并使“先被访问的先被访问的顶顶 点的邻接点点的邻接点”先于先于“后被访问的顶点的邻后被访问的顶点的邻接接 点点”被访问，直到图中所有已被访问过的被访问，直到图中所有已被访问过的顶顶 点的邻接点都被访问到。点的邻接点都被访问到。n n为了实现逐层访问，算法中使用了一个队列，为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。便于向下一层访问。n n与深度优先搜索过程一样，为避免重复访问，与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶给被访问过的顶点加标记。点加标记。图的广度优先搜索算法图的广度优先搜索算法void BFSTraverse(ALGraph G)for(int v=0;vG.vexnum;+v)visitedv=0;for(v=0;vadjvex)printf(%c,G.verticesp-adjvex.data);visitedp-adjvex=1;Q.baseQ.rear=p-adjvex;Q.rear=(Q.rear+1)%MAXQSIZE;p=p-nextarc;算法分析算法分析n n如果使用邻接表表示图，则循环的总时间代如果使用邻接表表示图，则循环的总时间代价为价为 d0+d1+dn-1=O(e)，其中的其中的 di 是顶是顶点点 i 的度。的度。n n如果使用邻接矩阵，则对于每一个被访问过如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的的顶点，循环要检测矩阵中的 n 个元素，总个元素，总的时间代价为的时间代价为O(n2)。最小生成树最小生成树(minimum cost spanning tree)连通网的最小代价生成树连通网的最小代价生成树1.生成树生成树n n假设假设E(G)为连通图为连通图G中所有边的集合，则从图中所有边的集合，则从图中任一顶点出发遍历图时，必将中任一顶点出发遍历图时，必将E(G)分成两分成两个集合个集合T(G)和和B(G)，其中其中T(G)是遍历过程中是遍历过程中历经的边的结合；历经的边的结合；B(G)是剩余的边的集合。是剩余的边的集合。则边集则边集T(G)和图和图G中所有顶点一起构成连通图中所有顶点一起构成连通图G的一棵生成树。的一棵生成树。n n按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生个顶点的连通网络的生成树有成树有 n 个顶点、个顶点、n-1 条边。条边。n n使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深从不同的顶点出发，也可能得到不同的生成树。如深从不同的顶点出发，也可能得到不同的生成树。如深从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树度优先生成树、广度优先生成树度优先生成树、广度优先生成树度优先生成树、广度优先生成树2.2.最小生成树（最小代价生成树）最小生成树（最小代价生成树）最小生成树（最小代价生成树）最小生成树（最小代价生成树）p173p173n n构造准则构造准则构造准则构造准则:uu尽可能用网络中权值最小的边；尽可能用网络中权值最小的边；尽可能用网络中权值最小的边；尽可能用网络中权值最小的边；uu必须使用且仅使用必须使用且仅使用必须使用且仅使用必须使用且仅使用 n n-1 1 条边来联结网络中的条边来联结网络中的条边来联结网络中的条边来联结网络中的 n n 个顶个顶个顶个顶点；点；点；点；uu不能使用产生回路的边。不能使用产生回路的边。不能使用产生回路的边。不能使用产生回路的边。3.3.算法：采用算法：采用算法：采用算法：采用MSTMST性质性质性质性质 p173p173 1)1)普里姆算法普里姆算法普里姆算法普里姆算法 2 2)克鲁斯卡尔算法克鲁斯卡尔算法克鲁斯卡尔算法克鲁斯卡尔算法普里姆普里姆(Prim)算法算法n n普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络 N=V,E 中的某一顶点中的某一顶点 u0 出出发，选择与它关联的具有最小权值的边发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到将其顶点加入到生成树的顶点集合生成树的顶点集合U中。中。以后每一步从以后每一步从一个顶点在一个顶点在U中中，而，而另一个顶另一个顶点不在点不在U中中的各条边中选择的各条边中选择权值最小的边权值最小的边(u,v),把该边加入到生成树的边集把该边加入到生成树的边集TE中，把它的中，把它的顶点加入到顶点加入到集合集合U中。如此重复执行，直到网中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合络中的所有顶点都加入到生成树顶点集合U中中为止。为止。n n采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。普里姆普里姆(Prim)算法算法n n普里姆算法的基本思想：普里姆算法的基本思想：(1)在连通网的顶点集合在连通网的顶点集合V中，任选一个顶点，中，任选一个顶点，构成最小生成树的初始顶点集合构成最小生成树的初始顶点集合U；（2）在在U和和V-U中各选一个顶点，使得该边的中各选一个顶点，使得该边的权值最小，把该边加入到最小生成树的边集权值最小，把该边加入到最小生成树的边集TE中，同时将中，同时将V-U中的该顶点并入到中的该顶点并入到U中；中；（3）反复执行第（）反复执行第（2）步，直至）步，直至V-U=为止。为止。n n采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。n n设置一个辅助数组设置一个辅助数组closedge：uu lowcost域域 存存放放生生成成树树顶顶点点集集合合内内顶顶点点到到生生成树外各顶点成树外各顶点的各边上的当前最小权值；的各边上的当前最小权值；uu adjvex域域 记记录录生生成成树树顶顶点点集集合合外外各各顶顶点点距距离离集合内哪个顶点集合内哪个顶点最近最近(即权值最小即权值最小)。n n设置一个辅助数组设置一个辅助数组closedge：uu lowcost域域：存存放放在在V-U中中各各个个顶顶点点到到集集合合U中的当前最小权值；中的当前最小权值；uu adjvex域：域：记录该边所依附的在记录该边所依附的在U中的顶点中的顶点n n若选择从顶点若选择从顶点0出发，即出发，即u0=0，则辅助数组的则辅助数组的两个域的初始状态为：两个域的初始状态为：n n然后反复做以下工作：然后反复做以下工作：uu 在在 closedge i中选择中选择 adjvex 0 0&lowcost最小最小的边的边 i 用用 k 标记它。则选中的权值最小的边为标记它。则选中的权值最小的边为 (closedgek,G.vexsk)，相应的权值为相应的权值为 closedgek.lowcost。uu 将将 closedgek.adjvex 改为改为 0 0,表示它已加入表示它已加入生成树顶点集合。将边生成树顶点集合。将边(closedgek,G.vexsk)加入生成树的边集合。加入生成树的边集合。uu 取取 lowcosti=min lowcosti,G.arcski，即用即用生成树顶点集合外各顶点生成树顶点集合外各顶点 i 到到刚加入刚加入该集合的新顶点该集合的新顶点 k 的距离的距离 G.arcski 与原来与原来它们到生成树顶点集合中顶点的最短距离它们到生成树顶点集合中顶点的最短距离lowcosti 做比较做比较,取距离近的作为这些集合取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。外顶点到生成树顶点集合内顶点的最短距离。uu 如果如果生成树顶点集合外顶点生成树顶点集合外顶点 i 到到刚加入该集刚加入该集合的新顶点合的新顶点 k 的距离比原来它到生成树顶点的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改集合中顶点的最短距离还要近，则修改adj：adjvex=v。表示生成树外顶点表示生成树外顶点i到生成树内到生成树内顶点顶点k当前距离最近。当前距离最近。利用普里姆算法建立最小生成树利用普里姆算法建立最小生成树typedef int VRType;structVertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;void MiniSpanTree_PRIM(MGraph G,VertexType u)int k,j,i,minCost;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)if(j!=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj;closedgek.lowcost=0;for(i=1;iG.vexnum;+i)k=minimum(closedge);minCost=INFINITY;for(j=0;jG.vexnum;+j)if(closedgej.lowcost minCost&closedgej.lowcost!=0)minCost=closedgej.lowcost;k=j;printf(%c,%c)n,closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for(j=0;jG.vexnum;+j)if(G.arcskjclosedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj;算法分析：算法分析：若连通网络有若连通网络有 n 个顶点个顶点，则该算法的时，则该算法的时间复杂度为间复杂度为 O(n2),它适用于边稠密的网络。它适用于边稠密的网络。克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法n n克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N=V,E,最初先构造一个只有最初先构造一个只有 n 个顶点，没有边的非连个顶点，没有边的非连通图通图 T=V,图中每个顶点自成一个连通图中每个顶点自成一个连通分量。当在分量。当在 E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则若该边的两个顶点落在不同的连通分量上，则将此边加入到将此边加入到 T 中；否则将此边舍去，重新选中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。有顶点在同一个连通分量上为止。应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程活动网络活动网络(Activity Network)n n计划、施工过程、生产流程、程序流程等都是计划、施工过程、生产流程、程序流程等都是“工程工程”。除了很小的工程外，一般都把工程。除了很小的工程外，一般都把工程分为若干个叫做分为若干个叫做“活动活动”的子工程。完成了这的子工程。完成了这些活动，这个工程就可以完成了。些活动，这个工程就可以完成了。n n例如，计算机专业学生的学习就是一个工程，例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要