課程資源數(shù)據(jù)結(jié)構(gòu)與算法chapter

Chapter9GraphsDefinitionofgraphsandsometerminologyGraphrepresentationsSomealgorithms9.1DefinitionandterminologiesDefinitionofgraphs:Graph=(V,E)V:nonemptyfiniteverticesetE:edgesetUndirectedGraph:Ifthetupledenotinganedgeisunordered,then(v1,v2)and(v2,v1)arethesameedge.9.1DefinitionandterminologiesDirectedgraph:Ifthetupledenotinganedgeisordered,then<v1,v2>and<v2,v1>aredifferentedges.v1:始點(diǎn)v2:終點(diǎn)9.1Definitionandterminologies

Example:V1V2V4V3V(G1)={V1,V2,V3,V4}E(G1)={(V1,V2),(V1,V3),(V1,V4),(V2,V3),(V2,V4),(V3,V4)}G1V1V2V(G2)={V1,V2,,V3}E(G2)={<V1,V2>,<V2,V1>,<V2,V3>}V3G29.1Definitionandterminologies

Wewillnotdiscussgraphsofthefollowingtypes多重圖9.1DefinitionandterminologiespletegraphInanundirectedgraphwithnnodes,thenumberofedges<=n*(n-1)/2.If“=“issatisfied,thenitiscalledacompleteundirectgraph.V2V4V3V19.1Definitionandterminologies

Inadirectedgraphwithnnodes,thenumberofedges<=n*(n-1).If“=“issatisfied,thenitiscalledacompletedirectedgraph.9.1Definitionandterminologies3.degreedvofvertexv,TD(v):isthenumberofedgesincidentonvertexv.Inadirectedgraph:in-degreeofvertexvisthenumberofedgesincidenttov,ID(v).out-degreeofvertexvisthenumberofedges incidentfromthev,OD(v).9.1Definitionandterminologies

TD(v)=ID(v)+OD(v)

Generally,iftherearenverticesandeedgesinagraph,thene=(TD(vi))/2v1v2v3ID(v2)=1OD(v2)=2TD(v2)=3i=1n9.1Definitionandterminologies4.SubgraphGraphG=(V,E),G’=(V’,E’),ifV’V,E’E,andtheverticesincidentontheedgesinE’areinV’,thenG’isthesubgraphofG.Forexample1Definitionandterminologies

Anotherexample:V2V4V3V1V2V3V1V19.1Definitionandterminologies5.path.AsequenceofverticesP=i1,i2,……ikisani1toik

path

inthegraphofgraphG=(V,E)ifftheedge(ij,ij+1)isinEforeveryj,1<=j<k.6.Simplepathandcycle

ASimplepathisapathinwhichallverticesexceptpossiblythefirstandlast,aredifferent.

ASimplecycleisasimplepathwiththesamestartandendvertex.9.1Definitionandterminologies

Anexampleofacycle

9.1Definitionandterminologies7.Connectedgraph&ConnectedcomponentInaundirectedgraph,ifthereisapathfromvertexv1tov2,thenv1andv2areconnected.Inaundirectedgraph,iftwoarbitraryverticesareconnected,thenthegraphisaconnectedgraph.9.1Definitionandterminologies

Examples:

Non-connectedgraphMaximumconnectedsubgraph(極大連通子圖)iscalledconnectedcomponent.9.1Definitionandterminologies8.StrongconnectedgraphandstronglyconnectedcomponentAdigraphisstronglyconnectediffitcontainsadirectedpathfromitojandfromjtoiforeverypairofdistinctverticesiandj.Themaximumstrongconnectedsubgraph(極大強(qiáng)連通子圖)ofanon-stronglyconnectedgraphiscalledstronglyconnectedconponent(強(qiáng)連通分量).9.1Definitionandterminologies9.NetworkWhenweightsandcostsareassignedtoedges,theresultingdataobjectiscalledweightedgraphandweighteddigraph.Thetermnetworkreferstoweightedconnectedgraphandweightedconnecteddigraph.9.1Definitionandterminologies

Exampleofanetwork

V1V3V2V4V552348611109.1Definitionandterminologies10.SpanningtreeAspanningtreeofaconnectedgraphisitsminimumconnectedsubgraph(極小連通子圖).Ann-vertexspanningtreehasn-1edges.Forexample:123412349.2ADTGraphandDigraph

AbstractDataTypeGraph{instancesasetVofverticesandasetEofedgesoperationsCreate(n):createanundirectedgraphwithnverticesandnoedgesExist(i,j):returntrueifedge(i,j)exists;falseotherwiseEdges():returnthenumberofedgesinthegraphVertices():returnthenumberofverticesinthegraphAdd(i,j):addtheedge(i,j)tothegraphDelete(i,j):deletetheedge(i,j)Degree(i):returnthedegreeofvertexiInDegree(i):synonymfordegreeOutDegree(i):synonymfordegree}9.3Representationofgraphsanddigraphs1.AdjacencyMatrixG=(V,E),V={V1,V2,……,Vn}thentheadjacencymatrixofgraphG:

A(i,j)=1if<i,j>,<j,i>Eor(i,j)E0otherwise9.3Representationofgraphsanddigraphs

Forexample:graphV1V2V3V4A(i,j)=01111011110011001)Adjacencymatrixofgraphisasymmetricmatrix2)A(i,j)=A(j,i)=di(degreeofvertexi)nj=1nj=19.3Representationofgraphsanddigraphs

DigraphV1V2V5V4V3A(i,j)=0100010001010101000100000

A(i,j)=dioutA(j,i)=diin

j=1nnj=19.3Representationofgraphsanddigraphs

Representationofnetworks,replace1withweights,otherswith∞W(i,j)ifi!=jand<i,j>,<j,i>Eor(i,j)E

∞otherwise

A(i,j)=9.3Representationofgraphsanddigraphs

Forexample:341286231495A(i,j)=∞1∞4∞

∞9235∞8∞

∞6∞

除以上的鄰接矩陣外，還要一個(gè)記錄各頂點(diǎn)信息的表，

一個(gè)當(dāng)前的邊數(shù)

其類說(shuō)明：

constintMaxNumEdges=50//最大邊數(shù)

constintMaxNumVertices=10//最大頂點(diǎn)數(shù)

template<classNameType,classDistType>classGraph

{private:

SeqList<NameType>VerticesList(MaxNumVertices)//頂點(diǎn)表

DistTypeEdge[MaxNumVertices][MaxNumVertices]//鄰接矩陣

intCurrentEdges;//當(dāng)前邊數(shù)

intFindVertex(Seqlist<NameType>&L;constNameType&Vertex){returnL.Find(Vertex);}

intGetVertexPos(constNameTyoe&Vertex)

{returnFindVertex(VerticesList);}

//給出了頂點(diǎn)Vertex在圖中的位置

V0

V1

V2

V3

.

.

dataMaxsize012n-1public:

Graph(constintsz=MaxNumEdges);

intGraphEmpty()const{returnVerticesList.IsEmpty();}

intGraphFull()const{returnVerticesList.IsFull()||

CurrentEdges==MaxNumEdges;}

intNumberofVertices(){returnVerticesList.last;}

intNumberofEdges(){returnCurrentEdges;}

NameTypeGetvalue(constinti)

{returni>=0&&i<VerticesList.last?VerticesList.data[i]:NULL;}

DistTypeGetweight(constintv1,constintv2);

intGetFirstNeighbor(constintv);

intGetNextNeighbor(constintv1,constintv2);

voidInsertVertex(constNameType&Vertex);

voidInsertEdge(constintv1,constintv2,DistTypeweight);

voidremoveVertex(constintv);

voidremoveEdge(cosntintv1,constintv2);

}

Constructor

template<classNameType,classDistType>

Graph<NameType,DistType>::Graph(intsz){for(inti=0;i<sz;i++)

for(intj=0;j<sz;j++)Edge[i][j]=0;

currentEdge=0;

}

求頂點(diǎn)V的第一個(gè)鄰接頂點(diǎn)的位置

template<classNameType,classDistType>intGraph<NameType,DistType>::GetFirstNeighbor(intv){if(v!=-1)

{for(intcol=0;col<CurrentVertices;col++)

if(Edge[v][col]>0&&Edge[v][col]<max)returncol;

}

return-1;

}9.3Representationofgraphsanddigraphs2.Linked-adjacencyListsreducethestoragerequirementifthenumberofedgesinthegraphissmall.V1V3V2V4430243011201201234

h

destlink

9.3Representationofgraphsanddigraphs

Digraph:V1V2V311346224311032016130123

h

destcostlink

26330220140111123

h又稱逆鄰接表

關(guān)于鄰接表的聲明

constintDefaultsize=10;

template<classNameType，classDistType>classGraph;

template<classDistType>structEdge//邊的定義{friendclassGraph<NameType,DistType>;

intdest;//邊的另一頂點(diǎn)在頂點(diǎn)表中的位置

DistTypecost;//邊上的權(quán)

Edge<DistType>*link;//下一條邊的鏈指針

Edge(){}

Edge(intD,DistTypeC):dest(D),cost(C),link(NULL){}

intoperate!=(constEdge<DistType>&E)const

{returndest!=E.dest;}}template<classNameType,classDistType>structVertex{friendclassEdge<DistType>;

friendclassGraph<NameType,DistType>;

NameTypedata;//頂點(diǎn)名字

Edge<DistType>*adj;//出邊表頭指針}邊的三個(gè)數(shù)據(jù)成員

dataadjNodeTable:destcostlink圖的類定義template<classNameType，classDistType>classGraph{private:

Vertex<NameType,DistType>*NodeTable;//頂點(diǎn)表

intNumVertices;//當(dāng)前頂點(diǎn)數(shù)

intMaxNumVertices;//最大頂點(diǎn)個(gè)數(shù)

intNumEdges;//當(dāng)前邊數(shù)

intGetVertexpos(constType&Vertex);

public:

Graph(intsz);

~Graph();

intGraphEmpty()const{returnNumVertices==0;}

intGraphFull()const

{returnNumVertices==MaxNumVertices;}intNumberOfVertices(){returnNumVertices;}

intNumberOfEdges(){returnNumEdges;}

NameTypeGetValue(constinti)

{returni>=0&&i<NumVertices?NodeTable[i].data:NULL;}

voidInsertVertex(constNameType&Vertex);

voidRemoveVertex(intv);

圖的私有數(shù)據(jù)成員

voidInsertEdge(intv1,intv2,DistTypeweight);

voidRemoveEdge(intv1,intv2);

DistTypeGetweight(intv1,intv2);

intGetFristNeighbor(intv);

intGetNextNeighbor(intv1,intv2);}

1）Constructortemplate<classNameType,classDistType>Graph<NameType,DistType>::

Graph(intsz=Defaultsize):NumVertices(0),MaxNumVertices(sz),NumEdge(0){intNumVertices,NumEdges,k,j;

NameTypename,tail,head;

DistTypeweight;

NodeTable=newVertex<NameType>[MaxNumVertices]

cin>>NumVertices;//輸入頂點(diǎn)數(shù)

for(inti=0;i<NumVertices;i++)

{cin>>name;

InsertVertex(name);}

cin>>NumEdges;//輸入邊數(shù)

for(i=0;i<NumEdges;i++)

{cin>>tail>>head>>weight;

k=GetVertexpos(tail);

j=GetVertexpos(head);

InsertEdge(k,j,weight);

}}

intGraph<NameType,DistType>::

GetVertexpos(constNameType&Vertex)

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

if(NodeTable[i].data==Vertex)returni;return–1;

}

2)給出頂點(diǎn)V的第一個(gè)鄰接頂點(diǎn)的位置

template<classNameType,classDistType>intGraph<NameType,DistType>::GetFirstNeighbor(intv){

if(v!=-1){Edge<DistType>*p=NodeTable[v].adj;

if(p!=NULL)returnpdest;

}

return–1}

template<classNameType,classDistType>intGraph<NameType,DistType>::GetNextNeighbor

(intv1,intv2){if(v1!=-1)

{Edge<DistType>*p=NodeTable[v1].adj;while(p!=NULL)

{if(pdest==v2&&plink!=NULL)

returnplinkdest;elsep=plink;}}return–1;}

3.鄰接多重表(adjacencymultilist)

在無(wú)向圖中,如果邊數(shù)為m,則在鄰接表表示中需2m個(gè)單位來(lái)存儲(chǔ).為了克服這一缺點(diǎn),采用鄰接多重表,每條邊用一個(gè)結(jié)點(diǎn)表示.V2V4

V1V3e1e2e4e3e5dataFirstoutV1V2V4V3020301

2123vertex1path1vertex2path2e1e2e3e4e5

對(duì)有向圖而言，需用鄰接表和逆鄰接表，如果把這兩

個(gè)表結(jié)合起來(lái)用有向圖的鄰接多重表(也稱為十字鏈表)

來(lái)表示一個(gè)有向圖.ADEBCe3e6e5e4e2e1A

B

C

12∧∧D

E

34∧∧23∧∧40∧∧01∧dataFirstinFirstout03∧

markv1v2p1p2e1e2e3e4e5e69.4圖的遍歷與連通性

圖的遍歷(GraphTraversal):

從圖中某一頂點(diǎn)出發(fā)訪問(wèn)圖中其余頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次.

遍歷二叉樹(shù):前序,中序,后序.

遍歷樹(shù):深度優(yōu)先遍歷(先根,后根)

廣度優(yōu)先遍歷遍歷森林:深度優(yōu)先遍歷(先根,中根,后根)

廣度優(yōu)先遍歷遍歷圖:深度優(yōu)先遍歷DFS(DepthFirstSearch)

廣度優(yōu)先遍歷BFS(BreadthFirstSearch)1.深度優(yōu)先搜索(depth-first-search)

思想:從圖中某個(gè)頂點(diǎn)V0出發(fā),訪問(wèn)它,然后選擇一個(gè)

V0鄰接到的未被訪問(wèn)的一個(gè)鄰接點(diǎn)V1出發(fā)深度優(yōu)先遍

歷圖,當(dāng)遇到一個(gè)所有鄰接于它的結(jié)點(diǎn)都被訪問(wèn)過(guò)了的

結(jié)點(diǎn)U時(shí),回退到前一次剛被訪問(wèn)過(guò)的擁有未被訪問(wèn)的

鄰接點(diǎn)W,再?gòu)腤出發(fā)深度遍歷,……直到連通圖中的所

有頂點(diǎn)都被訪問(wèn)過(guò)為止.

以有向圖為例:v1v2v6v5v4v3v8v7v1v2v6v5v4v3v8v7V1V2V4V8V5V3V6V7深度優(yōu)先生成樹(shù)

遞歸方法實(shí)現(xiàn)

算法中用一個(gè)輔助數(shù)組visited[]:0:未訪問(wèn)1:訪問(wèn)過(guò)了

假設(shè)圖為連通圖

主過(guò)程:

template<NameType,DistType>

voidGraph<NameType,DistType>::DFS(){int*visited=newint[NumVertices];

for(inti=0;i<NumVertices;i++)visited[i]=0;

DFS(0,visited);//從頂點(diǎn)0開(kāi)始深度優(yōu)先搜索

delete[]visited;}子過(guò)程：

template<NameType,DistType>voidGraph<NameType,DistType>:: DFS(intv,visited[]){cout<<GetValue(v)<<‘’;

visited[v]=1;

intw=GetFirstNeighbor(v);

while(w!=-1)

{if(!visited[w])DFS(w,visited);

w=GetNextNeighbor(v,w);

}}

用圖的抽象數(shù)據(jù)類型來(lái)實(shí)現(xiàn)

算法分析：

用鄰接表表示O(n+e)

用鄰接矩陣表示O(n2)

Javavoiddfs(Vertexv){v.visited=true;foreachwadjacenttovif(!w.visited)dfs(w);}//偽代碼2.廣度優(yōu)先遍歷（breadthsearch）思想：從圖中某頂點(diǎn)V0出發(fā)，在訪問(wèn)了V0之后依次訪

問(wèn)v0的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接

點(diǎn)出發(fā)廣度優(yōu)先遍歷圖，直至圖中所有頂點(diǎn)都被訪問(wèn)

到為止.例子

v1v2v6v5v4v3v8v7v1v2v6v5v4v3v8v7

算法同樣需要一個(gè)輔助數(shù)組visited[]表示頂點(diǎn)是否被訪問(wèn)過(guò).還需要一個(gè)隊(duì)列,記正在訪問(wèn)的這一層和上一層的頂點(diǎn).

算法顯然是非遞歸的.廣度優(yōu)先生成樹(shù)V1→V2→V3→V4→V5→V6→V7→V8

template<NameType,DistType>

voidGraph<NameType,DistType>::BFS(intv){int*visited=newint[NumVertices];

for(inti=0;i<NumVertices;i++)visited[i]=0;

cout<<GetValue(v)<<‘’;

visited[v]=1;

queue<int>q;

q.EnQueue(v);

while(!q.IsEmpty())

{v=q.DeQueue();

intw=GetFirstNeighbor(v);

while(w!=-1)

{if(!visited[w])

{cout<<GetValue(w)<<‘’;visited[w]=1;

q.EnQueue(w);

}

w=GetNextNeighbor(v,w);

}

}

delete[]visited;}

算法分析：每個(gè)頂點(diǎn)進(jìn)隊(duì)列一次且只進(jìn)一次，∴算法

中循環(huán)語(yǔ)句至多執(zhí)行n次。從具體圖的存儲(chǔ)結(jié)構(gòu)來(lái)看：

1)如果用鄰接表：循環(huán)總時(shí)間代價(jià)為d0+d1+…+dn-1=O(e)

其中di是頂點(diǎn)i的度

2)如果用鄰接矩陣:對(duì)每個(gè)被訪問(wèn)過(guò)的頂點(diǎn)，循環(huán)檢測(cè) 矩陣中n個(gè)元素，∴時(shí)間代價(jià)為O(n2)3.連通分量

以上討論的是對(duì)一個(gè)無(wú)向的連通圖或一個(gè)強(qiáng)連通圖的

有向圖進(jìn)行遍歷，得到一棵深度優(yōu)先或廣度優(yōu)先生成樹(shù).但當(dāng)無(wú)向圖(以無(wú)向圖為例)為非連通圖時(shí)，從圖的某一

頂點(diǎn)出發(fā)進(jìn)行遍歷(深度，廣度)只能訪問(wèn)到該頂點(diǎn)所在

的最大連通子圖(即連通分量)的所有頂點(diǎn).

例子：ABCDEFGHJIKLMNO非連通無(wú)向圖非連通圖的連通分量A,B,F,G,E,C,D

H,I,JABCDEFGHJIKLMNOK,L,O,M,N下面是利用深度優(yōu)先搜索求非連通圖的連通分量算法實(shí)際上只要加一個(gè)循環(huán)語(yǔ)句就行了.

Template<NameType,DistType>

voidGraph<NameType,DistType>::components(){int*visited=newint[NumVertices];

for(inti=0;i<NumVertices;i++)visited[i]=0;

for(i=0;i<NumVertices;i++)

if(!visited[i])

{DFS(i,visited);

ponent();

}

delete[]visited;

}

9.5最小生成樹(shù)

生成樹(shù)不唯一生成樹(shù)的代價(jià)：TE（G）上諸邊的代價(jià)之和n個(gè)結(jié)點(diǎn)的生成樹(shù)有n-1條邊。1.生成樹(shù)的有關(guān)概念

生成樹(shù)的定義

設(shè)G=（V，E）是一個(gè)連通的無(wú)向圖（或是強(qiáng)連通有向圖）從圖G中的任一頂點(diǎn)出發(fā)作遍歷圖的操作，把遍歷走過(guò)的邊的集合記為TE（G），顯然G’=（V，TE）是G之子圖，G’被稱為G的生成樹(shù)（spanningtree），也稱為一個(gè)連通圖.

最小代價(jià)生成樹(shù)（minimun-costspanningtree）問(wèn)題的提出：如何找到一個(gè)網(wǎng)絡(luò)的最小生成樹(shù)，即各邊權(quán)的總和為最小的生成樹(shù)實(shí)際例子：6個(gè)城市已固定，現(xiàn)從一個(gè)城市發(fā)出信息到每一個(gè)城市如何選擇或鋪設(shè)通信線路，使花費(fèi)（造價(jià)）最低。前提：每條邊有代價(jià)

1423566551426356如果用廣度優(yōu)先，則12345661534=19最小代價(jià)生成=15兩個(gè)算法：Prim,Kruskal.它們都采用了逐步求解（Grandy)的策略。Grandy策略：設(shè)：連通網(wǎng)絡(luò)N={V,E},V中有n個(gè)頂點(diǎn)。1)先構(gòu)造n個(gè)頂點(diǎn)，0條邊的森林F={T0,T1,…..,Tn-1}2)每次向F中加入一條邊。該邊是一端在F的某棵樹(shù)Ti上而另一端不在Ti上的所有邊中具有最小權(quán)值的邊。這樣使F中兩棵樹(shù)合并為一棵，樹(shù)的棵數(shù)-13)重復(fù)n-1次

T0Tn-1

T1最小生成樹(shù)的類聲明：constintMAXINT=機(jī)器可表示的，問(wèn)題中不可能出現(xiàn)的大數(shù)classMinSpanTree;classMSTEdgeNode{friendclassMinSpanTree;private:inttail,head;intcost;};tailcosthead邊的結(jié)構(gòu):

classMinSpanTree{public:MinSpanTree(intSZ=NumVertices-1):MaxSize(SZ),n(0) {edgevalue=newMSTEdgeNode[MaxSize];}protected:MSTEdgeNode*edgevalue;//邊值數(shù)組

intMaxSize,n; //數(shù)組的最大元素個(gè)數(shù)和 //當(dāng)前個(gè)數(shù)}；Kruskal算法1)把無(wú)向圖中的所有邊排序

1342521012986372367891012（1,2)(3,5)(3,4)(4,5)(2,3)(2,5)(1,4)(1,3)2)一開(kāi)始的最小生成樹(shù)為

T(V,TE)即由n個(gè)不同的連通分量組成

TE=3)在E中選一條代價(jià)最小的邊（u,v)加入T，一定要滿足（u,v)不和

TE中已有的邊構(gòu)成回路，EE-{(u,v)},TE=TE{(u,v)}4)一直到TE中加滿n-1條邊為止。13452134522134522313452236134522368

圖用鄰接矩陣表示，edge(邊的信息）

圖的頂點(diǎn)信息在頂點(diǎn)表Verticelist中

邊的條數(shù)為CurrentEdges

取最小的邊以及判別是否構(gòu)成回路，取最小的邊利用:最小堆（MinHeap)

判別是否構(gòu)成回路利用：并查集（DisjointSets)克魯斯卡爾算法

voidGraph<string,float>::Kruskal(MinSpanTree&T){MSTEdgeNodee;MinHeap<MSTEdgeNode>H(currentEdges);intNumVertices=VerticesList.Last,u,v;

UfsetsF(NumVertices);//建立n個(gè)單元素的連通分量

for(u=0;u<NumVertices;u++)for(v=u+1;v<NumVertices;v++)if(Edge[u][v]!=MAXINT) {e.tail=u;e.head=v;e.cost=Edge[u][v]; H.insert(e);}

intcount=1;//生成樹(shù)邊計(jì)數(shù)

while(count<NumVertices){H.RemoveMin(e);u=F.Find(e.tail);v=F.Find(e.head);if(u!=v){F.union(u,v);T.Insert(e);count++;}}}

java(偽代碼）publicvoidkruskal(){intedgesAccepted;DisjSets;priorityQueueh;Vertexu,v;SetTypeuset,vset;Edgee;

h=readGraphIntoHeapArray();h.buildHeap();s=newDisjSet(NUM_VERTICES);edgesAccepted=0;while(edgesAccepted<NUM_VERTICES–1){e=h.deleteMin();//Edgee=(u,v)uset=s.find(u);vset=s.find(v);if(uset!=vset){edgesAccepted++;s.union(uset,vset);}}}

算法分析：1)建立e條邊的最小堆。每插入一條邊，執(zhí)行一次

fiterup()算法：log2e

所以，總的建堆時(shí)間為O(elog2e)

檢測(cè)鄰接矩陣O(n2)2)構(gòu)造最小生成樹(shù)時(shí)：

e次出堆操作：每一次出堆，執(zhí)行一次filterdown(),

總時(shí)間為O(elog2e)2e次find操作：O(elog2n)n-1次union操作：O(n)

所以，總的計(jì)算時(shí)間為O(elog2e+elog2n+n2+n)3.Prim算法設(shè)：原圖的頂點(diǎn)集合V(有n個(gè)） 生成樹(shù)的頂點(diǎn)集合U(最后也有n個(gè)），一開(kāi)始為空

TE集合為{

}步驟： 1)U={1}任何起始頂點(diǎn)，TE={} 2)每次生成（選擇）一條邊。這條邊是所有邊(u,v)

中代價(jià)（權(quán)）最小的邊，

uU,vV-U TE=TE+[(u,v)]; U=U+[v] 3)當(dāng)UV用一開(kāi)始的例子：14235665514263561423566551426356123456U V-U5條中找最小1423566551426356132456U V-U8條中找最小14235665514263569條中找最小136245U V-U142356614263568條中找最小136425U V-U114235614263565條中找最小136425U V-U42356142351=15

具體實(shí)現(xiàn)：1)圖采用鄰接矩陣2)設(shè)置了兩個(gè)輔助數(shù)組：改進(jìn)了實(shí)現(xiàn)效率(O(n2)).

最小生成樹(shù)不是唯一的.為什么?算法分析:1*(n-1)+2*(n-2)+……+(n-1)*(n-(n-1))=n-1+2n-4+3n-9+….+(n-1)*n-(n-1)2

=n+2n+3n+…+(n-1)*n-12-22-32-…(n-1)2

=n*(1+2+3+….+(n-1))-(12+22+32+….+(n-1)2)=O(n3)

Lowcost[]:存放生成樹(shù)頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹(shù)外各頂點(diǎn)的邊上的當(dāng)前最小權(quán)值；

nearvex[]:記錄生成樹(shù)頂點(diǎn)集合外各頂點(diǎn)，距離集合內(nèi)那個(gè)頂點(diǎn)最近。從頂點(diǎn)0出發(fā)初始狀態(tài)Lowcost:

nearvex:0123456012345602810-1000000如果為-1則表示已加入生成樹(shù)頂點(diǎn)集合28161214182422102543265011）在Lowcost[]中選擇nearvex[i]-1,且lowcost[i]最小的邊用v標(biāo)記它。，則

選中的權(quán)值最小的邊為（nearvex[v],v),相應(yīng)的權(quán)值為lowcost[v]。例如在上面圖中第一次選中的v=5;則邊（0，5），是選中的權(quán)值最小

的邊，相應(yīng)的權(quán)值為lowcost[5]=10。反復(fù)做以下工作：2）將nearvex[v]改為-1，表示它已加入生成樹(shù)頂點(diǎn)集合。

將邊(nearvex[v],v,lowcost[v])加入生成樹(shù)的邊集合。3）修改。

取lowcost[i]=min{lowcost[i],Edge[v][i]},即用生成樹(shù)頂點(diǎn)集合外各頂

點(diǎn)i到剛加入該集合的新頂點(diǎn)v的距離(Edge[v][i])與原來(lái)它所到生成樹(shù)頂點(diǎn)

集合中頂點(diǎn)的最短距離lowcost[i]做比較，取距離近的，作為這些集合外頂

點(diǎn)到生成樹(shù)頂點(diǎn)集合內(nèi)頂點(diǎn)的最短

距離。

如果生成樹(shù)頂點(diǎn)集合外的頂點(diǎn)i到剛加入該集合新頂點(diǎn)v的距離比原來(lái)它

到生成樹(shù)頂點(diǎn)集合中頂點(diǎn)的最短距離還要近，則修改nearvex[i]:nearvex[i]=v

表示生成樹(shù)外頂點(diǎn)i到生成樹(shù)的內(nèi)頂點(diǎn)v當(dāng)前距離最短。-10000-100123456028100123456nearvexlowcost(0,5,10)1051234560UV-U00512346-10005-10012345602825100123456nearvexlowcost(5,4,25)105UV-U42510541236-1004-1-140123456028222510240123456nearvexlowcost(4,3,22)105UV-U425122

30543126-103-1-1-13012345602812222510180123456nearvexlowcost(3,2,12)105UV-U4251223212U0543216-12-1-1-1-13012345601612222510180123456nearvexlowcost(2,1,16)V-U10542502232121166-1-1-1-1-1-11012345601612222510140123456nearvexlowcost(1,6,14)054321UV-U1054250223212116614Prim（普里姆）算法voidgraph<string,float>::Prim(MinSpanTree&T){intNumVertices=VerticesList.last;float*lowcost=newfloat[NumVertices];int*nearvex=newint[NumVertices];

for(inti=1;i<NumVertices;i++){lowcost[i]=Edge[0][i];nearvex[i]=0;}

nearvex[0]=-1;

MSTEdgeNodee;

for(inti=1;i<NumVertices;i++){1.floatmin=MAXINT;intv=0;2.for(intj=1;j<NumVertices;j++)if(nearvex[j]!=-1&&lowcost[j]<min){v=j;min=lowcost[j];}

//forj,選擇最小的邊

3.

if(v){

e.tail=nearvex[v];e.head=v;e.cost=lowcost[v];

T.Insert(e);nearvex[v]=-1;

for(intj=1;j<NumVertices;j++) if(nearvex[j]!=-1&&Edge[v][j]<lowcost[j]) {lowcost[j]=Edge[v][j];nearvex[j]=v;}}//if}//fori}算法結(jié)構(gòu)為：時(shí)間復(fù)雜度：O(n2)求最小的n修改nnn思考題：這兩種算法分別適合那種情況？9.6最短路徑（shortestpath)三種算法：1)邊上權(quán)值為非負(fù)情況的從一個(gè)結(jié)點(diǎn)到其它各結(jié)點(diǎn)的最短路徑（單源最短路徑）（Dijkstra算法）2)邊上權(quán)值為任意值的單源最短路徑3)邊上權(quán)值為非負(fù)情況的所有頂點(diǎn)之間的最短路徑

設(shè)G=(V,E)是一個(gè)帶權(quán)圖（有向，無(wú)向），如果從頂點(diǎn)v到頂點(diǎn)w的一條路徑為（v,v1,v2,…,w)，其路徑長(zhǎng)度不大于從v到w的所有其它路徑的長(zhǎng)度，則該路徑為從v到w的最短路徑。背景：交通網(wǎng)絡(luò)中，求各城鎮(zhèn)間的最短路徑。1.含非負(fù)權(quán)值的單源最短路徑（Dijkstra)問(wèn)題04123101003050201060V0 V1 10V0V3V2 50V0 V3 30V0V3V2V4 60如果按距離遞增的順序重新排列一下

經(jīng)過(guò) 終止距離V0

V1 10V0 V3 30V0V3 V2

50V0V3V2 V4 60012340103010005001020060001234

思想：按最短路徑長(zhǎng)度遞增的次序產(chǎn)生諸最短路徑。一開(kāi)始，在源點(diǎn)到直接有連線的諸頂點(diǎn)的path中找最小的，去掉該點(diǎn)，然后找從源點(diǎn)到余下點(diǎn)中最短的path(這里可以不是直接連線，可以是經(jīng)過(guò)前面已找到的最短path的頂點(diǎn)）V0SV1V2V3V4V-SV0V1SV2V3V4V-S算法思想：V0V1

V3SV2V4V-SV0V1

V3V2SV4V-S距離值數(shù)組:dist100-100-2600-1-250

0-3-2300-3300-31000-41000-4600-3-2-4900-3-401234路徑path00000320133-1000001234每次放由v0到達(dá)該頂點(diǎn)的前一頂點(diǎn)以下證明一下該算法的正確性，即證明：假設(shè)S是已求得的最短路徑的終點(diǎn)的集合，則可證明下一條最短路徑必然是從v0出發(fā)，中間只經(jīng)過(guò)S中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)vx(vxV-S)的路徑中的一條。用反證法：設(shè)此路徑上存在一個(gè)頂點(diǎn)vpV-S，則說(shuō)明還存在一條終點(diǎn)不在S而長(zhǎng)度比此路徑短的路徑，這是不可能的。V0VlVtVpSV-SDijkstra算法constintNumVertices=6;classgraph{private:intEdge[NumVertices][NumVertices];intdist[NumVertices];intpath[NumVertices];intS[NumVertices];public:voidshortestpath(int,int);intchoose(int);};voidGraph::shortestpath(intn,intv){for(inti=0;i<n;i++){1.dist[i]=Edge[v][i];s[i]=0;2.if(i!=v&&dist[i]<MAXNUM)path[i]=v;elsepath[i]=-1;}

s[v]=1;dist[v]=0;for(i=0;i<n-1;i++){1.floatmin=MAXNUM;intu=v;2.for(intj=0;j<n;j++) if(!s[j]&&dist[j]<min){u=j;min=dist[j];}

3.s[u]=1;4.for(intw=0;w<n;w++)if(!s[w]&&Edge[u][w]<MAXNUM&& dist[u]+Edge[u][w]<dist[w]) {dist[w]=dist[u]+Edge[u][w];path[w]=u;}}//for}

算法分析：O(n2)求最小的n修改nnn2.邊上權(quán)值為任意值的單源最短路徑（貝爾曼—福特）

dijkstra算法在邊上權(quán)值為任意值的圖上是不能正常工作的。為什么？問(wèn)題出在程序的哪里？例子：012-575貝兒曼—福特提出了一個(gè)改進(jìn)的算法：構(gòu)造一個(gè)最短路徑長(zhǎng)度數(shù)組

dist1[u],dist2[u],...distn-1[u]其中:dist1[u]:是從源點(diǎn)v到終點(diǎn)u的只經(jīng)過(guò)一條邊的的最短路徑長(zhǎng)度，

dist1[u]=Edge[v][u]dist2[u]:是從源點(diǎn)v最多經(jīng)過(guò)兩條邊到達(dá)終點(diǎn)u

的最短路徑長(zhǎng)度；v0->v25v0->v17

dist3[u]：是從源點(diǎn)v最多經(jīng)過(guò)不構(gòu)成帶負(fù)長(zhǎng)度邊回路的三條邊 的最短路徑長(zhǎng)度；012-211不允許帶負(fù)權(quán)值的邊組成回路distn-1[u]：是從源點(diǎn)v最多經(jīng)過(guò)不構(gòu)成帶負(fù)長(zhǎng)度邊回路的n-1條 邊的最短路徑長(zhǎng)度；遞推公式：

dist1[u]=Edge[v][u]; distk[u]=min{distk-1[u],min{distk-1[j]+Edge[j][u]}} j=0,1,2,…,n-1...例子：-11253064631-255-1-23distk[0]distk[1]distk[2]distk[3]distk[4]distk[5]distk[6]13200060-110-3-2-130-2-150-2330-3-250-3550-30-420-2-1-450-1-40-5440-3-50-66570-3-5-60-64013500-3-2-1-4450-2-1-4-6voidGraph::BellmanFord(intn,intv){for(inti=0;i<n;i++){dist[i]=Edge[v][i];if(i!=v&&dist[i]<MAXNUM)path[i]=v;elsepath[i]=-1;}

for(intk=2;k<n;k++)for(intu=0;u<n;u++)if(u!=v) for(i=0;i<n;i++)

if(Edge[i][u]<>0&&Edge[i][u]<MAXNUM&& dist[u]>dist[i]+Edge[i][u]) {