《C语言第八章1.ppt》由会员分享，可在线阅读，更多相关《C语言第八章1.ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径一、图的基本概念一、图的基本概念图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间的关及顶点间的关系系集合组成的一种数据结构集合组成的一种数据结构：Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象是顶点的有穷是顶点的有穷非空集合；非空集合；E=(x,y)|x,y V 是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)集集合。合。有向图与无向图有向图与无向图 若图若图G G中的每条边都是有方中的每条边都是有方向的，则称向的，则称G G为有向图。有向边也称
2、为弧。为有向图。有向边也称为弧。若图若图G G中的每条边都是没有方向的，则称中的每条边都是没有方向的，则称G G为为无向图。无向图。完全图完全图 对有对有n n个顶点的图，若为无向图且边个顶点的图，若为无向图且边数为数为n(n-1)/2n(n-1)/2，则称其为无向完全图；若为则称其为无向完全图；若为有向图且边数为有向图且边数为n(n-1)n(n-1)，则称其为有向完则称其为有向完全图。全图。邻接顶点邻接顶点 若（若（v vi i,v vj j）是一条无向边，则称是一条无向边，则称顶点顶点v vi i和和v vj j互为邻接点，或称互为邻接点，或称v vi i和和v vj j相邻接，相邻接，并
3、称边（并称边（v vi i,v vj j）关联于顶点关联于顶点v vi i和和v vj j，或称或称（v vi i,v vj j）与顶点与顶点v vi i和和v vj j相关联。相关联。n n顶点的度顶点的度顶点的度顶点的度 一个顶点一个顶点一个顶点一个顶点v v的度是与它相关联的边的条的度是与它相关联的边的条的度是与它相关联的边的条的度是与它相关联的边的条数。数。数。数。记作记作记作记作TD(TD(v v)。顶点顶点顶点顶点 v v 的入度的入度的入度的入度 是以是以是以是以 v v 为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数,记作记作记作记作 ID(I
4、D(v v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度是以是以是以是以 v v 为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数,记作记作记作记作 OD(OD(v v)。n n子图子图子图子图 设有两个图设有两个图设有两个图设有两个图 GG(V V,E E)和和和和 GG(V V,E E)。若若若若 V V V V 且且且且 E E E E,则称则称则称则称 图图图图GG是是是是 图图图图GG的子图的子图的子图的子图。路径路径路径路径 在图在图 G G(V V,E E)中中,若存在一个顶点序列若存在一个顶点序列 v vp p1 1,v vp p2 2,
5、v vpmpm，使得使得(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)均属于均属于E E，则称顶点则称顶点v vi i到到v vj j存在一存在一 条路径。若一条路径上除了条路径。若一条路径上除了v vi i 和和v vj j 可以相同外，可以相同外，其余顶点均不相同，则称此路径为一条简单路径其余顶点均不相同，则称此路径为一条简单路径 。起点和终点相同的路径称为简单回路或简单环。起点和终点相同的路径称为简单回路或简单环。图的连通图的连通 在无向图在无向图G G中，若两个顶点中，若两个顶点v vi i和和v vj j之间有之
6、间有 路径存在，则称路径存在，则称v vi i 和和v vj j 是连通的。若是连通的。若G G中任意两中任意两 个顶点都是连通的，则称个顶点都是连通的，则称G G为连通图为连通图。非连通图的非连通图的极大连通子图叫做连通分量。极大连通子图叫做连通分量。n n强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量在有向图中在有向图中,若对于每一若对于每一对顶点对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是强连通图。非强连通图的极大强连通则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。子图叫做强连通分量
7、。权权权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权。这种称之为权。这种带权图叫做网络带权图叫做网络。12356874ABDCE1079667123151660304535804075 生成树生成树一个连通图的生成树是它的极小一个连通图的生成树是它的极小连通子图，在连通子图，在n个顶点的情形下，有个顶点的情形下，有n-1条条边。边。n n不予讨论的图不予讨论的图 包含顶点到其自身的边；包含顶点到其自身的边；一条边在图中重复出现一条边在图中重复出现 二、图的存储结构二、图的存储结构n n在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个在图
8、的邻接矩阵表示中，有一个记录各个顶点信记录各个顶点信记录各个顶点信记录各个顶点信息息息息的的的的顶点表顶点表顶点表顶点表，还有一个，还有一个，还有一个，还有一个表示各个顶点之间关系表示各个顶点之间关系表示各个顶点之间关系表示各个顶点之间关系的的的的邻接矩阵邻接矩阵邻接矩阵邻接矩阵。n n设图设图设图设图 A=(A=(V V,E E)是一个有是一个有是一个有是一个有 n n 个顶点的图，则图的邻个顶点的图，则图的邻个顶点的图，则图的邻个顶点的图，则图的邻接矩阵是一个二维数组接矩阵是一个二维数组接矩阵是一个二维数组接矩阵是一个二维数组 A A.Edge.Edge n n n n，定义：定义：定义：
9、定义：n n无向图的邻接矩阵是对称的，有向图的邻接矩阵无向图的邻接矩阵是对称的，有向图的邻接矩阵无向图的邻接矩阵是对称的，有向图的邻接矩阵无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。可能是不对称的。可能是不对称的。可能是不对称的。邻接矩阵邻接矩阵(AdjacencyMatrix)在有向图中在有向图中在有向图中在有向图中,统计第统计第统计第统计第 i i 行行行行11的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点 i i 的出度，的出度，的出度，的出度，统计第统计第统计第统计第 j j 列列列列11的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点 j j 的入度。
10、的入度。的入度。的入度。在无向图中在无向图中在无向图中在无向图中,统计第统计第统计第统计第 i i 行行行行(列列列列)1)1的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点i i 的度。的度。的度。的度。网络的邻接矩阵网络的邻接矩阵邻接矩阵表示法中图的描述邻接矩阵表示法中图的描述#definen6/*图的顶点数图的顶点数*/#definee8/*图的边数图的边数*/typedefcharvextype;/*顶点的数据类型顶点的数据类型*/typedeffloatadjtype;/*权值类型权值类型*/typedefstructvextypevexsn;adjtypearcsnn;gr
11、aph;21435BADCE215346203050407080邻接矩阵表示法中无向网络的建立算法邻接矩阵表示法中无向网络的建立算法CREATEGRAPH(graph*ga)inti,j,k;floatw;for(i=0;ivexsigetchar();/*读入顶点信息，建立顶点表读入顶点信息，建立顶点表*/for(i=0;in;i+)for(j=0;jarcsij0;/*邻接矩阵初始化邻接矩阵初始化*/for(k=0;karcsijw;ga-arcsjiw;邻接表邻接表(AdjacencyList)无向图的邻接表无向图的邻接表 把同一个顶点发出的边链接在同一个边链表中，把同一个顶点发出的边链
12、接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点结点中保存有与该边相关联的另一顶点的顶点下标下标dest 和指向同一链表中下一个边结点的指和指向同一链表中下一个边结点的指针针link。有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表在有向图的邻接表中，第在有向图的邻接表中，第i个边链表链接的边个边链表链接的边都是都是顶点顶点i发出的边发出的边。也叫做。也叫做出边表出边表。在有向图的逆邻接表中，第在有向图的逆邻接表中，第i个边链表链接的个边链表链接的边都是边都是进入顶点进入顶点i的边的边。也叫做。也叫做入
13、边表入边表。带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值cost。顶点顶点i 的边链表的表头指针的边链表的表头指针adj 在顶点表的下标在顶点表的下标为为i 的顶点记录中，该记录还保存了该顶点的的顶点记录中，该记录还保存了该顶点的其它信息。其它信息。在邻接表的边链表中，在邻接表的边链表中，各个边结点的链入顺序各个边结点的链入顺序任意，视边结点输入次序而定。任意，视边结点输入次序而定。设图中有设图中有n 个顶点，个顶点，e 条边，则条边，则用邻接表表示用邻接表表示无向图时无向图时，需要，需要n 个顶点结点，个顶点结点，2e 个边结点；个边结点；用用邻接表表示有向图时邻接表表示
14、有向图时，若不考虑逆邻接表，若不考虑逆邻接表，只需只需n 个顶点结点，个顶点结点，e 个边结点。个边结点。邻接表的形式说明和建立算法邻接表的形式说明和建立算法typedefstructnode/*边表结点定义边表结点定义*/intadjvex;structnode*next;edgenode;typedefstruct/*顶点表结点定义顶点表结点定义*/vextypevertex;edgenode*link;vexnode;vexnodegan;CREATADJLIST(vexnodega)inti,j,k;edgenode*s;for(i=0;in;i+)/*读入顶点信息并初始化读入顶点信息
15、并初始化*/gai.vertexgetchar();gai.linkNULL;for(k=0;kadjvexj;s-nextgai.linkgai.links;smalloc(sizeof(edgenode);s-adjvexi;s-nextgaj.link;gai.links;网络网络(带权图带权图)的邻接表的邻接表三、图的遍历性三、图的遍历性从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个
16、顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历图的遍历图的遍历(GraphTraversal)GraphTraversal)。图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶
17、点。回到了曾经访问过的顶点。回到了曾经访问过的顶点。回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问为了避免重复访问，可设置一个标志顶点是否被访问为了避免重复访问，可设置一个标志顶点是否被访问为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组过的辅助数组过的辅助数组过的辅助数组 visitedvisited，它的初始状态为它的初始状态为它的初始状态为它的初始状态为0 0，在图的，在图的，在图的，在图的遍历过程中，一旦某一个顶点遍历过程中，一旦某一个顶点遍历过程中，一旦某一个顶点遍历过程中，一旦某一个顶点 i i 被访问，就立即让被访问，就立即让被访问，就立即让被访
18、问，就立即让 visitedvisited i i 为为为为1 1，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。深度优先搜索深度优先搜索DFS(DepthFirstSearch)深度优先搜索的示例深度优先搜索的示例 DFS DFS 在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点 v v 后，由后，由后，由后，由 v v 出发，出发，出发，出发，访问它的任一邻接顶点访问它的任一邻接顶点访问它的任一邻接顶点访问它的任一邻接顶点 w w1 1；再从再从再从再从 w w11出发，访问与出发，访问与出发，访问与出发，访问与 w
19、w1 1邻接但还没有访问过的顶点邻接但还没有访问过的顶点邻接但还没有访问过的顶点邻接但还没有访问过的顶点 w w2 2；然后再从然后再从然后再从然后再从 w w22出出出出发，进行类似的访问，发，进行类似的访问，发，进行类似的访问，发，进行类似的访问，如此进行下去，直至到达如此进行下去，直至到达如此进行下去，直至到达如此进行下去，直至到达所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点 u u 为止。接着，为止。接着，为止。接着，为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看
20、是否还退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回
21、一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。深度优先搜索算法深度优先搜索算法intvisitedn;graphg;DFS(inti)/*图用邻接矩阵表示图用邻接矩阵表示*/intj;printf(“node:%cn”,g.vexsi);visitedi=TRUE;for(j=0;jadjvex)DFSL(p-adjvex);p=p-next;例子例子遍历结果：遍历结果：A A、C C、B B、D D算法分析算法分析图中有图中有n 个顶点，个顶点，e
22、条边。条边。如果用邻接表表示图，沿如果用邻接表表示图，沿 Firstout link 链可链可以找到某个顶点以找到某个顶点v 的所有邻接顶点的所有邻接顶点w。由于总由于总共有共有2e 个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问而且对所有顶点递归访问1次，所以遍历图的次，所以遍历图的时间复杂性为时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为所有的边，所需时间为O(n)，则遍历图中所有则遍历图中所有的顶点所需的时间为的顶点所需的时间为O(n2)。广度优先搜索广度优先搜索BF
23、S(BreadthFirstSearch)广度优先搜索的示例广度优先搜索的示例 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点v 之后，之后，由由v 出发，依次访问出发，依次访问v 的各个未曾被访问过的的各个未曾被访问过的邻接顶点邻接顶点w1,w2,wt，然后再顺序访问然后再顺序访问w1,w2,wt 的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，有还未被访问过的邻接顶点，如此做下去，如此做下去，直
24、到图中所有顶点都被访问到为止。直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程，每向前广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。便于向下一层访问。与深度优先搜索过程一样，为
25、避免重复访问，与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组需要一个辅助数组visited，给被访问过的顶给被访问过的顶点加标记。点加标记。广度优先搜索算法广度优先搜索算法BSF(intk)/*图用邻接矩阵表示图用邻接矩阵表示*/inti,j;SETNULL(Q);printf(“%cn”,g.vexsk);visitedk=TRUE;ENQUEUE(Q,K);while(!EMPTY(Q)i=DEQUEUE(Q);for(j=0;jadjvex)printf(“%cn”,g1p-adjvex.vertex);visitedp-adjvex=TRUE;ENQUEUE(Q,p-adjv
26、ex);p=p-next;例子例子遍历结果：遍历结果：A A、B B、C C、D D算法分析算法分析如果使用邻接表表示图，则循环的总时间代如果使用邻接表表示图，则循环的总时间代价为价为d0+d1+dn-1=O(e)，其中的其中的di 是顶是顶点点i 的度。的度。如果使用邻接矩阵，则对于每一个被访问过如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的的顶点，循环要检测矩阵中的n 个元素，总个元素，总的时间代价为的时间代价为O(n2)。连通分量连通分量(Connectedcomponent)当无向图为非连通图时，从图中某一顶点出发，当无向图为非连通图时，从图中某一顶点出发，利用深度优
27、先搜索算法或广度优先搜索算法不利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图点所在的最大连通子图(连通分量连通分量)的所有顶点。的所有顶点。若从无向图的每一个连通分量中的一个顶点出若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。发进行遍历，可求得无向图的所有连通分量。在算法中，需要对图的每一个顶点进行检测：在算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点得的连
28、通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。出发遍历图，可求得图的另一个连通分量。对于非连通的无向图，所有连通分量的生成树对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。组成了非连通图的生成森林。非连通图的遍历非连通图的遍历 非连通图的遍历必须多次调用深度优先搜索或非连通图的遍历必须多次调用深度优先搜索或广度优先搜索算法，以广度优先搜索算法，以DFSDFS为例：为例：TRAVER()/*遍历用邻接矩阵表示的非连通图遍历用邻接矩阵表示的非连通图*/inti;for(i=0;in;i+)visitedi=FALSE;/*标志数组初始化标志数组初始化*/
29、for(i=0;in;i+)if(!visitedi)DFS(i);/*从顶点出发遍历一个连从顶点出发遍历一个连通分量通分量*/printf(“compendn”);四、最小生成树四、最小生成树(minimumcostspanningtree)连通图连通图G G的一个子图如果是一棵包含的一个子图如果是一棵包含G G的所的所有顶点的树，则该子图称为有顶点的树，则该子图称为G G的的生成树生成树。生成树是连通图的极小连通子图。所谓生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变出现一个回路；若去掉一
30、条边，将会使之变成非连通图。成非连通图。生成树各边的权值总和称为生成树的权。生成树各边的权值总和称为生成树的权。权最小的生成树称为权最小的生成树称为最小生成树最小生成树用不同的遍历图的方法，可以得到不同的生用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。成树。按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的个顶点的连通网络的生成树有生成树有n 个顶点、个顶点、n-1条边。条边。构造最小生成树的准则：必须只使用该网络构造最小生成树的准则：必须只使用该网络中的边来构造最小生成树；必须使用且仅使用中的边来构造最
31、小生成树；必须使用且仅使用n-1条边来联结网络中的条边来联结网络中的n 个顶点；不能使用产生个顶点；不能使用产生回路的边。回路的边。最小生成树的重要性质：最小生成树的重要性质：设设 G=G=（V V，E E）是一个连通网络，是一个连通网络，U U 是是顶点集顶点集 V V 的的一个真子集。若（一个真子集。若（u u，v v）是是 G G 中所有的一个顶点在中所有的一个顶点在 U U，另一个顶点不在另一个顶点不在 U U 的边中，具有最小权值的一条边，则一定存的边中，具有最小权值的一条边，则一定存在在 G G 的一棵最小生成树包括此边。的一棵最小生成树包括此边。uvUVU证明（反证法）：证明（反
32、证法）：假设假设 G G 中任何一棵最小生成树中都不包含中任何一棵最小生成树中都不包含(u u，v)v)。设设T T是一棵最小生成树但不包含是一棵最小生成树但不包含(u u，v)v)。由于由于T T是最小生成树，所以是最小生成树，所以 T T 是连通的，因是连通的，因此有一条从此有一条从u u到到v v的路径，且该路径上必有一条的路径，且该路径上必有一条连接两个顶点集连接两个顶点集 U U、V V 的边的边(u u，v v)，其中其中u uUU，v vV-UV-U。当把边当把边(u u，v)v)加入到加入到 T T 中后，得到中后，得到一个含有边一个含有边(u u，v)v)的回路。删除边的回路
33、。删除边(u u，v v)，上上述回路即被消除。由此得到另一棵生成树述回路即被消除。由此得到另一棵生成树 T T，T T 和和 T T 的区别仅在于用边的区别仅在于用边(u u，v)v)代替了代替了(u u，v v)。由于由于(u u，v)v)的权的权=(=(u u，v v)的全权，所以，的全权，所以，T T的权的权=T T的权，与假设矛盾。的权，与假设矛盾。uvUVUuv普里姆普里姆(Prim)算法算法普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络N=V,E中的某一顶点中的某一顶点u0出出发，选择与它关联的具有最小权值的边发，选择与它关联的具有最小权值的边(u0,v)，将其
34、顶点加入到将其顶点加入到生成树的顶点集合生成树的顶点集合U中。以后每中。以后每一步从一步从一个顶点在一个顶点在U中中，而，而另一个顶点不在另一个顶点不在U中中的各条边中选择的各条边中选择权值最小的边权值最小的边(u,v),把它的顶点把它的顶点加入到加入到集合集合U中。如此继续下去，直到网络中的中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合所有顶点都加入到生成树顶点集合U中为止。中为止。用普里姆算法构造最小生成树的过程用普里姆算法构造最小生成树的过程123465565173254612346551324普里姆算法构造的基本思想普里姆算法构造的基本思想为直观解释方便，设想在构造过程中
35、，为直观解释方便，设想在构造过程中，T T的的顶点集顶点集U U和边集均被涂成红色，和边集均被涂成红色，U U之外的顶点涂之外的顶点涂成蓝色，连接红点和蓝点的边被涂成紫色。因成蓝色，连接红点和蓝点的边被涂成紫色。因此，最短紫边就是连接此，最短紫边就是连接U U和和V-UV-U的最短边。的最短边。设当前生成的设当前生成的T T有有k k个顶点，则当前紫边数目个顶点，则当前紫边数目是是k(n-k)k(n-k)，紫边集过大。为了构造一个较小的紫边集过大。为了构造一个较小的侯选紫边集，可以这样处理：对每一个蓝点，侯选紫边集，可以这样处理：对每一个蓝点，从该蓝点到红点的紫边中，必有一条是最短的从该蓝点到
36、红点的紫边中，必有一条是最短的，我们只要将所有，我们只要将所有n-kn-k个蓝点所关联的最短紫边个蓝点所关联的最短紫边作为侯选集，就必定能保证所有紫边中最短的作为侯选集，就必定能保证所有紫边中最短的紫边属于该侯选集。紫边属于该侯选集。侯选集的调整方法：侯选集的调整方法：当最短紫边当最短紫边(u,v)u,v)被涂成红色被加入被涂成红色被加入T T中中后，后，v v由由蓝点变为红点，对每一个剩余的蓝蓝点变为红点，对每一个剩余的蓝点点j j，边边(v,j)v,j)就由非就由非紫边变成了紫边，这就紫边变成了紫边，这就使得我们必须对侯选集做如下调整：若侯选使得我们必须对侯选集做如下调整：若侯选集中蓝点集
37、中蓝点j j所关联的原最短紫边长度大于新所关联的原最短紫边长度大于新紫边紫边(v,j)v,j)的长度，则以的长度，则以(v,j)v,j)作为作为j j所所关联关联的新的最短紫边来代替的新的最短紫边来代替j j的原的原最短紫边，否最短紫边，否则则j j的原最短紫边不变。的原最短紫边不变。Prim Prim 算法的结构如下：算法的结构如下：(1)置置T为任意一个顶点，置初始侯选紫边集；为任意一个顶点，置初始侯选紫边集；(2)while(T中顶点数目中顶点数目n)(3)从侯选紫边集中选取最短紫边从侯选紫边集中选取最短紫边(u,v);(4)将将(u,v)及及蓝点蓝点v涂成红色，扩充到涂成红色，扩充到T
38、中；中；(5)调整侯选紫边集；调整侯选紫边集；(6)PRIM算法算法typedefstructintfromvex,endvex;floatlength;edge;floatdistnn;edgeTn-1;PRIM()intj,k,m,v,min,max=10000;floatd;edgee;for(j=1;jn;j+)Tj-1.fromvex=1;Tj-1.endvex=j+1;Tj-1.length=dist0j;for(k=0;kn-1;k+)min=max;for(j=k;jn-1;j+)if(Tj.lengthmin)min=Tj.length;m=j;e=Tm;Tm=Tk;Tk=e
39、;v=Tk.endvex;for(j=k+1;jn-1;j+)d=distv-1Tj.endvex-1;if(dTj.length)Tj.length=d;Tj.fromvex=v;算法分析算法分析 上述算法的初始化时间是上述算法的初始化时间是O(1)O(1)，k k循环循环中有两个循环语句，其时间大致为：中有两个循环语句，其时间大致为：令令O(1)O(1)为某一为某一正常数正常数C C，展开上述求和展开上述求和公式可知其数量级仍是公式可知其数量级仍是 n n 的平方。所以，的平方。所以，整个算法的时间复杂性是整个算法的时间复杂性是O(nO(n2 2)克鲁斯卡尔克鲁斯卡尔(Kruskal)算法
40、算法克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有n 个顶点的连通网络个顶点的连通网络N=V,E,最初先构造一个只有最初先构造一个只有n 个顶点，没有边的非连通个顶点，没有边的非连通图图T=V,图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。当在当在E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的若该边的两个顶点落在不同的连通分量上，则将此边加入两个顶点落在不同的连通分量上，则将此边加入到到T 中；否则将此边舍去，重新选择一条权值最中；否则将此边舍去，重新选择一条权值最小的边。小的边。如此重复下去，直到所有顶点在同一个连通如此重复下去，直到所有顶点在同一个连通分量上为止。分量上为止。用克鲁斯卡尔算法构造最小生成树的过程用克鲁斯卡尔算法构造最小生成树的过程123465565173254612346551324克鲁斯卡尔算法的基本思想克鲁斯卡尔算法的基本思想T=(V,)；While(T中所含边数中所含边数n-1)从从E中选取当前最短边中选取当前最短边(u,v);从从E中删除边中删除边(u,v);if(u,v)并入并入T之后不产生回路之后不产生回路)将边将边(u,v)并入并入T中；中；