圖算法

圖是由一個頂點集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