下载文档原格式
考研数据结构图的必背算法及知识点Prepared on 22 November 20201.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。
这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。
n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。
最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。
解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。
他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。
时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。
采用kruskal(克鲁斯卡尔)算法求无向连通网图的一棵最小生成树。
#include<iostream>using namespace std;const int MaxSize=6; // 顶点数const int m=9; //边数int vertexNum, arcNum; //顶点数和边数char vertex[MaxSize]; //顶点数组int parent[MaxSize];struct EdgeType{int from, to;int weight;};EdgeType edge[m];void edgesz(char a[], int n, int e){int i,j,k,w;vertexNum=n; arcNum=e;for (i=0; i<vertexNum; i++) vertex[i]=a[i];for (k=0; k<arcNum; k++) //依次输入每一条边{cin>>i>>j>>w; //边依附的两个顶点的序号及权值edge[k].from=i;edge[k].to=j;edge[k].weight=w;}}int FindRoot(int parent[], int v){int t;t=v;while ( parent[t]>-1) t=parent[t];return t;}void DubbleSort(EdgeType r[],int n){int exchange,bound,j,k;exchange=n-1; //第一趟的区间为1-- nwhile(exchange) //当还未完全有序{ bound=exchange; //传递本趟最后交换位置exchange=0;for(j=0;j<bound;j++) //一趟扫描if (r[j].weight>r[j+1].weight){k=r[j].from;r[j].from=r[j+1].from;r[j+1].from=k;k=r[j].to;r[j].to=r[j+1].to;r[j+1].to=k;k=r[j].weight;r[j].weight=r[j+1].weight;r[j+1].weight=k;exchange=j; } //记录交换位置}}//kruskal(克鲁斯卡尔)算法int main(){int i;char a[MaxSize];cout <<"输入"<<MaxSize<<"个顶点数据："<<endl;for (i=0;i<MaxSize;i++) cin >>a[i];cout <<"依次输入"<<m<<"条边的每一条边两个顶点的序号及权值："<<endl;edgesz(a, MaxSize, m);DubbleSort(edge,m);cout <<"无向连通图的(Kruskal)生成树为："<<endl;Kruskal();cout << endl;return 0;}。
最小生成树的模型数学公式
最小生成树的模型数学公式是：
给定无向连通图G(V,E)，其中V为图的顶点集合，E为图的边集合。
每条边e∈E都带有一个非负权重w(e)。
找到一个包含图中所有顶点的子图T(V,E')，使得E' ⊆ E，并且E'构成一颗树（即连通且无环），使得所有的边的权重之和最小。
拓展：
最小生成树的应用十分广泛，可以用于解决多种问题。
以下是最小生成树的一些常见拓展场景：
1.带有约束条件的最小生成树：
在某些情况下，除了最小化权重之和外，还需要满足一些特定的约束条件。
例如，可以要求最小生成树的边数限制在特定的范围内，或者要求选择特定类型的边。
这时可以在最小生成树的模型中引入额外的约束条件，从而得到满足要求的最小生成树。
2.多目标最小生成树：
有时候，最小生成树问题不仅需要最小化权重之和，还需要考虑其他目标。
例如，可以同时考虑最小化权重之和和最大化生成树中的最长边权重。
这样的问题可以转化为多目标优化问题，并通过权衡不同目标之间的关系来求解。
3.带有边权重动态变化的最小生成树：
在某些场景中，图的边权重可能会根据一些规则进行动态变化。
例如，网络中的通信链路可能会根据网络拓扑和负载情况进行变化。
这时可以通过动态更新最小生成树来快速适应环境变化，从而保持最小生成树的有效性。
总之，最小生成树的模型可以通过引入不同的约束条件和目标函数进行拓展，以适应不同的应用场景。
求无向连通图的生成树————————————————————————————————作者：————————————————————————————————日期:求无向连通图的生成树一、实验目的⑴掌握图的逻辑结构⑵掌握图的邻接矩阵存储结构⑶验证图的邻接矩阵存储及其遍历操作的实现二、实验内容（1)建立无向图的邻接矩阵存储(2)对建立的无向图,进行深度优先遍历(3)对建立的无向图进行广度优先遍历三、设计与编码(1)本实验用到的理论知识（2)算法设计(３)编码／/ 图抽象类型及其实现．cpｐ : Defｉnes ｔhe enｔry poiｎt for the coｎｓｏle aｐplication./／#include"ｓtdafｘ.ｈ"#ｉｎclude"Graｐh.h"#incluｄe"ｉｏｓtream．h＂int Grａｐｈ：:Ｆinｄ(int keｙ,int &ｋ){ﻩiｎt flａg＝0;ﻩfoｒ(iｎt i=0;i＜VｅrtexLｅn;ｉ++)ﻩif(Ａ[ｉ].ｄata.kｅy＝=ｋeｙ){k=ｉ;flaｇ=1;bｒeａk;};ｒetuｒn fｌag;};int Graｐh::CｒeａteGraph(inｔ vertexnuｍ,Edgｅ *E,inｔ edgeｎum)｛／/由边的集合E(E[0]~Ｅ［VｅrtｅｘNum-1]）,生成该图的邻接表表示if(veｒtｅxnum<１）reｔurｎ(－１）;//参数vｅrtｅxnum非法ｉnt i,frｏｎt，reａr,k；ﻩEｎode *ｑ;ﻩ//先生成不带边表的顶点表--即顶点为孤立顶点集ﻩA=newＶnode［verｔexnuｍ］;if(!A)return（0）;//堆耗尽ﻩfｏｒ(i=０;i<vertｅｘnuｍ；i＋+)ﻩ{ﻩﻩA[i].datａ．keｙ＝i;ﻩＡ[i].ｔag=０;ﻩﻩA[ｉ].datａ.ＩnDegｒee=A［i]．dａta．OutDｅｇｒee＝A［ｉ］.tag ＝0；ﻩ A[i].fｉrsｔ=0;}；VｅrtｅxＬeｎ＝vertｅｘnｕm;ﻩ/／在生成边表if(eｄgenuｍ<0）rｅｔｕrｎ(1);//无边的图ﻩfｏr(ｉ=０;i＜edｇeｎum；i++）{front=E[i]．Head；rear=E［i].Taｉｌ;if（!Find(reａr，k) || ！Finｄ（fronｔ,ｋ))return(-2);//参数E非法ﻩﻩq=new Enodｅ；if（!q)rｅturn(0);ﻩｑ－>keｙ=fronｔ;q->Weiｇht=E[i].weigｈｔ;ﻩﻩq->next=A[rear］.fｉrｓｔ;ﻩA[rear]．ｆｉrsｔ=ｑ;ﻩＡ[ｒeａr］.data.OutDegrｅe++;A[frｏnt].data.IｎDegrｅe++;ﻩiｆ(Tｙpe>2)｛ﻩﻩq＝ｎew Enoｄｅ;ﻩｉf(!q)reｔuｒn(０）;q-＞kｅｙ=ｒear；ﻩﻩﻩq－>ｎext=A[front].firｓt;ﻩＡ[fｒｏnt].firsｔ=q；ﻩq－＞Wｅight=E[i].wｅight;ﻩﻩ};｝；ﻩretuｒn(1);｝;voidＧraph::Dfs（iｎt key,int &fｌag){ﻩ//staｔic ｒuｎ=1;ﻩEｎode *ｗ;ﻩA［ｋey］.tａg=ｆlag;if(Type>2)ｃout<＜"连通分量="<＜flａg<<＇\t';cout＜＜"顶点键值="<＜kｅy<<ｅndl；ﻩfor(w=A[kｅy].fiｒsｔ;w ;ｗ＝w-＞ｎｅxt)ﻩﻩiｆ(!A［w->ｋey].tag)Ｄfs（ｗ->ｋey，flaｇ);｝；intＧｒaｐｈ:：DｆsDrａverｓ(ｉntｖ０) /／从指定顶点深度遍历{inｔｉ，k,ｃｏmｐｏnentnum=1；//if(Tｙpe<3）return（-1);/／不考虑由向图//cｏut<<＂ｂｅｇaiｎ..．．\n";if(!(Finｄ(v0,k))){cｏut＜<"fｉnd=＝＂＜<ｋ<＜endl;return （0);};//初始结点v0不存在ｉf(Type>2)cout＜<＂---连通分量＂<＜componeｎtｎum<<＂－--"<<ｅnｄl;ﻩＤfs(k,ｃomponentnuｍ);ｃomｐoｎｅｎtnum++;ﻩfｏｒ（i=０;ｉ<VerｔeｘLen;ｉ＋+)｛ﻩﻩｉf（！A[i].tag）{ﻩｉf(Tyｐe＞２)coｕt<＜"---连通分量"<<ｃoｍｐoｎentnum<＜"---"＜<enｄl；ﻩＤfｓ(i，compｏneｎｔｎuｍ)；compｏnentｎuｍ+＋；ﻩﻩ};}；ﻩreｔurn(componeｎtnum－１）；｝;int Graｐh:：Bfs(）{int i,comp=1; ﻩﻩﻩ／/ｃomp=连通分量的标记,、、...stｒucｔ queue{inｔｋey;qｕeuｅ * nｅxt;};Enode *ｐe;ﻩquｅue *f,*ｒ，*q,*ｐ=new queuｅ;ﻩiｆ(！p）retuｒｎ(-1); ﻩﻩﻩﻩ/／堆耗尽ﻩｐ－>ｎｅxt＝０;ｆ=r=p；ﻩﻩﻩ／/生成空队列fｏr(ｉ＝0;i<ＶerteｘLeｎ;ｉ++)A[ｉ］.tag=0;／/初始化已访问标志ﻩfｏr(i＝０;ｉ<ＶｅrtｅｘLeｎ;i+＋){ﻩﻩif(A[i].tag==０)ﻩ｛ﻩ A[i]．tag=comp;／／入队该顶点的keｙp＝newｑueue；ﻩﻩif(!ｐ)return(-1)；ﻩ p－>kｅｙ=A［i]．ｄata．ｋｅy;ﻩ p->next=0;ﻩﻩf-＞ｎext=ｐ;r=ｐ；ﻩﻩwhｉle(ｆ->next)//当队非空时{//出队一顶点ﻩﻩﻩq=f->ｎexｔ;ﻩﻩﻩif（Tｙpe>2)cｏｕｔ<<"连通分量"<<comp＜<'\t'；ﻩﻩﻩcｏut<<＂顶点键值="<<q->ｋｅy＜<ｅndl;ﻩﻩf-＞neｘt=ｑ-＞neｘt;ﻩﻩﻩｉｆ(q==ｒ)r=f；ﻩﻩﻩ//与q连接的未访问的顶点入队ﻩpｅ=A[ｑ->kｅy］.ｆirst;ﻩﻩwhｉlｅ（pｅ)ﻩﻩ{ﻩﻩﻩﻩif（Ａ[ｐｅ-＞keｙ]．taｇ==0)ﻩﻩ{／/入队ﻩif(!(p=new queue）)rｅtuｒn(-1）;ﻩ A[pｅ－＞key].ｔag=ｃomp;ﻩp->ｋｅy=pe－>ｋey;ﻩﻩﻩp-＞neｘt＝0；ﻩﻩﻩﻩiｆ(f==r)f->next=p；ﻩﻩﻩr->nｅxt=p;r＝p;};ﻩｐe=pｅ－＞nｅｘt；}；／/end of (pe)dｅlete q;ﻩﻩ};／/enｄｏｆ (f->neｘｔ)ﻩcｏmｐ++; ﻩﻩ};//enf oｆ ifﻩ};//释放队列while(f)｛p=f-＞next；dｅletｅf；f＝p;｝;ﻩreturnｃｏｍp－1; /／返回连通分量数};/*int Grａｐh::TopoSoｒｔ(int＊ｑｕe,iｎt &ｎum）{ ／/ｑuｅ顺序队列保存了拓扑排序的结果，f和r为que的头尾指示;loop用于判有无环intｉ,f＝０,r=0，indｅx,lｏoｐ=１;ﻩＥnoｄｅ *pe;ｎｕｍ＝0;fｏｒ(i=0;i＜VerｔｅxLen；ｉ++）A[i]．tａｇ=A［i］.data.InDegr ｅe; //初始化入度到ｔaｇ域ﻩfor(i=０;i<VｅｒｔeｘLen;i＋＋)if（A[i].ｔag==0){ｑue［r++]=i;A[i].ｔaｇ＝－1;loｏｐ=０;｝;if（loｏｐ)ｒeturn（０);ﻩwhile(f<r）{／/栈未处理完ﻩﻩindｅx=ｑue[f＋+];ﻩfor(pe=A[iｎdｅｘ］.ｆｉrst;pe;ｐe=ｐe-＞nexｔ)ﻩ {ﻩﻩA［pｅ->kｅｙ].tａｇ－－;ﻩﻩｉf(Ａ[pe->key].ｔag==0){que[ｒ＋+］=pe－>key;A[pe-＞ｋey].tａg=-1;};};ﻩﻩ};ﻩnum=r;if(r<VertexLen)retuｒｎ(０);//存在环retuｒn 1;};int maiｎ(intａrｇc，char* aｒgｖ［］){ Graph g１(１);int num=5,temｐ=1；int *ｓtaｃｋ=new int[5];ﻩEdｇｅｂ[１2];ﻩｂ[０］.Heａd=1；b[0]．Tail＝0;b[0].weiｇｈｔ=1;b[1]．Heａd=3;ｂ［１]．Tａil=1;b[１].weighｔ=1;ﻩb[2].Ｈead＝0;b[2].Ｔail=2;b[2］.weｉghｔ=１;b［3].Head=1;b[3］．Taｉl=４;b[3]．weigｈt=1；b[4]．Hｅad＝4;b［4].Ｔａiｌ=2;b[4]．weight=1;ｂ［5].Heａd=４;b［5］.Tail=3；b[5].ｗeｉght=1;／/b[6].Heaｄ=0;b［6].Tail＝1;b[6］．ｗｅighｔ=１；ﻩｂ[7].Hｅad=1;b[7].Tａil＝3;b[7].wｅigｈｔ＝1;b[8].Hｅad＝2;b[８].Tail＝0;ｂ[8］.weight=1;ﻩb［9].Heaｄ=4;b[９]．Taｉl=1;b［9].wｅight=1;ﻩb[１0].Ｈead=2；b[10].Taiｌ=4；b[10].weｉｇｈｔ＝1;b[11]．Heａd=3;b[11]．Taｉl=2;b[１１]．weigｈt=1;／/b=={{１,０,１},｛３,１,1},{０，2,1},(１,４,1},{４,2,1}，{2,3，１}};g1.CreａtｅGｒapｈ(ｎum,b,６）;if(g１．GetTypｅ()＞2）ｃout＜<"连通分量数="＜<g1.DfsDravｅrs(2）<＜ｅndl;ﻩcoｕt<＜"－－－---------－-"<<endl;iｆ(ｇ１.GetTｙpe()＞2）coｕt<＜＂连通分量数="<<ｇ１.Bfs()<<ｅndl;ｉf（g1.GetＴyｐｅ()<3){ﻩif(ｇ1.TopoSｏｒt(stａｃｋ,tｅｍp))couｔ<＜"拓扑排序成功！\n";ﻩelseｃout<<"该图有环！\n";ﻩﻩcout＜<"部分或全部的拓扑序列为:(顶点总数="＜<g1.ＧetＬｅn(）<<")＼n"；ﻩfｏｒ(int i=０；i＜ｔemp;i++)ｃout<<sｔack[i］＜<'\t';ｃout ＜＜"已排序顶点数目=＂<<ｔemｐ<<enｄｌ;};ﻩdelete[5］sｔack;ﻩ／/prｉntf("Helｌｏ Wｏｒlｄ!\n")；ﻩreturｎ０;}四、运行与调试运行结果为:该图有环！部分或全部拓扑序列为:<顶点总数=5>20 已排序顶点数目=2Pｒeｓs aｎy key to ｃontinue五、总结与心得。
