數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性

1圖的遍歷與連通性從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，就叫做圖的遍歷

(GraphTraversal)。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。為了避免重復(fù)訪問(wèn)，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問(wèn)過(guò)的輔助數(shù)組visited[]。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第2頁(yè)。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第3頁(yè)。4DFS

在訪問(wèn)圖中某一起始頂點(diǎn)v

后,由

v

出發(fā),訪問(wèn)它的任一鄰接頂點(diǎn)

w1;再?gòu)膚1出發(fā),訪問(wèn)與w1鄰接但還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)w2;然后再?gòu)膚2出發(fā),進(jìn)行類似的訪問(wèn),…如此進(jìn)行下去,直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)u為止。接著,退回一步,退到前一次剛訪問(wèn)過(guò)的頂點(diǎn),看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。如果有,則訪問(wèn)此頂點(diǎn),之后再?gòu)拇隧旤c(diǎn)出發(fā),進(jìn)行與前述類似的訪問(wèn);如果沒(méi)有,就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程,直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第4頁(yè)。5圖的深度優(yōu)先搜索算法template<classT,classE>voidDFS(Graph<T,E>&G,constT&v){//從頂點(diǎn)v出發(fā)對(duì)圖G進(jìn)行深度優(yōu)先遍歷的主過(guò)程

inti,loc,n=G.NumberOfVertices();//頂點(diǎn)個(gè)數(shù)

bool*visited=newbool[n];//創(chuàng)建輔助數(shù)組

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

[i]=false;

//輔助數(shù)組visited初始化

loc=G.getVertexPos(v);

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

delete[]visited;//釋放visited}數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第5頁(yè)。6template<classT,classE>voidDFS(Graph<T,E>&G,intv,boolvisited[]){cout<<G.getValue(v)<<'';//訪問(wèn)頂點(diǎn)v

visited[v]=true; //作訪問(wèn)標(biāo)記

intw=G.getFirstNeighbor(v);//第一個(gè)鄰接頂點(diǎn)

while(w>=0){ //若鄰接頂點(diǎn)w存在

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

//若w未訪問(wèn)過(guò),遞歸訪問(wèn)頂點(diǎn)w

w=G.getNextNeighbor(v,w);//下一個(gè)鄰接頂點(diǎn)

}}數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第6頁(yè)。7廣度優(yōu)先搜索BFS

(BreadthFirstSearch)廣度優(yōu)先搜索的示例廣度優(yōu)先搜索過(guò)程廣度優(yōu)先生成樹(shù)ACDEGBFIHACDEGBFH123456789123456789I數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第7頁(yè)。8BFS在訪問(wèn)了起始頂點(diǎn)v之后,由v出發(fā),依次訪問(wèn)v的各個(gè)未被訪問(wèn)過(guò)的鄰接頂點(diǎn)w1,w2,…,wt,然后再順序訪問(wèn)w1,w2,…,wt的所有還未被訪問(wèn)過(guò)的鄰接頂點(diǎn)。再?gòu)倪@些訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，再訪問(wèn)它們的所有還未被訪問(wèn)過(guò)的鄰接頂點(diǎn)，…如此做下去，直到圖中所有頂點(diǎn)都被訪問(wèn)到為止。廣度優(yōu)先搜索是一種分層的搜索過(guò)程,每向前走一步可能訪問(wèn)一批頂點(diǎn),不像深度優(yōu)先搜索那樣有往回退的情況。因此,廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第8頁(yè)。9為了實(shí)現(xiàn)逐層訪問(wèn),算法中使用了一個(gè)隊(duì)列,以記憶正在訪問(wèn)的這一層和上一層的頂點(diǎn),以便于向下一層訪問(wèn)。為避免重復(fù)訪問(wèn),需要一個(gè)輔助數(shù)組visited[]，給被訪問(wèn)過(guò)的頂點(diǎn)加標(biāo)記。template<classT,classE>voidBFS(Graph<T,E>&G,constT&v){inti,w,n=G.NumberOfVertices();

//圖中頂點(diǎn)個(gè)數(shù)圖的廣度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第9頁(yè)。10

bool*visited=newbool[n];

for(i=0;i<n;i++)visited[i]=false;intloc=G.getVertexPos(v); //取頂點(diǎn)號(hào)

cout<<G.getValue(loc)<<'';//訪問(wèn)頂點(diǎn)v

visited[loc]=true; //做已訪問(wèn)標(biāo)記

Queue<int>Q;Q.EnQueue(loc);

//頂點(diǎn)進(jìn)隊(duì)列,實(shí)現(xiàn)分層訪問(wèn)

while(!Q.IsEmpty()){//循環(huán),訪問(wèn)所有結(jié)點(diǎn)

Q.DeQueue(loc);

w=G.getFirstNeighbor(loc);//第一個(gè)鄰接頂點(diǎn)

while(w>=0){ //若鄰接頂點(diǎn)w存在

if(!visited[w]){ //若未訪問(wèn)過(guò)數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第10頁(yè)。11cout<<G.getValue(w)<<'';//訪問(wèn)

visited[w]=true;

Q.EnQueue(w); //頂點(diǎn)w進(jìn)隊(duì)列

}

w=G.getNextNeighbor(loc,w);

//找頂點(diǎn)loc的下一個(gè)鄰接頂點(diǎn)

}} //外層循環(huán)，判隊(duì)列空否

delete[]visited;}數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第11頁(yè)。12連通分量(Connectedcomponent)當(dāng)無(wú)向圖為非連通圖時(shí)，從圖中某一頂點(diǎn)出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn)，只能訪問(wèn)到該頂點(diǎn)所在最大連通子圖（連通分量）的所有頂點(diǎn)。若從無(wú)向圖每一連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷,可求得無(wú)向圖的所有連通分量。例如，對(duì)于非連通的無(wú)向圖，所有連通分量的生成樹(shù)組成了非連通圖的生成森林。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第12頁(yè)。13ACDEBFGOIHJNMLK非連通無(wú)向圖AHKCDEIBFOGJNML非連通圖的連通分量數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第13頁(yè)。14確定連通分量的算法template<classT,classE>voidComponents(Graph<T,E>&G){//通過(guò)DFS，找出無(wú)向圖的所有連通分量

inti,n=G.NumberOfVertices();//圖中頂點(diǎn)個(gè)數(shù)

bool*visited=newbool[n]; //訪問(wèn)標(biāo)記數(shù)組

for(i=0;i<n;i++)visited[i]=false;for(i=0;i<n;i++)

//掃描所有頂點(diǎn)

if(!visited[i]){ //若沒(méi)有訪問(wèn)過(guò)

DFS(G,i,visited); //訪問(wèn)

OutputNewComponent();//輸出連通分量

} 數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第14頁(yè)。15delete[]visited;}例：以深度優(yōu)先搜索方法從頂點(diǎn)出發(fā)遍歷圖,建立深度優(yōu)先生成森林。A有向圖深度優(yōu)先生成森林ABCDEFGABDECFG數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第15頁(yè)。16最小生成樹(shù)

(minimumcostspanningtree)使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)。按照生成樹(shù)的定義，n

個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹(shù)有n

個(gè)頂點(diǎn)、n-1條邊。構(gòu)造最小生成樹(shù)：假設(shè)有一個(gè)網(wǎng)絡(luò)，用以表示n

個(gè)城市之間架設(shè)通信線路，邊上的權(quán)值代表架設(shè)通信線路的成本。如何架設(shè)才能使線路架設(shè)的成本達(dá)到最??？數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第16頁(yè)。17構(gòu)造最小生成樹(shù)的準(zhǔn)則必須使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n

個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達(dá)到最小。北京天津南京上海廣州西安成都昆明武漢34764158312419253822221931394450數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第17頁(yè)。18北京天津南京上海廣州西安成都昆明武漢76241922221931北京天津南京上海廣州西安成都昆明武漢34764158312419253822221931394450數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第18頁(yè)。19克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的基本思想： 設(shè)有一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn),沒(méi)有邊的非連通圖T={V,},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。當(dāng)在E中選到一條具有最小權(quán)值的邊時(shí),若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點(diǎn)在同一個(gè)連通分量上為止。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第19頁(yè)。20Kruskal算法的偽代碼描述

T=; //T是最小生成樹(shù)的邊集合

//E是帶權(quán)無(wú)向圖的邊集合

while(T包含的邊少于n-1&&E不空){

從E中選一條具有最小代價(jià)的邊(v,w);

從E中刪去(v,w);

如果(v,w)加到T中后不會(huì)產(chǎn)生回路,則將

(v,w)加入T;否則放棄(v,w); } if(T中包含的邊少于n-1條)cout<<"不是最小生成樹(shù)"<<endl;數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第20頁(yè)。21算法的框架利用最小堆(MinHeap)和并查集(DisjointSets)來(lái)實(shí)現(xiàn)克魯斯卡爾算法。首先,利用最小堆來(lái)存放E中的所有的邊,堆中每個(gè)結(jié)點(diǎn)的格式為在構(gòu)造最小生成樹(shù)過(guò)程中,利用并查集的運(yùn)算檢查依附一條邊的兩頂點(diǎn)tail、head

是否在同一連通分量(即并查集的同一個(gè)子集合)上,是則舍去這條邊；否則將此邊加入T,同時(shí)將這兩個(gè)頂點(diǎn)放在同一個(gè)連通分量上。邊的兩個(gè)頂點(diǎn)位置邊的權(quán)值

tailheadcost

數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第21頁(yè)。22隨著各邊逐步加入到最小生成樹(shù)的邊集合中,各連通分量也在逐步合并,直到形成一個(gè)連通分量為止。10504613228102514242216181250461325046132原圖(a)(b)構(gòu)造最小生成樹(shù)的過(guò)程數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第22頁(yè)。231012504613228102514242216181250461325046132101412原圖(c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第23頁(yè)。24在求解最小生成樹(shù)時(shí)，可以用鄰接矩陣存儲(chǔ)圖，也可以用鄰接表存儲(chǔ)圖。算法中使用圖的抽象基類的操作，無(wú)需考慮圖及其操作的具體實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第24頁(yè)。25出堆順序

(0,5,10)

選中

(2,3,12)

選中

(1,6,14)

選中

(1,2,16)

選中(3,6,18)舍棄

(3,4,22)

選中(4,6,24)舍棄(4,5,25)

選中并查集原圖-2-2-2-2-1-1-1-1-1-1-1-1-1-1-1-102-1-1-10-2200000123456-21-11-2-1-421-2-51211-711211F5046132281025142422161812(0,5,10)(2,3,12)(1,6,14)(1,2,16)(3,4,22)(4,5,25)數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第25頁(yè)。26普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡(luò)N={V,E}中的某一頂點(diǎn)u0

出發(fā),選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v),將其頂點(diǎn)加入到生成樹(shù)頂點(diǎn)集合U中。 以后每一步從一個(gè)頂點(diǎn)在集合U中,而另一個(gè)頂點(diǎn)不在集合U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合U中。如此繼續(xù)下去,直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹(shù)頂點(diǎn)集合U中為止。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第26頁(yè)。27普里姆(Prim)的偽代碼描述

選定構(gòu)造最小生成樹(shù)的出發(fā)頂點(diǎn)u0;

Vmst

={u0}，Emst=; while(Vmst包含的頂點(diǎn)少于n&&E不空){

從E中選一條邊(u,v),

uVmst∩vV-Vmst,且具有最小代價(jià)(cost);

令Vmst

=Vmst∪{v},Emst=Emst∪{(u,v)};

將新選出的邊從E中剔除：E=E-{(u,v)}; } if(Vmst包含的頂點(diǎn)少于n)cout<<"不是最小生成樹(shù)"<<endl;數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第27頁(yè)。28252510504613228102514242216185046132504613210原圖(a)

(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第28頁(yè)。29例子50461322810251424221618125046132281025142422161812H={(0,5,10),(0,1,28)}ed=(0,5,10)Vmst={t,f,f,f,f,f,f}Vmst={t,f,f,f,f,t,f}數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第29頁(yè)。305046132281025142422161812H={(5,4,25),(0,1,28)}ed=(5,4,25)Vmst={t,f,f,f,f,t,f}Vmst={t,f,f,f,t,

t,f}5046132281025142422161812H={(4,3,22),(4,6,24),(0,1,28)}ed=(4,3,22)Vmst={t,f,f,f,t,

t,f}Vmst={t,f,f,t,

t,

t,f}數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第30頁(yè)。315046132281025142422161812H={(3,2,12),(3,6,18),(4,6,24),(0,1,28)}ed=(3,2,12)Vmst={t,f,f,t,

t,

t,f}Vmst={t,f,t,

t,

t,

t,f}5046132281025142422161812H={(2,1,16),(3,6,18),(4,6,24),(0,1,28)}ed=(2,1,16)Vmst={t,f,t,

t,

t,

t,f}Vmst={t,

t,

t,

t,

t,

t,f}數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第31頁(yè)。325046132281025142422161812H={(1,6,14),(3,6,18),(4,6,24),(0,1,28)}ed=(1,6,14)Vmst={t,t,

t,

t,

t,

t,f}Vmst={t,

t,

t,

t,

t,

t,

t}最小生成樹(shù)中邊集合里存入的各條邊為：

(0,5,10),(5,4,25),(4,3,22), (3,2,12),(2,1,16),(1,6,14)數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第32頁(yè)。33Prim算法適用于邊稠密的網(wǎng)絡(luò)。Kruskal算法不僅適合于邊稠密的情形，也適合于邊稀疏的情形。注意：當(dāng)各邊有相同權(quán)值時(shí)，由于選擇的隨意性，產(chǎn)生的生成樹(shù)可能不唯一。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第33頁(yè)。34最短路徑(ShortestPath)最短路徑問(wèn)題：在圖中，從某一頂點(diǎn)（稱為源點(diǎn)）到另一頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。問(wèn)題解法

邊上權(quán)值非負(fù)情形的單源最短路徑問(wèn)題

—Dijkstra算法

(僅講此算法)

邊上權(quán)值為任意值的單源最短路徑問(wèn)題

—Bellman和Ford算法

(不講)所有頂點(diǎn)之間的最短路徑

—Floyd算法

(不講)數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第34頁(yè)。35邊上權(quán)值非負(fù)情形的

單源最短路徑問(wèn)題問(wèn)題的提法：給定一個(gè)帶權(quán)有向圖D與源點(diǎn)v，求從v到D中其他頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑,Dijkstra提出按路徑長(zhǎng)度的遞增次序,逐步產(chǎn)生最短路徑的算法。首先求出長(zhǎng)度最短的一條最短路徑，再參照它求出長(zhǎng)度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第35頁(yè)。艾茲格·W·迪杰斯特拉EdsgerWybeDijkstra，生于1930年5月11日，卒于2002年8月6日，荷蘭人。計(jì)算機(jī)科學(xué)家，畢業(yè)并就職于荷蘭Leiden大學(xué)，早年鉆研物理及數(shù)學(xué)，而后轉(zhuǎn)為計(jì)算科學(xué)。曾在1972年獲得過(guò)素有計(jì)算機(jī)科學(xué)界的諾貝爾獎(jiǎng)之稱的圖靈獎(jiǎng)。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第36頁(yè)。37Dijkstra逐步求解的過(guò)程源點(diǎn)終點(diǎn)最短路徑路徑長(zhǎng)度v0

v1

v2

v3

v4

10432101003050206010(v0,v1)—(v0,v3)(v0,v4)1030100,60,90(v0,v1,v2)(v0,v3,v4)(v0,v3,v2),50,60(v0,v3,v2,v4)數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第37頁(yè)。38引入輔助數(shù)組dist。它的每一個(gè)分量dist[i]表示當(dāng)前找到的從源點(diǎn)v0到終點(diǎn)

vi的最短路徑的長(zhǎng)度。初始狀態(tài)：若從v0到頂點(diǎn)vi有邊,則dist[i]為該邊的權(quán)值；若從v0到頂點(diǎn)vi無(wú)邊,則dist[i]為。假設(shè)S是已求得的最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑必然是從v0出發(fā)，中間只經(jīng)過(guò)S中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)vx(vxV-S)的路徑中的一條。每次求得一條最短路徑后,其終點(diǎn)vk加入集合S，然后對(duì)所有的vi

V-S，修改其dist[i]值。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第38頁(yè)。39Dijkstra算法可描述如下：①

初始化：S{v0};

dist[j]Edge[0][j],

j=1,2,…,n-1;//n為圖中頂點(diǎn)個(gè)數(shù)②

求出最短路徑的長(zhǎng)度：

dist[k]min{dist[i]},iV-S;

SS∪{k};③

修改：

dist[i]min{dist[i],dist[k]+Edge[k][i]},

對(duì)于每一個(gè)

iV-S

;④

判斷：若

S=V,則算法結(jié)束，否則轉(zhuǎn)②。數(shù)據(jù)結(jié)構(gòu)與算法-圖的遍歷與連通性全文共43頁(yè)，當(dāng)前為第39頁(yè)。40計(jì)算從單個(gè)頂點(diǎn)到其他各頂點(diǎn)

最短路徑的算法voidShortestPath(Graph<T,E>&G,Tv,

Edist[],intpath[]){//Graph是一個(gè)帶權(quán)有向圖。dist[j],0≤j<n,是當(dāng)前//求到的從頂點(diǎn)v到頂點(diǎn)j的最短路徑長(zhǎng)度,path[j],//0≤j<n,存放求到的最短路徑。

intn=G.NumberOfVertices();bool*S=newbool[n]; //最短路徑頂點(diǎn)集

inti,j,k;Ew,min;for(