第十二章 图优秀PPT.ppt

第十二章第十二章 图图第一页，本课件共有77页12.2 2006图n n 图的一些专有名词图的一些专有名词n n 图数据结构表示法图数据结构表示法n n 图的遍历图的遍历n n 最小生成树最小生成树n n 拓扑排序拓扑排序n n 关键路径法关键路径法第二页，本课件共有77页12.3 2006图结构示意图n n 图结构示意图图结构示意图图图12-3 12-3 图结构示意图图结构示意图 第三页，本课件共有77页12.4 2006图的一些专有名词（1）n n 顶点顶点顶点顶点（vertexvertex）：-图图12-312-3中的圆圈称为顶点。中的圆圈称为顶点。n n 边（边（边（边（edge edge）：）：）：）：-每个顶点之间的连线称为边。每个顶点之间的连线称为边。n n 无向图（无向图（无向图（无向图（undirected graph undirected graph）：）：）：）：-在边上没有箭头的图称为无向图，如图在边上没有箭头的图称为无向图，如图12-312-3中中GIGI和和G2G2为无向为无向 图。图。n n 有向图（有向图（有向图（有向图（directed graph directed graph directed graph directed graph）：）：）：）：-在边上有箭头的图称为有向图，如图在边上有箭头的图称为有向图，如图12-312-3中中G3G3为有向图。为有向图。n n 图（图（图（图（graph graph graph graph）：）：）：）：-图是由所有顶点和所有边组合而成的，以图是由所有顶点和所有边组合而成的，以G=(V,E)G=(V,E)表示。表示。第四页，本课件共有77页12.5 2006图的一些专有名词（2）n n 多重图（多重图（多重图（多重图（mutigraph mutigraph mutigraph mutigraph）：）：）：）：-假如两个顶点有多条相同的边，则称之为多重图，而不是假如两个顶点有多条相同的边，则称之为多重图，而不是 图形。图形。n n 完全图（完全图（完全图（完全图（complete graph complete graph complete graph complete graph）：）：）：）：-在在n n个顶点的无向图中，假如有个顶点的无向图中，假如有n(n-1)/2n(n-1)/2个边，则这样的个边，则这样的 图称为完全图。图称为完全图。n n 邻接（邻接（邻接（邻接（adjacent adjacent adjacent adjacent）：）：）：）：-在图的某一边在图的某一边(V V1 1,V,V2 2)中，称顶点中，称顶点V V1 1与顶点与顶点V V2 2是邻接的，但是邻接的，但 在有向图中称在有向图中称 为为V V1 1是邻接到是邻接到V V2 2或或V V2 2邻接自邻接自V V1 1。第五页，本课件共有77页12.6 2006图的一些专有名词（3）n n 依附（依附（依附（依附（incidentincidentincidentincident）：）：）：）：-在图在图12-312-3中，顶点中，顶点V V1 1和顶点和顶点V V2 2是邻接的，而边是邻接的，而边(V V1 1,V,V2 2)依附依附 在顶点在顶点V V1 1与与V V2 2顶点上。可以发现在顶点上。可以发现在G3G3中依附在顶点中依附在顶点V V2 2的的 边有边有、及及。n n 子图（子图（子图（子图（subgraphsubgraphsubgraphsubgraph）：）：）：）：-假使假使V(GV(G)V(G)V(G)及及E(GE(G)E(G)E(G)，则称则称G G 是是G G的子图。的子图。n n 路径（路径（路径（路径（pathpathpathpath）：）：）：）：-在图在图G G中，从顶中，从顶V Vp p到顶点到顶点V Vq q的路径是指一系列的顶点的路径是指一系列的顶点V Vp p、V Vi1i1、V Vi2i2、V Vinin、V Vq q，其中其中(V Vp p,V,Vi1i1)、(V(Vi1i1,V,Vi2i2)、(V(Vinin,V,Vq q)是是 E(G)E(G)上的边。上的边。第六页，本课件共有77页12.7 2006图的一些专有名词（4）n n 长度（长度（长度（长度（lengthlengthlengthlength）：）：）：）：-一条路径上的长度是指该路径上所有边的数目。一条路径上的长度是指该路径上所有边的数目。n n 简单路径（简单路径（简单路径（简单路径（simple pathsimple pathsimple pathsimple path）：）：）：）：-除头尾顶点之外，其余顶点都在不相同的路径上。如图除头尾顶点之外，其余顶点都在不相同的路径上。如图12-312-3 中，中，G1G1的两条路径的两条路径1 1、2 2、4 4、3 3和和1 1、2 2、4 4、2 2，其长度都为，其长度都为3 3，但前者是简单路径，而后者不是简单路径。但前者是简单路径，而后者不是简单路径。n n 回路或环（回路或环（回路或环（回路或环（cyclecyclecyclecycle）：）：）：）：-指第一个顶点和最后一个顶点相同的简单路径。指第一个顶点和最后一个顶点相同的简单路径。n n 连通（连通（连通（连通（connectedconnectedconnectedconnected）：）：）：）：-在一个图在一个图G G中，如果有一条路径从中，如果有一条路径从V V1 1到到V V2 2，那么就说那么就说V V1 1与与V V2 2是是 连通的。连通的。第七页，本课件共有77页12.8 2006图的一些专有名词（5）n n 连通分量（连通分量（连通分量（连通分量（connected componentconnected componentconnected componentconnected component）：）：）：）：-或称分量（或称分量（componentcomponent）是指该图中最大的连通子图是指该图中最大的连通子图 （maximal connected subgraphmaximal connected subgraph）。）。n n 强连通（强连通（强连通（强连通（strongly connectedstrongly connectedstrongly connectedstrongly connected）：）：）：）：-在一个有向图中如果在一个有向图中如果V(G)V(G)中的每一对不同顶点中的每一对不同顶点V Vi i、V Vj j各有一条各有一条 从从V Vi i到到V Vj j及从及从V Vj j到到V Vi i的有向路径，则称此有向图是强连通的。的有向路径，则称此有向图是强连通的。n n 强连通分量（强连通分量（强连通分量（强连通分量（strongly connected componentstrongly connected componentstrongly connected componentstrongly connected component）：）：）：）：-是指一个强连通最大子图。是指一个强连通最大子图。第八页，本课件共有77页12.9 2006图的一些专有名词（6）n n 度（度（度（度（degreedegreedegreedegree）：）：）：）：-依附在顶点的边数。若为有向图，则其度为入度与出度之和。依附在顶点的边数。若为有向图，则其度为入度与出度之和。n n 入度（入度（入度（入度（in-degreein-degreein-degreein-degree）：）：）：）：-顶点顶点V V的入度是指以的入度是指以V V为终点（即箭头指向为终点（即箭头指向V V）的边数。的边数。n n 出度（出度（出度（出度（out-degreeout-degreeout-degreeout-degree）：）：）：）：-顶点顶点V V的出度是以的出度是以V V为起点的边数。为起点的边数。第九页，本课件共有77页12.10 2006图数据结构表示法 n n 图的数据结构表示法常用的有下列两种：图的数据结构表示法常用的有下列两种：（1 1 1 1）邻接矩阵（）邻接矩阵（）邻接矩阵（）邻接矩阵（adjacency matrixadjacency matrixadjacency matrixadjacency matrix）：邻接矩阵是将图中的邻接矩阵是将图中的n n个顶点（个顶点（verticesvertices）以一个以一个nnnn的二的二 维矩阵来表示，其中每一元素维矩阵来表示，其中每一元素V Vijij若为若为1 1，表示图中，表示图中V Vi i与与V Vj j有有 一条边为一条边为(V Vi i,V,Vj j)，假如是有向图，表示有一条边为假如是有向图，表示有一条边为 。V Vijij=0=0表示顶点表示顶点I I与顶点与顶点j j没有边存在。没有边存在。（2 2 2 2）邻接表（）邻接表（）邻接表（）邻接表（adjacency listadjacency listadjacency listadjacency list）：）：）：）：邻接表是将图中的每个顶点都形成表头，而在每个表头的节邻接表是将图中的每个顶点都形成表头，而在每个表头的节 点表示它们之间有边存在。点表示它们之间有边存在。第十页，本课件共有77页12.11 2006邻接矩阵 n n 邻接矩阵是对称性的，而且对角线都为零，所以图中邻接矩阵是对称性的，而且对角线都为零，所以图中 只需要储存上三角形或下三角形即可，所需储存空间只需要储存上三角形或下三角形即可，所需储存空间 为为n(n-1)/2n(n-1)/2。n n 邻接矩阵表示法邻接矩阵表示法：图图G5G5示意图示意图 G5G5的邻接矩阵表示法的邻接矩阵表示法 第十一页，本课件共有77页12.12 2006图中顶点度的计算n n假假如如要要求求图图中中某某一一顶顶点点邻邻接接边边的的数数目目（即即度度），只只要要计计算邻接矩阵中某一列所有算邻接矩阵中某一列所有1 1之和或某一行所有之和或某一行所有1 1之和。之和。n n在在有有向向图图的的邻邻接接矩矩阵阵中中，列列的的和和表表示示顶顶点点的的出出度度，行行的的和和表表示顶点的入度。示顶点的入度。无向图节点度的计算方法无向图节点度的计算方法 有向图节点度的计算方法有向图节点度的计算方法 第十二页，本课件共有77页12.13 2006邻接表（1）n n邻接表的表示法：邻接表的表示法：顶点顶点1 1顶点顶点2 2顶点顶点3 3顶点顶点4 4顶点顶点5 5顶点顶点6 6顶点顶点7 7顶点顶点8 8图图G5G5示意图示意图 G5G5的邻接表表示法的邻接表表示法 第十三页，本课件共有77页12.14 2006邻接表（2）n n从从邻邻接接表表中中知知某某一一顶顶点点的的度度，由由此此顶顶点点表表头头后后有有n n个个节节点点便便可可计计算算出来。出来。n n在有向图中，每个表头后面的节点数表示此顶点的出度数目。在有向图中，每个表头后面的节点数表示此顶点的出度数目。n n在在有有向向图图中中若若要要求求入入度度的的数数目目，则则必必须须把把邻邻接接矩矩阵阵变变成成相相反反的的邻邻接接表表。步步骤骤如下：如下：-先把邻接矩阵变为转置矩阵（先把邻接矩阵变为转置矩阵（transpose matrixtranspose matrix），如图所示。），如图所示。-再把转置矩阵变为邻接表，如图所示。再把转置矩阵变为邻接表，如图所示。顶点顶点1 1顶点顶点2 2顶点顶点3 3G3G3的邻接矩阵的转置矩阵的邻接矩阵的转置矩阵 G3G3的邻接矩阵的转置矩阵对应的邻接矩阵的转置矩阵对应的邻接表的邻接表 第十四页，本课件共有77页12.15 2006图的遍历n n图的遍历是从图的某一顶点开始，访问图的其他顶点。图的遍历是从图的某一顶点开始，访问图的其他顶点。n n图的遍历只用在：图的遍历只用在：（1 1）判断此图是不是连通；）判断此图是不是连通；（2 2）找出此图的连通分量；）找出此图的连通分量；（3 3）画出此图的最小生成树（）画出此图的最小生成树（spanning treespanning tree）。）。n n图的遍历有两种方法：图的遍历有两种方法：深度优先搜索和广度优先搜索。深度优先搜索和广度优先搜索。第十五页，本课件共有77页12.16 2006深度优先搜索n n深度优先搜索（深度优先搜索（depth first searchdepth first search）-深度优先搜索是以堆栈（深度优先搜索是以堆栈（stackstack）方式来操作的。）方式来操作的。n n图的深度优先搜索的过程是：图的深度优先搜索的过程是：（1 1）先访问起始点）先访问起始点V V；（2 2）然后选择与）然后选择与V V邻接而未被访问的顶点邻接而未被访问的顶点W W，以，以W W为起始点做深度优为起始点做深度优 先搜索；先搜索；（3 3）假使某一顶点其邻接的顶点都被访问过时，就退回到最近曾）假使某一顶点其邻接的顶点都被访问过时，就退回到最近曾 访问的顶点，如果其尚有未被访问过的邻接顶点，继续做深访问的顶点，如果其尚有未被访问过的邻接顶点，继续做深 度优先搜索；度优先搜索；（4 4）假若从任何已访问过的顶点，都无法再找到未被访问过的邻）假若从任何已访问过的顶点，都无法再找到未被访问过的邻 接顶点时，此时搜索结束。接顶点时，此时搜索结束。第十六页，本课件共有77页12.17 2006深度优先搜索操作步骤n n比如有一个图比如有一个图A A如图如图12-2212-22所示。所示。图图12-22 12-22 图图A A示意图示意图 第十七页，本课件共有77页12.18 2006深度优先搜索操作步骤（续1）（1 1）先输出）先输出V V1 1（V V1 1为起点）。为起点）。（2 2）将）将V V1 1的邻接顶点的邻接顶点V V2 2及及V V3 3放入堆栈中，如图放入堆栈中，如图12-2312-23所示。所示。（3 3）弹出堆栈的第一个顶点）弹出堆栈的第一个顶点V V2 2，然后将，然后将V V2 2的邻接顶点的邻接顶点V V1 1、V V4 4及及V V5 5推入到堆栈，如图推入到堆栈，如图12-2412-24所示。所示。图图12-23 12-23 执执行行完完第第（2 2）的的堆堆栈栈状态图状态图 图图12-24 12-24 执执行行完完第第（3 3）后后的的堆堆栈状态图栈状态图 第十八页，本课件共有77页12.19 2006深度优先搜索操作步骤（续2）（4 4）弹出）弹出V V1 1，由于，由于V V1 1己被输出，故再弹出己被输出，故再弹出V V4 4，将，将V V4 4的邻接的邻接 顶点顶点V V2 2及及V V8 8放入堆栈，如图放入堆栈，如图12-2512-25所示。所示。（5 5）弹出）弹出V V2 2，由于，由于V V2 2已被输出过，故再弹出已被输出过，故再弹出V V8 8，再将，再将V V8 8的的 邻接顶点邻接顶点V V4 4、V V5 5及及V V1010放入堆栈，如图放入堆栈，如图12-2612-26所示。所示。（6 6）弹出）弹出V V4 4，由于已输出过，故弹出，由于已输出过，故弹出V V5 5，然后将，然后将V V5 5的邻接的邻接 顶点顶点V V2 2及及V V8 8放入堆栈，如图放入堆栈，如图12-2712-27所示。所示。（7 7）弹出）弹出V V2 2及及V V8 8，由于这两个顶点已被输出过，故弹出，由于这两个顶点已被输出过，故弹出V V1010，再将，再将V V1010的邻接点的邻接点V V8 8及及V V9 9放入堆栈，如图放入堆栈，如图12-12-2828所示。所示。第十九页，本课件共有77页12.20 2006深度优先搜索操作步骤（续3）图图12-25 12-25 执行完执行完第（第（4 4）后的堆）后的堆栈状态图栈状态图 图图12-26 12-26 执行完执行完第（第（5 5）后的）后的堆栈状态图堆栈状态图 图图12-27 12-27 执行执行完第（完第（6 6）后的）后的堆栈状态图堆栈状态图 图图12-28 12-28 执行完执行完第（第（7 7）后的）后的堆栈状态图堆栈状态图 第二十页，本课件共有77页12.21 2006深度优先搜索操作步骤（续4）n n（8 8）弹出）弹出V V8 8，此顶点已被输出故弹出此顶点已被输出故弹出V V9 9，将将V V9 9的邻的邻 接顶点接顶点V V6 6、V V7 7及及V V1010放入堆栈，如图放入堆栈，如图12-2912-29所示。所示。n n（9 9）弹出）弹出V V6 6，再将再将V V6 6的邻接顶点的邻接顶点V V3 3及及V V9 9放入堆栈，放入堆栈，如图如图12-3012-30所示。所示。图图12-29 12-29 执行完执行完第（第（8 8）后的堆栈状态图）后的堆栈状态图 图图12-30 12-30 执执行行完完第第（9 9）后后的的堆栈状态图堆栈状态图 第二十一页，本课件共有77页12.22 2006深度优先搜索操作步骤（续5）（1010）弹出）弹出V V3 3，将将V V1 1与与V V7 7放入堆栈，如图放入堆栈，如图12-3112-31所示。所示。（1111）弹出）弹出V V1 1，此顶点已输出故弹出此顶点已输出故弹出V V7 7，再将再将V V3 3及及V V9 9放入放入 堆栈，如图堆栈，如图12-3212-32所示。所示。图图12-31 12-31 执执行行完完第第（1010）后后的的堆栈状态图堆栈状态图 图图12-32 12-32 执执行行完完第第（1111）后后的的堆栈状态图堆栈状态图 第二十二页，本课件共有77页12.23 2006深度优先搜索操作步骤（续6）（1212）最后弹出）最后弹出V V3 3、V V9 9、V V9 9、V V7 7、v v1010、V V5 5、V V3 3，由于这些由于这些 顶点都已输出过，此时堆栈是空的，表示搜索已顶点都已输出过，此时堆栈是空的，表示搜索已 结束。结束。从从上上述述的的搜搜索索步步骤骤可可知知其其顺顺序序为为：V V1 1、V V2 2、V V4 4、V V8 8、V V5 5、V V1010、V V9 9、V V6 6、V V3 3、V V7 7。读者需注意的是此顺序并不惟一，读者需注意的是此顺序并不惟一，而是根据顶点放入堆栈的顺序而定。而是根据顶点放入堆栈的顺序而定。第二十三页，本课件共有77页12.24 2006广度优先搜索n n广广度度优优先先搜搜索索（breadth breadth first first searchsearch）和和深深度度优优先先搜搜索不同的是：索不同的是：-广度优先搜索先访问完所有的邻接顶点，再去找寻下一层的广度优先搜索先访问完所有的邻接顶点，再去找寻下一层的 其他顶点。其他顶点。-深度优先搜索以堆栈来操作，而广度优先搜索则以队列来操深度优先搜索以堆栈来操作，而广度优先搜索则以队列来操 作。作。n n任选一顶点任选一顶点V Vi i为初始点，广度优先搜索基本思想是为初始点，广度优先搜索基本思想是:-首先访问出发点首先访问出发点V Vi i -接着依次访问接着依次访问V Vi i的所有邻接点的所有邻接点 W W1 1，W W2 2，.，W Wt t -然后再依次访问与然后再依次访问与W W1 1，W W2 2，.，W Wt t邻接的所有未被访问过的邻接的所有未被访问过的 顶点顶点 -依次类推，直到图中所有和初始出发点依次类推，直到图中所有和初始出发点V Vi i有路径相通的顶点有路径相通的顶点 都已访问到为止都已访问到为止第二十四页，本课件共有77页12.25 2006程序实例图的遍历/*file name:dfs.c*/*file name:dfs.c*/*/*图的遍历图的遍历:邻接表与深度优先搜索法邻接表与深度优先搜索法(DFS)*/(DFS)*/#include#include#include#include#include#include#define MAX_V 100 /*#define MAX_V 100 /*最大节点数最大节点数*/#define TRUE 1#define TRUE 1#define FALSE 0#define FALSE 0 第二十五页，本课件共有77页12.26 2006程序实例图的遍历（续1）/*/*定义数据结构定义数据结构*/typedef struct node_tag typedef struct node_tag int vertex;int vertex;struct node_tag*link;struct node_tag*link;Node;Node;Node*adjlistMAX_V+1;/*Node*adjlistMAX_V+1;/*宣告邻接表宣告邻接表*/int visitedMAX_V+1;/*int visitedMAX_V+1;/*记录顶点是否已访问过记录顶点是否已访问过*/int total_vertex;int total_vertex;第二十六页，本课件共有77页12.27 2006程序实例图的遍历（续2）void build_adjlist();void build_adjlist();void show_adjlist();void show_adjlist();void dfs(int);void dfs(int);Node*searchlast(Node*);Node*searchlast(Node*);void main()void main()build_adjlist();/*build_adjlist();/*以邻接表表示图形以邻接表表示图形*/show_adjlist();/*show_adjlist();/*显示表的数据显示表的数据*/puts(n-Depth Fisrt Search-);puts(n-Depth Fisrt Search-);dfs(1);/*dfs(1);/*图的深度优先搜索，以顶点图的深度优先搜索，以顶点1 1为起始顶点为起始顶点*/第二十七页，本课件共有77页12.28 2006程序实例图的遍历（续3）void build_adjlist()void build_adjlist()FILE*fptr;FILE*fptr;Node*node,*lastnode;Node*node,*lastnode;int vi,vj,weight;int vi,vj,weight;fptr=fopen(dfs.dat,r);fptr=fopen(dfs.dat,r);if(fptr=NULL)if(fptr=NULL)perror(dfs.dat);perror(dfs.dat);exit(0);exit(0);第二十八页，本课件共有77页12.29 2006程序实例图的遍历（续4）/*/*读取节点总数读取节点总数*/fscanf(fptr,%d,&total_vertex);fscanf(fptr,%d,&total_vertex);for(vi=1;vi=total_vertex;vi+)for(vi=1;vi vertex=vi;adjlistvi-vertex=vi;adjlistvi-link=NULL;adjlistvi-link=NULL;第二十九页，本课件共有77页12.30 2006程序实例图的遍历（续5）/*/*读取节点数据读取节点数据*/for(vi=1;vi=total_vertex;vi+)for(vi=1;vi=total_vertex;vi+)for(vj=1;vj=total_vertex;vj+)for(vj=1;vj vertex=vj;node-vertex=vj;node-link=NULL;node-link=NULL;第三十页，本课件共有77页12.31 2006程序实例图的遍历（续6）lastnode=searchlast(adjlistvi);lastnode=searchlast(adjlistvi);lastnode-link=node;lastnode-link=node;fclose(fptr);fclose(fptr);/*/*显示各邻接表的数据显示各邻接表的数据*/void show_adjlist()void show_adjlist()int index;int index;Node*ptr;Node*ptr;第三十一页，本课件共有77页12.32 2006程序实例图的遍历（续7）puts(Head adjacency nodes);puts(Head adjacency nodes);puts(-);puts(-);for(index=1;index=total_vertex;index+)for(index=1;index vertex);printf(V%-2d,adjlistindex-vertex);ptr=adjlistindex-link;ptr=adjlistindex-link;while(ptr!=NULL)while(ptr!=NULL)printf(-V%d,ptr-vertex);printf(-V%d,ptr-vertex);ptr=ptr-link;ptr=ptr-link;printf(n);printf(n);第三十二页，本课件共有77页12.33 2006程序实例图的遍历（续8）/*/*图的深度优先搜索图的深度优先搜索*/void dfs(int v)void dfs(int v)Node*ptr;Node*ptr;int w;int w;printf(V%d,adjlistv-vertex);printf(V%d,adjlistv-vertex);visitedv=TRUE;/*visitedv=TRUE;/*设定设定v v顶点为已访问过顶点为已访问过*/ptr=adjlistv-link;ptr=adjlistv-link;/*/*访问相邻顶点访问相邻顶点*/第三十三页，本课件共有77页12.34 2006程序实例图的遍历（续9）do do /*/*若顶点尚未访问，则以此顶点为新起始点继续若顶点尚未访问，则以此顶点为新起始点继续 做深度优先搜索遍历，否则找与其相邻的顶点，做深度优先搜索遍历，否则找与其相邻的顶点，直到所有相连接的节点都已访问直到所有相连接的节点都已访问 */w=ptr-vertex;w=ptr-vertex;if(!visitedw)if(!visitedw)dfs(w);dfs(w);else else ptr=ptr-link;ptr=ptr-link;while(ptr!=NULL);while(ptr!=NULL);第三十四页，本课件共有77页12.35 2006程序实例图的遍历（续10）/*/*搜索表最后节点函数搜索表最后节点函数*/Node*searchlast(Node*linklist)Node*searchlast(Node*linklist)Node*ptr;Node*ptr;ptr=linklist;ptr=linklist;while(ptr-link!=NULL)ptr=ptr-link;while(ptr-link!=NULL)ptr=ptr-link;return ptr;return ptr;第三十五页，本课件共有77页12.36 2006程序实例图的遍历（续11）输出的结果输出的结果head adjacency nodeshead adjacency nodes-V1-V2-V3V1-V2-V3V2-V1-V4-V5V2-V1-V4-V5V3-V1-V6-V7V3-V1-V6-V7V4-V2-V8V4-V2-V8V5-V2-V8V5-V2-V8V6-V3-V9V6-V3-V9V7-V3-V9V7-V3-V9V8-V4-V5-V10V8-V4-V5-V10V9-V6-V7-V10V9-V6-V7-V10V10-V8-V9V10-V8-V9-Depth First Search-Depth First Search-V1 V2 V4 V8 V5 V10 V9 V6 V3 v7V1 V2 V4 V8 V5 V10 V9 V6 V3 v7第三十六页，本课件共有77页12.37 2006最小生成树n n最小生成树是以最少的边数来连接图中所有的顶点。最小生成树是以最少的边数来连接图中所有的顶点。n n用图的遍历可以画出图的最小生成树：用图的遍历可以画出图的最小生成树：-使用深度优先搜索的遍历方式，则称为深度优先搜索最小生使用深度优先搜索的遍历方式，则称为深度优先搜索最小生 成树。成树。-使用广度优先搜索的遍历方式，则称为广度优先搜索最小生使用广度优先搜索的遍历方式，则称为广度优先搜索最小生 成树。成树。n n若若G=(V,G=(V,E)E)是是一一个个图图，而而S S=(V,(V,T)T)是是G G的的最最小小生生成成树树。其其中中T T是是遍遍历历时时所所访访问问过过的的边边，而而以以K K表表示示遍遍历历后后所所未未被被访访问问的的边边。此此时时最最小小生生成成树具有下列几点特性：树具有下列几点特性：-E=T+K-E=T+K -V -V中的任何两个顶点中的任何两个顶点V V1 1及及V V2 2在在S S中有惟一的边。中有惟一的边。-插入插入K K中任何一个边于中任何一个边于S S中，会形成回路。中，会形成回路。第三十七页，本课件共有77页12.38 2006最小生成树n n若若图图中中每每一一个个边边加加上上一一些些数数值值，此此数数值值称称为为权权（weightweight），而称此图为，而称此图为权图（权图（weight graphweight graph）。n n假假设设此此权权是是代代价价（costcost）或或距距离离（distancedistance），则则称称此此图为图为网（网（networknetwork）。n n假假如如在在网网中中有有一一个个最最小小生生成成树树具具有有最最小小代代价价，则则求求最最小小代代价价最小生成树有两种方法：最小生成树有两种方法：（1 1）普里姆算（）普里姆算（PrimPrim s algorithms algorithm），），（2 2）克鲁斯卡尔算法（）克鲁斯卡尔算法（KruskalKruskal s algorithms algorithm）。）。第三十八页，本课件共有77页12.39 2006普里姆算法和克鲁斯卡尔算法 n n普里姆算法（普里姆算法（普里姆算法（普里姆算法（Prims algorithmPrims algorithmPrims algorithmPrims algorithm）-有一个网有一个网G=(V,E)G=(V,E)，其中，其中V=1,2,3,V=1,2,3,n,n 起初设定起初设定U1U1，U U 及及V V是两个顶点的集合，然后从是两个顶点的集合，然后从V-UV-U集合中找一个顶点集合中找一个顶点x x，能，能 与与U U集合中的某顶点形成最小的边，把这一个顶点集合中的某顶点形成最小的边，把这一个顶点x x插入插入U U集集 合，继续此步骤，直到合，继续此步骤，直到U U集合等于集合等于V V集合为止。集合为止。n n克鲁斯卡尔算法（克鲁斯卡尔算法（克鲁斯卡尔算法（克鲁斯卡尔算法（Kruskals algorithmKruskals algorithmKruskals algorithmKruskals algorithm）-有一个网有一个网G=(V,E)G=(V,E)，V=P1,2,3,V=P1,2,3,n,n，E E中每一边都有一个中每一边都有一个 代价，代价，T=(v,)T=(v,)表示开始时表示开始时T T没有边。首先从没有边。首先从E E中找具有最小代中找具有最小代 价的边；若此边插入价的边；若此边插入T T中不形成回路，则将此边从中不形成回路，则将此边从E E删除并插删除并插 入入T T中，直到中，直到T T中含有中含有n-1n-1个边为止。个边为止。第三十九页，本课件共有77页12.40 2006两种算法的等价性n 不论由普里姆算法或克鲁斯卡尔算法来求最小代价最 小生成树，所得到的图是一样的。第四十页，本课件共有77页12.41 2006求最小生成树程序实例/*file name:kruskal.c*/*使用 kruskals 算法求最小生成树*/#include#include#include#define MAX_V 100 /*最大节点数*/#define TRUE 1#define FALSE 0 typedef struct 第四十一页，本课件共有77页12.42 2006求最小生成树程序实例（续1）int vertex1;int vertex2;int weight;int edge_deleted;Edge;typedef struct int vertexMAX_V;int edges;Graph;第四十二页，本课件共有77页12.43 2006求最小生成树程序实例（续2）Edge EMAX_V;Graph T;int total_vertex;int total_edge;int adjmatrixMAX_VMAX_V;/*store matrix weight*/void kruskal();void addEdge(Edge);void build_adjmatrix();Edge mincostEdge();int cyclicT(Edge e);void showEdge();第四十三页，本课件共有77页12.44 2006求最小生成树程序实例（续3）void main()Edge e;int i,j,weight;build_adjmatrix();for(i=1;i=total_vertex;i+)for(j=i+1;j=total_vertex;j+)weight=adjmatrixij;if(weight!=0)第四十四页，本课件共有77页12.45 2006求最小生成树程序实例（续4）e.vertex1=i;e.vertex2=j;e.weight=weight;e.edge_deleted=FALSE;addEdge(e);showEdge();/*init T*/for(i=1;i=total_vertex;i+)第四十五页，本课件共有77页12.46 2006求最小生成树程序实例（续5）T.vertexi=0;T.edges=0;puts(nMinimum cost spanning tree using Kruskal);puts(-);kruskal();void build_adjmatrix()第四十六页，本课件共有77页12.47 2006求最小生成树程序实例（续6）FILE*fptr;int vi,vj;fptr=fopen(kruskal.dat,r);if(fptr=NULL)perror(kruskal.dat);exit(0);/*读取节点总数*/fscanf(fptr,%d,&total_vertex);第四十七页，本课件共有77页12.48 2006求最小生成树程序实例（续7）for(vi=1;vi=total_vertex;vi+)for(vj=1;vj=total_vertex;vj+)fscanf(fptr,%d,&adjmatrixvivj);fclose(fptr);void addEdge(Edge e)E+total_edge=e;第四十八页，本课件共有77页12.49 2006求最小生成树程序实例（续8）void showEdge()int i=1;printf(total vertex=%d ,total_vertex);printf(total_ed