图算法1(最小生成树)

1、图算法图算法 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集 R构成构成的数据结构。的数据结构。 Graph = (V , R )其中，VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧，并称 w 为弧头弧头，v为弧尾弧尾。 图的结构定义图的结构定义: 由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图有向图。 AB E C D例如例如: :G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 若VR 必有VR, 则称 (v,w) 为顶点v 和顶点 w 之间存在一条边边。 B CA D F E由顶点集和边集构成的图称作

2、无向图无向图。例如: G2=(V2,VR2)假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作完全图完全图； 含有 e=n(n-1) 条弧的有向图称作 有向完全图有向完全图； 若边或弧的个数 enlogn，则称作稀疏图稀疏图，否则称作稠密图稠密图。 假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点邻接点，ACDFE例如例如: :TD(B) = 3TD(A) = 2 边(v,w) 和顶点v 和w 相关联关联。 和顶点v 关联的边的数目边的数目定义为边的度度。B顶点的出度出度: : 以顶点v为弧尾的弧的数目；ABECF对有向图来说对有向图来说，顶点

3、的入度入度: : 以顶点v为弧头的弧的数目。顶点的度度( (TD)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1TD(B) = 3 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林生成森林。BACDFE1. 设有设有6个结点的无向图，该图至少应有个结点的无向图，该图至少应有_条边才能确保是一个连通图。条边才能确保是一个连通图。2. 在一个无向图中，所有顶点度数之和等于在一个无向图中

4、，所有顶点度数之和等于图的边数的图的边数的_倍。倍。3. 具有具有N个顶点的有向图最多有个顶点的有向图最多有_条边。条边。练 习ABCDEFAij=0 (i,j)VR1 (i,j)VR一、一、图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为A B C D E F010010100011000101001001110000011100有向图的邻接矩阵有向图的邻接矩阵为非对称矩阵为非对称矩阵ABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0typedef struct ArcCell / 弧的定义弧的定义 VRType a

5、dj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； /对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct / 图的定义图的定义 VertexType / 顶点信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph;0 A 1 41 B 0 4 52 C 3 5

6、3 D 2 54 E 0 15 F 1 2 3BACDFE二、图的邻接表二、图的邻接表 存储表示存储表示有向图的邻接表有向图的邻接表1 4230 120 1 2 3 4 A B C D EABECD可见，在有向图的邻接表中不易找到指向该顶点的弧。typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构typedef struct VNode Ver

7、texType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc顶点的结点结构顶点的结点结构三、有向图的十字链表存储表示三、有向图的十字链表存储表示 弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧尾有相同弧尾的结点指向下一个有相同弧头有相同弧头的结点四、无向图的邻接多重表存储表示结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作遍历遍历插入和删除弧插入和删除弧

8、基本操作基本操作图的遍历图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索Vw1SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V ：for (W1、W2、W3 ) 若该邻接点Wi未被访问， 则从它出发进行深度优先搜索遍历。w2w3w2 (连通网的连通网的)最小生成树最小生成树MST (minimum spanning tree) 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在

9、最节省经费的前如何在最节省经费的前提下建立提下建立这个通讯网通讯网？问题：问题： 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法） 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加在添加的顶点的顶点 w 和已经在生成树上的顶点和已经在生成树上的顶点v 之间之间必定存在一条边，并且该边的权值在所有必定存在一条边，并且该边的权值在所有连通顶点连通顶点 v 和和 w 之间的边中取值最

10、小之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。普里姆算法的基本思想普里姆算法的基本思想:abcdegf例如例如: :195141827168213ae12dcbgf7148531621所得生成树权值和= 14+8+3+5+16+21 = 67 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通在所有连通U中顶点和中顶点和V-U中中顶点的边中选取权值最小的边顶点的边中选取权值最小的边。 一般情况下所添加的顶点应满足下列条件:Prim 算法过程算法过程bchifaedg4884

11idcbhgfe12全部节点都被覆盖，算法结束abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 5具体做法具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。考虑问题的出发点考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：abcdegf195141827168213ae12d

12、cbgf7148531621例如例如: :7121819Kruskal 算法过程算法过程bchifaedg488414791067211aidcbhgfe12构成环路构成环路构成环路全部节点都被覆盖，算法结束普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法贪心准则贪心准则 Prim算法算法l加入后仍形成树，且耗费最小加入后仍形成树，且耗费最小l始终保持树的结构始终保持树的结构Kruskal算法是森林算法是森林nKruskal算法算法每个步骤选择一条边加入生成树每个步骤选择一条边加入生

13、成树不会产生不会产生环路环路，且耗费最小，且耗费最小下面看一个例子： Agri-Net Description Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course. Farmer John ordered a high speed connection for his farm and is going to sh

14、are his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms. Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all t

15、ogether. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm. The distance between any two farms will not exceed 100,000. Input The input includes several cases. For each case, the first line contains the number of farms, N (3 = N = 100). The fol

16、lowing lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0,

17、 since the distance from farm i to itself is not interesting for this problem.Output For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms. Sample Input4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 Sample Output28 这个题目，实际上是

18、给了N个顶点，每两个顶点间的距离已经给出，让你求一条最小权值的路径，该路径使得所有的farms能够相互到达。这是典型的最小生成树。分析2431421816179代码：(朴素prim）#includeint main() int i,j,k,n,a101101; while(scanf(%d,&n)!=EOF) for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&aij); int flag101=0,sum=0; /flagi用来标记节点i是否被覆盖 flag1=1; /选取第一个点 for(k=1;kn;k+) /循环n-1次 int min=-1,min_i

19、; for(i=1;i=n;i+) /选取下一个最小权值的节点 if(flagi=0&(min=-1|a1imin) min=a1i; min_i=i; flagmin_i=1; /覆盖节点 for(i=1;iamin_ii) a1i=amin_ii; sum+=a1min_i; /加上权值 printf(%dn,sum); return 0;Kruskal算法的实现并查集还有其他优化策略，比如路径压缩，这里不再论述。对于kruskal算法，在判断加入的边(u,v)是否构成回路时，只需判断Find(u)与Find(v)是否相等即可。若相等，则构成回路，否则不构成回路。例子的kruskal程序如

20、下：#include #include #include using namespace std;#define N 10000struct Edge int u,v,w;class UFset private: bool *root; int *parent; int n;public: UFset(int n) int i; this-n=n; root=new booln; parent=new intn; for(i=0;in;i+) parenti=1; rooti=true; UFset() delete parent; delete root; int Find(int e) /

21、 Return root of tree containing e. / Compact path from e to root. int i=e; / Find root while(!rooti) i=parenti; / compact int j=e;/ start at e while(j!=i)/ j is not root int pj=parentj; parentj=i;/ move j to level 2 j=pj;/ j moves to old parent return i; Kruskal算法的实现 bool Union(int x,int y) / Combin

22、e trees with roots px and py. int px=Find(x); int py=Find(y); if(px=py) return false; if(parentpxparentpy) / px becomes subtree of py parentpy+=parentpx; rootpx=false; parentpx=py; else / py becomes subtree of px parentpx+=parentpy; rootpy=false; parentpy=px; return true; ;class graph public: int n,

23、m; Edge edgeN; void kruskal();bool cmp(const Edge &e1,const Edge &e2) return e1.we2.w;void graph:kruskal() sort(edge,edge+m,cmp); UFset ufset(n); int min=0,k=0; for(int i=0;im;i+) if(ufset.Union(edgei.u,edgei.v) min+=edgei.w; +k; if(k=n-1) break; printf(%dn,min);Kruskal算法的实现graph g;int main() int i,

24、j,w; while(scanf(%d,&g.n)!=EOF) int k=0; for(i=0;ig.n;i+) for(j=0;jg.n;j+) scanf(%d,&w); if(ij) g.edgek.u=i; g.edgek.v=j; g.edgek.w=w; k+; g.m=k; g.kruskal(); return 0;练习： 1751 Highways HighwaysDescriptionThe island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has a very poor system

25、 of public highways. The Flatopian government is aware of this problem and has already constructed a number of highways connecting some of the most important towns. However, there are still some towns that you cant reach via a highway. It is necessary to build more highways so that it will be possib

26、le to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N and town i has a position given by the Cartesian coordinates (xi, yi). Each highway connects exaclty two towns. All highways (both the original ones and the ones that are to be built) f

27、ollow straight lines, and thus their length is equal to Cartesian distance between towns. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government w

28、ants to minimize the cost of building new highways. However, they want to guarantee that every town is highway-reachable from every other town. Since Flatopia is so flat, the cost of a highway is always proportional to its length. Thus, the least expensive highway system will be the one that minimiz

29、es the total highways length. Sample Input91 50 0 3 24 55 10 45 21 25 331 39 71 2 Sample Output1 63 74 95 78 3 8642-2-4-6-10-5510代码：#include#include#include using namespace std;int a760760,b760,f760,x760,y760,pre760; /prei用于记录与第i 个点相连的点,输出时是2到N；int len(int x1,int y1,int x2,int y2) return (x1-x2)*(x1

30、-x2)+(y1-y2)*(y1-y2); /刚才开始这里开方，丢精度，影响计算结果，干脆不开方，结果对sum不要求!int main() int i,t,j,k,ival,num1,num2,num, MIN ; scanf(%d,&ival); for(i=1;i=ival;+i) scanf(%d%d,&xi,&yi); for(i=1;i=ival;+i) for(j=1;j=ival;+j) aij=len(xi,yi,xj,yj); scanf(%d,&num); for(i=1;i=num;+i) scanf(%d%d,&num1,&num2); anum1num2=anum2n

31、um1=0; for(i=1;i=ival;+i) fi=0; bi=ai1; prei=1; /将各个点都与1相连 f1=1; for(t=1;tival;+t) MIN=2147483640 ; for(i=2;ibi) MIN=bi; k=i; fk=1; for(i=2;iaik&!fi) bi=aik; prei=k; /找到与t相连的点，如果没有进行到这一步，则说明t与1相连是最短的 for(i=2;i=ival;i+) if(apreii!=0) printf(%d %dn,prei,i); return 0; 1639 Picnic Planning DescriptionTh

32、e Contortion Brothers are a famous set of circus clowns, known worldwide for their incredible ability to cram an unlimited number of themselves into even the smallest vehicle. During the off-season, the brothers like to get together for an Annual Contortionists Meeting at a local park. However, the brothers are not only tight with regard to cramped quarters, but with money as well, so they try to find the way to get everyone to the party which minimizes the number of miles put on eve