2023年8月1日发(作者：)

一、树及生成树的基本概念树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述：(1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。例如：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。若用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。任意两个城市之间均可以通话，这个图必须是连通图，且这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是一个不含圈的连通图，代表了一个电话线网。生成树（支撑树）定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。定理：一个图G有生成树的条件是G是连通图。证明:必要性显然；充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子图GK，且不含圈，从而GK是一个生成树。寻找连通图生成树的方法：破圈法：从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个生成树。取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3）中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7，这样，剩下的图不含圈，于是得到一个支撑树，如图所示。避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。二、最小生成树概念：设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v,w]。所有生成树G’上各边权的总和最小的生成树称为G的最小生成树。应用：如在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v，w]表示建立城市v、w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络最经济的方案。性质：设G=(V,E)是连通带权图，U是V的真子集。若(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权c[u，v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质也称为MST性质。算法：经典方法有两种：kruskal、prim算法（贪心思想）：一次生成一条最短边。【Prim算法】：算法思想：任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。按结点来贪，因此适用于稠密图的处理.算法内容：①设置顶点集合V和边集E，它们的初始状态为空集。②任意选取一个顶点A加入V中。③重复以下过程直到V中已经包含原图的所有节点：1、选一条权值最小的边(u,v)，并使其满足u,v两节点只有一个在点集V中。2、将两个节点中不在V的那个点加入集合V中，并将边(u,v)加入边集E中。④所得的子图G’=(V,E)即为所求的最小生成树。关键：找出当前最优得一条边,穷举每一条不在集合E中的边，找出符合条件且最优的边。时间复杂度：O（V*E），即顶点数乘以边数。代码：varn,i,j,k,min,sum:longint;a:array[1..1000,1..1000]oflongint;b,d:array[1..1000]oflongint;procedureprim;beginsum:=0;fori:=1tondod[i]:=a[1,i];forj:=2tondobeginmin:=maxlongint;fori:=1tondoif(d[i]0)thenbeginmin:=d[i];k:=i;end;sum:=sum+d[k];d[k]:=0;fori:=1tondoif(a[k,i]k)thend[i]:=a[k,i];end;end;beginreadln(n);fori:=1tondoforj:=1tondobeginread(a[i,j]);if(i<>j)and(a[i,j]=0)thena[i,j]:=maxlongint;end;//初始化prim;writeln(sum);算法：初始状态A包含任意一个顶点r，从r开始，每次都向A中添加一条连接树A和G=（V,A）中某个孤立顶点的轻边，直至生成树A包含了图中所有的顶点。有效实现该算法的关键是设法较容易地选择一条轻边。我们可以借助最小优先级队列。图中的顶点可以分为两类，一类是在A中的，已经纳入最小生成树了，另一种是不在A中的，记为B，对于这些顶点，我们需要保存它们与A中的某个顶点相连的边中的最小权值。最小优先级队列保存的就是B（尚未纳入最小生成树）中的顶点以及它们与A中某个顶点相连的边中的最小权值。每次队首出队，设新加入A的顶点为V，那么我们要修改V的邻接点中尚未在A中（在最小优先级队列）的且与A中顶点相连的边的最小权值（比较拗口）。Prim+heapy优化：*优化：在选择权值最小的可行边时可以使用堆。(nlogn)堆优化的Prim算法适用于稀疏图，而不优化的Prim算法适用于稠密图。代码：varn,i,j,k,sum:longint;a:array[0..1000,0..1000]oflongint;b,d,heap,pos:array[0..10000]oflongint;procedureswap(vari,j:longint);{交换整数i和j}//省略procedureheapify(p:longint);{向下调整堆的过程}varbest:longint;beginbest:=p;//下面两个if是分别判断根和左、右孩子最短距离的大小if(p*2<=j-1)and(key[heap[p*2]]pthen//若根有所变动，即跟比左右孩子都大（最短距离）beginswap(pos[heap[p]],pos[heap[best]]);//互换节点heap[p]、heap[best]在堆的位置swap(heap[p],heap[best]);//互换堆中元素p、bestheapify(best);//继续调整互换后的元素bestend;end;proceduremodify(id,new_d:longint);{判断new_d与d[id]大小，并修改key[id]大小}varp:longint;beginif(new_d1)and(key[heap[p]]j)and(a[i,j]=0)thena[i,j]:=maxlongint;end;//初始化fori:=1tondobeginheap[i]:=i;pos[i]:=i;d[i]:=maxlongint;end;prim;writeln(sum);end.【Kruskal算法】算法内容：初始时把每个顶点看作一个集合①将所有边以长度为关键词从小到大排序。②将每个顶点都加入一个集合中，即N个顶点共N个集合。③设置边集E，初始状态为空。④从小到大访问每条边，若边连接的两个顶点属于不同集合，则合并两个顶点所在的集合，并将该边加入到边集E中。⑤所得的子图TG=(V,E)即为所求的最小生成树，其中顶点集V就是原图的所有顶点。**关键：集合的合并。我们可以采用路径压缩的算法，用树结构作为集合的结构，对于每个点只记录它的父亲，集合的代表元素即为树的根。在判断两个节点是否属于同一集合时，递归查找节点所在树的根，同时压缩路径。合并集合只需将集合B的根的父亲记为集合A的根即可。时间复杂度：O（eloge）varx,j,tot,i,n:longint;l,a,b:array[1..10000]oflongint;f:array[1..100]oflongint;procedureqs(low,high:longint);//以每条边的长度排序；functionfind(x:longint):longint;//找集合的根结点、vartmp:longint;beginiff[x]=xthenexit(x)elseexit(find(f[x]));end;procedureunion(u,v:longint);//合并子集varfu,fv:longint;beginfu:=find(u);fv:=find(v);f[fv]:=fu;end;procedurekruskal;varcnt,i,ans:longint;beginfori:=1tondof[i]:=i;//初始子集，都是自己；cnt:=0;ans:=0;fori:=1tototdoif(find(a)<>find(b))then//判断是否属于同一子集beginunion(a,b);inc(ans);inc(cnt);ifcnt=n-1thenbreak;//n个结点，连接n-1条边end;writeln(ans);end;begintot:=0;readln(n);fori:=1tondoforj:=1tondobeginread(x);if(i<>j)thenbegininc(tot);a[tot]:=i;b[tot]:=j;l[tot]:=x;end;end;qsort(1,tot);kruskal;在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。+Heap在任何时候都有令人满意的的时间复杂度，但是代价是空间消耗极大。【以及代码很复杂>_<】3.时间复杂度并不能反映出一个算法的实际优劣。竞赛题大多数是稀疏图，所以尽可能地使用Prim+Heap，在稀疏图中这是无敌的。如果一定要在朴素Prim和Kruskal里选一个的话那就用Kruskal吧。当然Prim的代码比较简单，对付水题用Prim也无所谓，只要不是极稀疏图两者相差不大习题：1、最优布线问题（wire）[问题描述]学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，使任意两台计算机都连通（不管是直接的或间接的）。[输入格式]输入文件，第一行为整数n（2<=n<=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。[输出格式]输出文件，一个整数，表示最小的连接费用。[样例输入]3012101210[样例输出]2（注：表示连接1和2，2和3，费用为2）[问题分析]这道题是典型的求最小生成树的题目，可以运用上文所讲的两种算法进行处理。2、【最小生成树算法实例】现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？【输入】第一行两个数v(v<=200),e，分别代表城市数和边数，以下e行，每行为两个顶点和它们之间的边权w(w<1000)。【输出】v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。【输入样例】645633【输出样例】1215183、例题农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。输入格式InputFormat(1)采用邻接矩阵存储第一行为农场的个数，N（3<=N<=100）。接下去为一个N*N的矩阵,表示每个农场之间的距离。(农场之间的距离小于999，0路线表示无法直接到达)。(2)图采用边目录方式存储。第一行N为农场的个数,M为农场与农场之间共有M条可以搭设光纤路线。接下去的M行为中每行有3个数A，B，C。分别表示农场A到农场B的距离为B。输出格式OutputFormat输出连接所有农场并所用光纤最短的方案。样例输入SampleInput(1)采用邻接矩阵存储。(2)采用边目录方式存储。667样例输出SampleOutput

2023年8月1日发(作者：)

一、树及生成树的基本概念树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述：(1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。例如：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。若用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。任意两个城市之间均可以通话，这个图必须是连通图，且这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是一个不含圈的连通图，代表了一个电话线网。生成树（支撑树）定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。定理：一个图G有生成树的条件是G是连通图。证明:必要性显然；充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子图GK，且不含圈，从而GK是一个生成树。寻找连通图生成树的方法：破圈法：从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个生成树。取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3）中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7，这样，剩下的图不含圈，于是得到一个支撑树，如图所示。避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。二、最小生成树概念：设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v,w]。所有生成树G’上各边权的总和最小的生成树称为G的最小生成树。应用：如在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v，w]表示建立城市v、w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络最经济的方案。性质：设G=(V,E)是连通带权图，U是V的真子集。若(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权c[u，v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质也称为MST性质。算法：经典方法有两种：kruskal、prim算法（贪心思想）：一次生成一条最短边。【Prim算法】：算法思想：任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。按结点来贪，因此适用于稠密图的处理.算法内容：①设置顶点集合V和边集E，它们的初始状态为空集。②任意选取一个顶点A加入V中。③重复以下过程直到V中已经包含原图的所有节点：1、选一条权值最小的边(u,v)，并使其满足u,v两节点只有一个在点集V中。2、将两个节点中不在V的那个点加入集合V中，并将边(u,v)加入边集E中。④所得的子图G’=(V,E)即为所求的最小生成树。关键：找出当前最优得一条边,穷举每一条不在集合E中的边，找出符合条件且最优的边。时间复杂度：O（V*E），即顶点数乘以边数。代码：varn,i,j,k,min,sum:longint;a:array[1..1000,1..1000]oflongint;b,d:array[1..1000]oflongint;procedureprim;beginsum:=0;fori:=1tondod[i]:=a[1,i];forj:=2tondobeginmin:=maxlongint;fori:=1tondoif(d[i]0)thenbeginmin:=d[i];k:=i;end;sum:=sum+d[k];d[k]:=0;fori:=1tondoif(a[k,i]k)thend[i]:=a[k,i];end;end;beginreadln(n);fori:=1tondoforj:=1tondobeginread(a[i,j]);if(i<>j)and(a[i,j]=0)thena[i,j]:=maxlongint;end;//初始化prim;writeln(sum);算法：初始状态A包含任意一个顶点r，从r开始，每次都向A中添加一条连接树A和G=（V,A）中某个孤立顶点的轻边，直至生成树A包含了图中所有的顶点。有效实现该算法的关键是设法较容易地选择一条轻边。我们可以借助最小优先级队列。图中的顶点可以分为两类，一类是在A中的，已经纳入最小生成树了，另一种是不在A中的，记为B，对于这些顶点，我们需要保存它们与A中的某个顶点相连的边中的最小权值。最小优先级队列保存的就是B（尚未纳入最小生成树）中的顶点以及它们与A中某个顶点相连的边中的最小权值。每次队首出队，设新加入A的顶点为V，那么我们要修改V的邻接点中尚未在A中（在最小优先级队列）的且与A中顶点相连的边的最小权值（比较拗口）。Prim+heapy优化：*优化：在选择权值最小的可行边时可以使用堆。(nlogn)堆优化的Prim算法适用于稀疏图，而不优化的Prim算法适用于稠密图。代码：varn,i,j,k,sum:longint;a:array[0..1000,0..1000]oflongint;b,d,heap,pos:array[0..10000]oflongint;procedureswap(vari,j:longint);{交换整数i和j}//省略procedureheapify(p:longint);{向下调整堆的过程}varbest:longint;beginbest:=p;//下面两个if是分别判断根和左、右孩子最短距离的大小if(p*2<=j-1)and(key[heap[p*2]]pthen//若根有所变动，即跟比左右孩子都大（最短距离）beginswap(pos[heap[p]],pos[heap[best]]);//互换节点heap[p]、heap[best]在堆的位置swap(heap[p],heap[best]);//互换堆中元素p、bestheapify(best);//继续调整互换后的元素bestend;end;proceduremodify(id,new_d:longint);{判断new_d与d[id]大小，并修改key[id]大小}varp:longint;beginif(new_d1)and(key[heap[p]]j)and(a[i,j]=0)thena[i,j]:=maxlongint;end;//初始化fori:=1tondobeginheap[i]:=i;pos[i]:=i;d[i]:=maxlongint;end;prim;writeln(sum);end.【Kruskal算法】算法内容：初始时把每个顶点看作一个集合①将所有边以长度为关键词从小到大排序。②将每个顶点都加入一个集合中，即N个顶点共N个集合。③设置边集E，初始状态为空。④从小到大访问每条边，若边连接的两个顶点属于不同集合，则合并两个顶点所在的集合，并将该边加入到边集E中。⑤所得的子图TG=(V,E)即为所求的最小生成树，其中顶点集V就是原图的所有顶点。**关键：集合的合并。我们可以采用路径压缩的算法，用树结构作为集合的结构，对于每个点只记录它的父亲，集合的代表元素即为树的根。在判断两个节点是否属于同一集合时，递归查找节点所在树的根，同时压缩路径。合并集合只需将集合B的根的父亲记为集合A的根即可。时间复杂度：O（eloge）varx,j,tot,i,n:longint;l,a,b:array[1..10000]oflongint;f:array[1..100]oflongint;procedureqs(low,high:longint);//以每条边的长度排序；functionfind(x:longint):longint;//找集合的根结点、vartmp:longint;beginiff[x]=xthenexit(x)elseexit(find(f[x]));end;procedureunion(u,v:longint);//合并子集varfu,fv:longint;beginfu:=find(u);fv:=find(v);f[fv]:=fu;end;procedurekruskal;varcnt,i,ans:longint;beginfori:=1tondof[i]:=i;//初始子集，都是自己；cnt:=0;ans:=0;fori:=1tototdoif(find(a)<>find(b))then//判断是否属于同一子集beginunion(a,b);inc(ans);inc(cnt);ifcnt=n-1thenbreak;//n个结点，连接n-1条边end;writeln(ans);end;begintot:=0;readln(n);fori:=1tondoforj:=1tondobeginread(x);if(i<>j)thenbegininc(tot);a[tot]:=i;b[tot]:=j;l[tot]:=x;end;end;qsort(1,tot);kruskal;在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。+Heap在任何时候都有令人满意的的时间复杂度，但是代价是空间消耗极大。【以及代码很复杂>_<】3.时间复杂度并不能反映出一个算法的实际优劣。竞赛题大多数是稀疏图，所以尽可能地使用Prim+Heap，在稀疏图中这是无敌的。如果一定要在朴素Prim和Kruskal里选一个的话那就用Kruskal吧。当然Prim的代码比较简单，对付水题用Prim也无所谓，只要不是极稀疏图两者相差不大习题：1、最优布线问题（wire）[问题描述]学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，使任意两台计算机都连通（不管是直接的或间接的）。[输入格式]输入文件，第一行为整数n（2<=n<=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。[输出格式]输出文件，一个整数，表示最小的连接费用。[样例输入]3012101210[样例输出]2（注：表示连接1和2，2和3，费用为2）[问题分析]这道题是典型的求最小生成树的题目，可以运用上文所讲的两种算法进行处理。2、【最小生成树算法实例】现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？【输入】第一行两个数v(v<=200),e，分别代表城市数和边数，以下e行，每行为两个顶点和它们之间的边权w(w<1000)。【输出】v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。【输入样例】645633【输出样例】1215183、例题农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。输入格式InputFormat(1)采用邻接矩阵存储第一行为农场的个数，N（3<=N<=100）。接下去为一个N*N的矩阵,表示每个农场之间的距离。(农场之间的距离小于999，0路线表示无法直接到达)。(2)图采用边目录方式存储。第一行N为农场的个数,M为农场与农场之间共有M条可以搭设光纤路线。接下去的M行为中每行有3个数A，B，C。分别表示农场A到农场B的距离为B。输出格式OutputFormat输出连接所有农场并所用光纤最短的方案。样例输入SampleInput(1)采用邻接矩阵存储。(2)采用边目录方式存储。667样例输出SampleOutput