图算法1(最小生成树)

图算法

图是由一个顶点集V和一个弧集R构成的数据结构。

Graph=(V,R)其中，VR＝{<v,w>|v,w∈V且P(v,w)}

<v,w>表示从v到w的一条弧，并称w为弧头，v为弧尾。

图的结构定义:

由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。

ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}若<v,w>VR

必有<w,v>VR,则称(v,w)为顶点v和顶点w之间存在一条边。

BCADFE由顶点集和边集构成的图称作无向图。例如:G2=(V2,VR2)假设图中有

n

个顶点，e

条边，则

含有e=n(n-1)/2条边的无向图称作完全图；

含有e=n(n-1)条弧的有向图称作

有向完全图；若边或弧的个数e<nlogn，则称作稀疏图，否则称作稠密图。

假若顶点v和顶点w之间存在一条边，则称顶点v

和w

互为邻接点，ACDFE例如:TD(B)=3TD(A)=2边(v,w)

和顶点v和w

相关联。

和顶点v关联的边的数目定义为边的度。B顶点的出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说，顶点的入度:以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3

假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFE设有6个结点的无向图，该图至少应有_____条边才能确保是一个连通图。在一个无向图中，所有顶点度数之和等于图的边数的_______倍。具有N个顶点的有向图最多有_____条边。练习ABCDEFAij={0(i,j)VR1(i,j)VR一、图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为ABCDEF010010100011000101001001110000011100有向图的邻接矩阵为非对称矩阵ABECDtypedef

struct

ArcCell{//弧的定义

VRType

adj;//VRType是顶点关系类型。

//对无权图，用1或0表示相邻否；

//对带权图，则为权值类型。

InfoType*info;//该弧相关信息的指针}ArcCell,

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef

struct{//图的定义

VertexType//顶点信息

vexs[MAX_VERTEX_NUM];

AdjMatrixarcs;//弧的信息

int

vexnum,arcnum;//顶点数，弧数

GraphKindkind;//图的种类标志

}

MGraph;0A141B0452C353D254E015F123BACDFE二、图的邻接表存储表示有向图的邻接表142301201234ABCDE

ABECD可见，在有向图的邻接表中不易找到指向该顶点的弧。typedef

struct

ArcNode

{

int

adjvex;//该弧所指向的顶点的位置

struct

ArcNode

*nextarc;//指向下一条弧的指针

InfoType

*info;//该弧相关信息的指针}

ArcNode;adjvex

nextarcinfo弧的结点结构typedef

struct

VNode

{

VertexTypedata;//顶点信息

ArcNode

*firstarc;//指向第一条依附该顶点的弧

}

VNode,AdjList[MAX_VERTEX_NUM];

datafirstarc顶点的结点结构三、有向图的十字链表存储表示

弧的结点结构弧尾顶点位置弧头顶点位置弧的相关信息指向下一个有相同弧尾的结点指向下一个有相同弧头的结点四、无向图的邻接多重表存储表示结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作遍历插入和删除弧基本操作图的遍历

从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索广度优先搜索Vw1SG1SG2SG3W1、W2和W3

均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3

的子图。访问顶点V：for(W1、W2、W3)

若该邻接点Wi未被访问，

则从它出发进行深度优先搜索遍历。w2w3w2

(连通网的)最小生成树MST(minimumspanningtree)

假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。算法二：（克鲁斯卡尔算法）该问题等价于：算法一：（普里姆算法）

取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。普里姆算法的基本思想:abcdegf例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U

和尚未落在生成树上的顶点集V-U

，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。

一般情况下所添加的顶点应满足下列条件:Prim算法过程bchifaedg488414791067211aidcbhgfe12全部节点都被覆盖，算法结束abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c55具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：abcdegf195141827168213ae12dcbgf7148531621例如:7121819Kruskal算法过程bchifaedg488414791067211aidcbhgfe12构成环路构成环路构成环路全部节点都被覆盖，算法结束普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围比较两种算法贪心准则

Prim算法加入后仍形成树，且耗费最小始终保持树的结构——Kruskal算法是森林Kruskal算法每个步骤选择一条边加入生成树不会产生环路，且耗费最小下面看一个例子：

Agri-NetDescription

FarmerJohnhasbeenelectedmayorofhistown!Oneofhiscampaignpromiseswastobringinternetconnectivitytoallfarmsinthearea.Heneedsyourhelp,ofcourse.

FarmerJohnorderedahighspeedconnectionforhisfarmandisgoingtosharehisconnectivitywiththeotherfarmers.Tominimizecost,hewantstolaytheminimumamountofopticalfibertoconnecthisfarmtoalltheotherfarms.

Givenalistofhowmuchfiberittakestoconnecteachpairoffarms,youmustfindtheminimumamountoffiberneededtoconnectthemalltogether.Eachfarmmustconnecttosomeotherfarmsuchthatapacketcanflowfromanyonefarmtoanyotherfarm.

Thedistancebetweenanytwofarmswillnotexceed100,000.

Input

Theinputincludesseveralcases.Foreachcase,thefirstlinecontainsthenumberoffarms,N(3<=N<=100).ThefollowinglinescontaintheNxNconectivitymatrix,whereeachelementshowsthedistancefromonfarmtoanother.Logically,theyareNlinesofNspace-separatedintegers.Physically,theyarelimitedinlengthto80characters,sosomelinescontinueontoothers.Ofcourse,thediagonalwillbe0,sincethedistancefromfarmitoitselfisnotinterestingforthisproblem.Output

Foreachcase,outputasingleintegerlengththatisthesumoftheminimumlengthoffiberrequiredtoconnecttheentiresetoffarms.SampleInput

4 04921 40817 98016 2117160SampleOutput

28

这个题目，实际上是给了N个顶点，每两个顶点间的距离已经给出，让你求一条最小权值的路径，该路径使得所有的farms能够相互到达。这是典型的最小生成树。分析2431421816179代码：(朴素prim）#include<iostream.h>intmain(){

inti,j,k,n,a[101][101];

while(scanf("%d",&n)!=EOF){

for(i=1;i<=n;i++){

for(j=1;j<=n;j++){

scanf("%d",&a[i][j]);}}

intflag[101]={0},sum=0;//flag[i]用来标记节点i是否被覆盖

flag[1]=1;//选取第一个点

for(k=1;k<n;k++)//循环n-1次

{

intmin=-1,min_i;

for(i=1;i<=n;i++)//选取下一个最小权值的节点

{

if(flag[i]==0&&(min==-1||a[1][i]<min)){min=a[1][i];min_i=i;}}

flag[min_i]=1;//覆盖节点

for(i=1;i<=n;i++)//更新未覆盖节点的距离

{

if(flag[i]==0&&a[1][i]>a[min_i][i]){a[1][i]=a[min_i][i];}}sum+=a[1][min_i];//加上权值

}

printf("%d\n",sum);}return0;}Kruskal算法的实现

并查集还有其他优化策略，比如路径压缩，这里不再论述。对于kruskal算法，在判断加入的边(u,v)是否构成回路时，只需判断Find(u)与Find(v)是否相等即可。若相等，则构成回路，否则不构成回路。

例子的kruskal程序如下：#include<stdio.h>#include<memory.h>#include<algorithm>usingnamespacestd;#defineN10000structEdge{

int

u,v,w;};classUFset{private:

bool*root;

int*parent;

intn;public:

UFset(intn){

inti;this->n=n;root=newbool[n];parent=newint[n];

for(i=0;i<n;i++){

parent[i]=1;root[i]=true;}}~UFset(){delete[]parent;delete[]root;}

int

Find(inte){//Returnrootoftreecontaininge.//Compactpathfrometoroot.

inti=e;//Findroot

while(!root[i])i=parent[i];//compact

intj=e;//startate

while(j!=i)//jisnotroot{

int

pj=parent[j];

parent[j]=i;//movejtolevel2j=pj;//jmovestooldparent}returni;}Kruskal算法的实现

bool

Union(int

x,inty){//Combinetreeswithrootspxandpy.

int

px=Find(x);

int

py=Find(y);

if(px==py)returnfalse;

if(parent[px]<parent[py]){//pxbecomessubtreeofpy

parent[py]+=parent[px];

root[px]=false;

parent[px]=py;}else{//pybecomessubtreeofpx

parent[px]+=parent[py];

root[py]=false;

parent[py]=px;}returntrue;}};classgraph{public:

int

n,m;Edgeedge[N];voidkruskal();};bool

cmp(constEdge&e1,constEdge&e2){returne1.w<e2.w;}voidgraph::kruskal(){

sort(edge,edge+m,cmp);

UFset

ufset(n);

intmin=0,k=0;

for(inti=0;i<m;i++){

if(ufset.Union(edge[i].u,edge[i].v)){min+=edge[i].w;++k;}

if(k==n-1)break;}

printf("%d\n",min);}Kruskal算法的实现graphg;intmain(){

int

i,j,w;

while(scanf("%d",&g.n)!=EOF){

intk=0;

for(i=0;i<g.n;i++){

for(j=0;j<g.n;j++){

scanf("%d",&w);

if(i<j){

g.edge[k].u=i;g.edge[k].v=j;

g.edge[k].w=w;k++;}}}

g.m=k;g.kruskal();}return0;}练习：1751HighwaysHighwaysDescriptionTheislandnationofFlatopiaisperfectlyflat.Unfortunately,Flatopiahasaverypoorsystemofpublichighways.TheFlatopiangovernmentisawareofthisproblemandhasalreadyconstructedanumberofhighwaysconnectingsomeofthemostimportanttowns.However,therearestillsometownsthatyoucan'treachviaahighway.Itisnecessarytobuildmorehighwayssothatitwillbepossibletodrivebetweenanypairoftownswithoutleavingthehighwaysystem.

Flatopiantownsarenumberedfrom1toNandtownihasapositiongivenbytheCartesiancoordinates(xi,yi).Eachhighwayconnectsexacltytwotowns.Allhighways(boththeoriginalonesandtheonesthataretobebuilt)followstraightlines,andthustheirlengthisequaltoCartesiandistancebetweentowns.Allhighwayscanbeusedinbothdirections.Highwayscanfreelycrosseachother,butadrivercanonlyswitchbetweenhighwaysatatownthatislocatedattheendofbothhighways.

TheFlatopiangovernmentwantstominimizethecostofbuildingnewhighways.However,theywanttoguaranteethateverytownishighway-reachablefromeveryothertown.SinceFlatopiaissoflat,thecostofahighwayisalwaysproportionaltoitslength.Thus,theleastexpensivehighwaysystemwillbetheonethatminimizesthetotalhighwayslength.SampleInput91500324551045212533139712SampleOutput1637495783代码：#include<iostream>#include<math.h>#include<iomanip>usingnamespacestd;inta[760][760],b[760],f[760],x[760],y[760],pre[760];//pre[i]用于记录与第i个点相连的点,输出时是2到N；intlen(intx1,inty1,intx2,inty2){return((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//刚才开始这里开方，丢精度，影响计算结果，干脆不开方，结果对sum不要求!!!}intmain(){inti,t,j,k,ival,num1,num2,num,MIN;scanf("%d",&ival);for(i=1;i<=ival;++i){scanf("%d%d",&x[i],&y[i]);}for(i=1;i<=ival;++i){for(j=1;j<=ival;++j){a[i][j]=len(x[i],y[i],x[j],y[j]);}}scanf("%d",&num);for(i=1;i<=num;++i){scanf("%d%d",&num1,&num2);a[num1][num2]=a[num2][num1]=0;}for(i=1;i<=ival;++i){f[i]=0;b[i]=a[i][1];pre[i]=1;//将各个点都与1相连}f[1]=1;for(t=1;t<ival;++t){MIN=2147483640;for(i=2;i<=ival;++i){if(!f[i]&&MIN>b[i]){MIN=b[i];k=i;}}f[k]=1;for(i=2;i<=ival;++i){if(b[i]>a[i][k]&&!f[i]){b[i]=a[i][k];pre[i]=k;//找到与t相连的点，如果没有进行到这一步，则说明t与1相连是最短的}}}for(i=2;i<=ival;i++){if(a[pre[i]][i]!=0)printf("%d%d\n",pre[i],i);}return0;}1639PicnicPlanningDescriptionTheContortionBrothersareafamoussetofcircusclowns,knownworldwidefortheirincredibleabilitytocramanunlimitednumberofthemselvesintoeventhesmallestvehi