數(shù)據(jù)結(jié)構(gòu)之--圖的基本運(yùn)算方法

1、數(shù)據(jù)結(jié)構(gòu)A：實(shí)驗(yàn)-圖的基本運(yùn)算方法一、 實(shí)驗(yàn)?zāi)康暮鸵?.掌握在圖的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的基本運(yùn)算的算法。學(xué)習(xí)使用圖算法解決應(yīng)用問(wèn)題的方法。(1). 驗(yàn)證教材中關(guān)于在鄰接矩陣和鄰接表兩種不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本運(yùn)算的算法（2）在鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的深度和寬度優(yōu)先遍歷算法。（3）在兩種儲(chǔ)存結(jié)構(gòu)上面分別實(shí)現(xiàn)Dijkstra、prim、Floyd算法2. 飛機(jī)最少換乘次數(shù)問(wèn)題。二、實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)PC計(jì)算機(jī)，Windows 7操作系統(tǒng)，IDE: Codeblocks 16.01編譯器: GNU GCC Compiler、實(shí)驗(yàn)原理及內(nèi)容程序一：鄰接矩陣表示的圖的運(yùn)算本程序

2、包含鄰接矩陣表示的圖的基本運(yùn)算，包括插入邊，移除邊，判斷邊是否存在，深度優(yōu)先遍歷DFS，寬度優(yōu)先遍歷BFS，單源最短路Dijkstra算法，多源最短路Floyd算法，以及最小生成樹prim算法。程序定義了一個(gè)圖類包含三個(gè)數(shù)據(jù)成員，分別是指向二維數(shù)據(jù)的指針T *a,記錄頂點(diǎn)數(shù)的n和記錄邊數(shù)量的e。構(gòu)造函數(shù)負(fù)責(zé)申請(qǐng)二維數(shù)組動(dòng)態(tài)空間，析構(gòu)函數(shù)負(fù)責(zé)釋放空間。類的聲明：templateclass MGraphpublic:MGraph(int mSize);MGraph();bool Insert(int u,int v,int w);bool Remove(int u,int v);bool Exis

3、t(int u,int v)const; void DFS();void BFS();void Dijkstra(int v,T *d,int *path);void Floyd(int dSize,int pathSize);void prim(int k,int *nearest,T* lowcost);protected: int Choose(int *d,bool *s); void DFS(int v,bool *visited);void BFS(int v,bool *visited);T *a;int n,e;（1） 深度優(yōu)先遍歷DFS算法圖的深度優(yōu)先遍歷重載了兩個(gè)DFS函數(shù)

4、，分別是面向用戶的DFS()和私有成員DFS(int v,bool *visited)。面向用戶的不帶參數(shù)版本，首先定義一個(gè)一位數(shù)組visited來(lái)標(biāo)記當(dāng)前已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn)，并初始化為false。為了防止圖不是一個(gè)連通圖，在外層DFS中，要通過(guò)一個(gè)循環(huán)一遍一遍的調(diào)用帶參數(shù)版本的DFS(i,visited)，如果圖是一個(gè)連通圖，那么在第一次調(diào)用之后，所以的visited都變成true，后續(xù)就不再調(diào)用，如果圖不是一個(gè)連通圖，那么還要多次調(diào)用帶參數(shù)版本DFS（i,visited）通過(guò)這個(gè)方法，也可以用來(lái)判斷圖是不是一個(gè)連通圖。代碼：templatevoid MGraph:DFS()int i;boo

5、l *visited=new booln;for(i=0;in;i+)visitedi=false;for(i=0;in;i+) if(visitedi=false) DFS(i,visited); coutendl;delete visited;templatevoid MGraph:DFS(int v,bool *visited)visitedv=true;printf( %d ,v);for(int u=0;un;u+) if(avu!=INF & visitedu= false) DFS(u,visited); 算法分析：深度優(yōu)先遍歷，沒(méi)嵌套調(diào)用一次，實(shí)際是對(duì)一個(gè)頂點(diǎn)v查看所有的鄰接點(diǎn)

6、，設(shè)圖有n個(gè)頂點(diǎn)，時(shí)間復(fù)雜度是O(n2)空間復(fù)雜度：由于要定義一個(gè)臨時(shí)數(shù)組標(biāo)記訪問(wèn)過(guò)的頂點(diǎn)，所以空間復(fù)雜度是O(n)。（2） 寬度優(yōu)先遍歷BFS圖的寬度優(yōu)先遍歷BFS重載了兩個(gè)版本，一個(gè)是面向用戶的不帶參數(shù)版本，一個(gè)是帶參數(shù)版本。不帶參數(shù)版本的作用主要是為了防止圖不是一個(gè)連通圖，導(dǎo)致不能訪問(wèn)所有頂點(diǎn)，所有通過(guò)一個(gè)循環(huán)來(lái)一遍一遍調(diào)用帶參數(shù)版本BFS，與DFS類似，如果圖是一個(gè)連通圖，那么第一次調(diào)用就能訪問(wèn)所有頂點(diǎn)，如果不是連通圖，得多次調(diào)用，通過(guò)此方法也可以判斷是不是連通圖。帶參數(shù)版本BFS通過(guò)隊(duì)列來(lái)實(shí)現(xiàn)寬度優(yōu)先遍歷，首先將第一個(gè)頂點(diǎn)加入隊(duì)列，然后，每次從隊(duì)列取出一個(gè)頂點(diǎn)，并將與之相鄰并且還沒(méi)有

7、訪問(wèn)過(guò)的頂點(diǎn)加入到隊(duì)列，直到隊(duì)列為空停止。為了代碼簡(jiǎn)潔，隊(duì)列使用了STL庫(kù)的queue頭文件。代碼：templatevoid MGraph:BFS()int i;bool *visited=new booln;for(i=0;in;i+)visitedi=false;for(i=0;in;i+) if(visitedi=false) BFS(i,visited); coutendl;delete visited;templatevoid MGraph:BFS(int v,bool *visited)queue Q;visitedv=true;Q.push(v);while(!Q.empty()

8、 v=Q.front(); Q.pop(); coutv ; for(int i=0;in;i+) if(visitedi=false&avi!=INF) visitedi=true; Q.push(i); 算法分析：每個(gè)頂點(diǎn)只進(jìn)入一次隊(duì)列，對(duì)于每個(gè)從隊(duì)列取走的點(diǎn)，都查看其所有的鄰接點(diǎn)，設(shè)頂點(diǎn)數(shù)是n，邊數(shù)是e，時(shí)間復(fù)雜度是O(n2)空間復(fù)雜度：同樣需要定義臨時(shí)數(shù)組標(biāo)記訪問(wèn)過(guò)的頂點(diǎn)，隊(duì)列中元素個(gè)數(shù)不超過(guò)n個(gè)，所以空間復(fù)雜度是O(n)。（3） prim最小生成樹算法prim算法的整體思路為，首先加入一個(gè)頂點(diǎn)到生成樹中，然后，每次加入一條代價(jià)最小的邊，邊的一個(gè)頂點(diǎn)已被加入生成樹，一個(gè)頂點(diǎn)未被加入生成

9、樹，然后標(biāo)記這個(gè)邊的頂點(diǎn)，表示將這個(gè)頂點(diǎn)也加入，加入之后更新其lowcost數(shù)組，然后繼續(xù)選邊，直到所有頂點(diǎn)都被標(biāo)記。定義三個(gè)臨時(shí)數(shù)組，mark數(shù)組來(lái)實(shí)現(xiàn)上述標(biāo)記，lowcostj記錄與頂點(diǎn)j相接的邊中最小的權(quán)值(邊的另一個(gè)頂點(diǎn)未被標(biāo)記)，nearestj表示頂點(diǎn)j上述最小權(quán)值邊的另一個(gè)頂點(diǎn)。主函數(shù)打印最小生成樹的邊集(nearestj,j,lowcostj)代碼：template void MGraph:prim(int k,int *nearest,T* lowcost) bool *mark=new booln; if(kn-1) printf(out of boundsn); retu

10、rn; for(int i=0;in;i+) nearesti=-1; lowcosti=INF; marki=false; lowcostk=0; nearestk=k; markk=true; int cnt=n-1; while(cnt-) for(int i=0;iaki) lowcosti=aki; nearesti=k; T minn=INF; for(int j=0;jn;j+) if(!markj)&(lowcostjminn) minn=lowcostj; k=j; markk=true; 算法分析：由于要加入n個(gè)頂點(diǎn)，每次加入都要找最小邊和更新lowcost，所以時(shí)間復(fù)雜度

11、是O(n2)?？臻g復(fù)雜度：定義兩個(gè)一維數(shù)組，空間復(fù)雜度是O(n)（4） Dijkstra單源最短路算法Dijkstra的整體思路是，首先加入起點(diǎn)到s集合中，然后更新與之相鄰的頂點(diǎn)的數(shù)組d的值，然后每次選擇不在s中并且dj最小的頂點(diǎn)，將頂點(diǎn)加入到s集合，并更新與這個(gè)頂點(diǎn)相鄰的頂點(diǎn)dj的值，然后再選擇不在s中并且dj最小的頂點(diǎn)，如此重復(fù)n-1次，將所有頂點(diǎn)都加入s中。利用s數(shù)組來(lái)標(biāo)記是不是在集合s中，調(diào)用choose函數(shù)來(lái)選擇不在s中且d最小的頂點(diǎn)，每次更新d的時(shí)候也要更新path數(shù)組來(lái)記錄路徑。代碼：templatevoid MGraph:Dijkstra(int v,T *d,int *pat

12、h)int i,k,w;if(vn-1)coutout of bounds!endl;return;bool *s=new booln;for(i=0;in;i+)si=false;di=avi;if(i!=v&diINF)pathi=v;else pathi=-1;sv=true;dv=0;for(i=1;in;i+)k=Choose(d,s); sk=true; for(w=0;wn;w+) if(!sw&dk+akwdw) dw=dk+akw; pathw=k; 算法復(fù)雜度：要加入n-1個(gè)頂點(diǎn)，每次加入都要調(diào)用choose函數(shù)，choose函數(shù)時(shí)間復(fù)雜度是O(n)，綜上，時(shí)間復(fù)雜度是O(

13、n2)?？臻g復(fù)雜度：定義path數(shù)組，d數(shù)組，和s數(shù)組，都是一維數(shù)組，空間復(fù)雜度是O(n)。（5） Floyd多源最短路算法Floyd算法又稱為插點(diǎn)法，是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法其狀態(tài)轉(zhuǎn)移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,j；mapi,j表示i到j(luò)的最短距離，K是窮舉i,j的斷點(diǎn)，mapn,n初值應(yīng)該為0，或者按照題目意思來(lái)做。算法過(guò)程為，首先，從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)為無(wú)窮大。然后，對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到

14、 v 比已知的路徑更短。如果存在則更新它。代碼：templatevoid MGraph:Floyd(int dSize,int pathSize)int i,j,k; for(int i=0;in;i+) for(int j=0;jn;j+) dij=aij; if(i!=j&aijINF) pathij=i; else pathij=-1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jn;j+) if(dik+dkjdij) dij=dik+dkj; pathij=pathkj; 算法分析：時(shí)間復(fù)雜度是O(n3)，用二維數(shù)組保存結(jié)果，空間復(fù)雜度是O(n2)。

15、程序測(cè)試：輸入課本179頁(yè)下方圖結(jié)果正確程序測(cè)試: 176頁(yè)上方圖結(jié)果正確。程序二：鄰接表表示的圖的基本運(yùn)算本程序包含鄰接表表示的圖的基本運(yùn)算，包括插入邊，移除邊，判斷邊是否存在，深度優(yōu)先遍歷DFS，寬度優(yōu)先遍歷BFS，單源最短路Dijkstra算法，多源最短路Floyd算法，以及最小生成樹prim算法。程序定義了一個(gè)圖類包含三個(gè)數(shù)據(jù)成員，分別是指向vector的數(shù)組的指針,記錄頂點(diǎn)數(shù)的n和記錄邊數(shù)量的e。構(gòu)造函數(shù)負(fù)責(zé)申請(qǐng)n個(gè)vector數(shù)組， Mi為一個(gè)vector數(shù)組，存放頂點(diǎn)i相接的邊，相當(dāng)于鏈表，為了代碼的簡(jiǎn)潔，程序用STL庫(kù)的vector代替了鏈表。析構(gòu)函數(shù)負(fù)責(zé)釋放空間。Vector

16、的元素類型為定義的結(jié)構(gòu)體表示的邊，邊上有兩個(gè)屬性，分別是邊的另一側(cè)的頂點(diǎn)值，和邊的權(quán)值。表示邊的結(jié)構(gòu)體：struct edge int to; int cost; edge(int x,int y) to=x; cost=y; ;表示邊的圖例說(shuō)明：類的聲明：templateclass LGraphprivate: vector *M; int n; int e; void DFS(int u,bool *vis); void BFS(int v,bool *vis);public: LGraph(int mSize); LGraph(); bool Insert(int u,int v,int

17、 w); bool Exist(int u,int v); bool Remove(int u,int v); void Dijkstra(int v,T *d,int *path); void prim(int k,int *nearest,T* lowcost); void Floyd(int dSize,int pathSize); void DFS(); void BFS();類的圖例說(shuō)明:（1） 構(gòu)造函數(shù)負(fù)責(zé)申請(qǐng)n個(gè)vector數(shù)組，用來(lái)存放鄰接邊代碼：templateLGraph:LGraph(int mSize) M=new vectormSize; n=mSize; e=0;（

18、2） 插入函數(shù)InsertInsert函數(shù)首先判斷插入的邊是否存在，如果存在返回false，不存在則插入邊，插入的時(shí)候首先構(gòu)造一個(gè)邊，然后調(diào)用vector的push_back函數(shù)插入。代碼：templatebool LGraph:Insert(int u,int v,int w) int i; if(u0|un-1|un-1) return false; for(i=0;iMu.size();i+) if(Mui.to=v) return false; edge tmp(v,w); Mu.push_back(tmp); e+; return true;（3） Remove移除邊移除邊首先要判斷

19、參數(shù)合理性，然后搜索這條邊是否存在，如果存在移除，不存在返回false代碼：templatebool LGraph:Remove(int u,int v) int i; if(u0|vn-1|vn-1) return false; for(i=0;iMu.size();i+) if(Mui.to=v) Mu.erase(Mu.begin()+i); return true; return false;（4） 深度優(yōu)先遍歷DFS與上面鄰接矩陣的DFS類似，鄰接表由于直接記錄與當(dāng)前頂點(diǎn)相鄰的頂點(diǎn)，所有循環(huán)的時(shí)候不需要遍歷所有頂點(diǎn)判斷INF，循環(huán)的時(shí)間復(fù)雜度更加低。思路與鄰接矩陣類似，但是由于鄰接表

20、在插入的時(shí)候沒(méi)有考慮順序，導(dǎo)致每個(gè)頂點(diǎn)后面接的頂點(diǎn)不一定按照從小到大的順序排列，而鄰接矩陣循環(huán)是從0到n-1按照從小到大的順序來(lái)的，所以為了保持和鄰接矩陣的一致性，在DFS的時(shí)候第一步首先將每個(gè)vector進(jìn)行排序，將vector中元素按照邊的另一頭頂點(diǎn)從小到大的順序排列，調(diào)用STL中的頭文件中的sort傳入函數(shù)參數(shù)cmpcmp定義：int cmp(edge a,edge b) return a.tob.to;DFS代碼：templatevoid LGraph:DFS() for(int i=0;in;i+) sort(Mi.begin(),Mi.end(),cmp); int i; bool

21、 *vis=new booln+1; for(i=0;in;i+) visi=false; for(i=0;in;i+) if(visi=false) DFS(i,vis); delete vis; coutendl;templatevoid LGraph:DFS(int v,bool *vis) visv=true; printf(%d ,v); int i; for(i=0;iMv.size();i+) int t=Mvi.to; if(vist=false) DFS(t,vis); 算法分析：深度優(yōu)先遍歷，沒(méi)嵌套調(diào)用一次，實(shí)際是對(duì)一個(gè)頂點(diǎn)v查看所有的鄰接點(diǎn)，設(shè)圖有n個(gè)頂點(diǎn)，時(shí)間復(fù)雜度是O

22、(n+e)?？臻g復(fù)雜度是O(n)。（5） 寬度優(yōu)先遍歷BFSBFS與鄰接矩陣類似，重載了兩個(gè)版本，一個(gè)是面向用戶的不帶參數(shù)版本，一個(gè)是帶參數(shù)版本。不帶參數(shù)版本的作用主要是為了防止圖不是一個(gè)連通圖，導(dǎo)致不能訪問(wèn)所有頂點(diǎn)，所有通過(guò)一個(gè)循環(huán)來(lái)一遍一遍調(diào)用帶參數(shù)版本BFS，與DFS類似，如果圖是一個(gè)連通圖，那么第一次調(diào)用就能訪問(wèn)所有頂點(diǎn)，如果不是連通圖，得多次調(diào)用，通過(guò)此方法也可以判斷是不是連通圖。帶參數(shù)版本BFS通過(guò)隊(duì)列來(lái)實(shí)現(xiàn)寬度優(yōu)先遍歷，首先將第一個(gè)頂點(diǎn)加入隊(duì)列，然后，每次從隊(duì)列取出一個(gè)頂點(diǎn)，并將與之相鄰并且還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)加入到隊(duì)列，直到隊(duì)列為空停止。為了代碼簡(jiǎn)潔，隊(duì)列使用了STL庫(kù)的queu

23、e頭文件。代碼：templatevoid LGraph:BFS() int i; bool *vi=new booln; for(i=0;in;i+) vii=false; for(i=0;in;i+) if(vii=false) BFS(i,vi); coutendl; delete vi;templatevoid LGraph:BFS(int v,bool *vi) int i; viv=true; queue Q; Q.push(v); while(!Q.empty() v=Q.front(); printf(%d ,v); Q.pop(); for(i=0;iMv.size();i+)

24、 int t=Mvi.to; if(vit=false) Q.push(t); vit=true; 算法分析：每個(gè)頂點(diǎn)只進(jìn)入一次隊(duì)列，對(duì)于每個(gè)從隊(duì)列取走的點(diǎn)，都查看其所有的鄰接點(diǎn)，設(shè)頂點(diǎn)數(shù)是n，邊數(shù)是e，時(shí)間復(fù)雜度是O(n+e)?？臻g復(fù)雜度：隊(duì)列中元素個(gè)數(shù)不超過(guò)n個(gè)，同時(shí)需要定義數(shù)組標(biāo)記已訪問(wèn)過(guò)的頂點(diǎn)，所以空間復(fù)雜度是O(n)。（6） prim最小生成樹算法鄰接表的prim算法與鄰接矩陣類似，只是在循環(huán)的時(shí)候稍有不同，要注意鄰接點(diǎn)是edge中的to元素。算法的整體思路為，首先加入一個(gè)頂點(diǎn)到生成樹中，然后，每次加入一條代價(jià)最小的邊，邊的一個(gè)頂點(diǎn)已被加入生成樹，一個(gè)頂點(diǎn)未被加入生成樹，然后標(biāo)記這個(gè)

25、邊的頂點(diǎn)，表示將這個(gè)頂點(diǎn)也加入，加入之后更新其lowcost數(shù)組，然后繼續(xù)選邊，直到所有頂點(diǎn)都被標(biāo)記。定義三個(gè)臨時(shí)數(shù)組，mark數(shù)組來(lái)實(shí)現(xiàn)上述標(biāo)記，lowcostj記錄與頂點(diǎn)j相接的邊中最小的權(quán)值(邊的另一個(gè)頂點(diǎn)未被標(biāo)記)，nearestj表示頂點(diǎn)j上述最小權(quán)值邊的另一個(gè)頂點(diǎn)。主函數(shù)打印最小生成樹的邊集(nearestj,j,lowcostj)代碼：templatevoid LGraph:prim(int k,int *nearest,T* lowcost) bool *mark=new booln+1; for(int i=0;in;i+) nearesti=-1; marki=false;

26、 lowcosti=INF; markk=true; lowcostk=0; nearestk=k; for(int i=1;in;i+) for(int j=0;jMkj.cost&!(markt) lowcostt=Mkj.cost; nearestt=k; int min=INF; for(int j=0;jn;j+) if(!markj & lowcostjmin) min=lowcostj; k=j; markk=true; delete mark;算法分析：由于要加入n個(gè)頂點(diǎn)，每次加入都要找最小邊和更新lowcost，所以時(shí)間復(fù)雜度是O(n2)?？臻g復(fù)雜度：定義兩個(gè)一維數(shù)組，空間復(fù)

27、雜度是O(n)（7） Dijkstra單源最短路算法算法思路與鄰接矩陣類似，不同的地方是開始的時(shí)候要將d數(shù)組和path數(shù)組分別賦值為INF何-1，將s數(shù)組賦值為false，然后將圖中與參數(shù)v相鄰的頂點(diǎn)的d賦值為邊的權(quán)值。整體思路是，首先加入起點(diǎn)到s集合中，然后更新與之相鄰的頂點(diǎn)的數(shù)組d的值，然后每次選擇不在s中并且dj最小的頂點(diǎn)，將頂點(diǎn)加入到s集合，并更新與這個(gè)頂點(diǎn)相鄰的頂點(diǎn)dj的值，然后再選擇不在s中并且dj最小的頂點(diǎn)，如此重復(fù)n-1次，將所有頂點(diǎn)都加入s中。利用s數(shù)組來(lái)標(biāo)記是不是在集合s中，調(diào)用choose函數(shù)來(lái)選擇不在s中且d最小的頂點(diǎn)，每次更新d的時(shí)候也要更新path數(shù)組來(lái)記錄路徑。代

28、碼：templatevoid LGraph:Dijkstra(int v,T *d,int *path) int i; bool *s=new booln; for(i=0;in;i+) di=INF; pathi=-1; si=false; for(i=0;iMv.size();i+) int t=Mvi.to; dt=Mvi.cost; patht=v; sv=true; dv=0; for(i=1;in;i+) int index=-1; int min=INF; for(int j=0;jn;j+) if(sj=false & dj=min) min=dj; index=j; sind

29、ex=true; for(int k=0;kMindex.size();k+) int t=Mindexk.to; if(dindex+Mindexk.costdt&st=false) dt=dindex+Mindexk.cost; patht=index; delete s;算法復(fù)雜度：要加入n-1個(gè)頂點(diǎn)，每次加入都要調(diào)用choose函數(shù)，choose函數(shù)時(shí)間復(fù)雜度是O(n)，綜上，時(shí)間復(fù)雜度是O(n2)?？臻g復(fù)雜度：定義path數(shù)組，d數(shù)組，和s數(shù)組，都是一維數(shù)組，空間復(fù)雜度是O(n)。（8） Floyd多源最短路算法算法與鄰接矩陣類似，要做稍微改動(dòng)，首先要將d和path數(shù)組分別賦值為IN

30、F和-1，然后根據(jù)鄰接表在賦值d和path，這樣才能保證，邊不存在的情況下dij=INF，pathij=-1。整體是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法，其狀態(tài)轉(zhuǎn)移方程為 mapi,j:=minmapi,k+mapk,j,mapi,j 。mapi,j表示i到j(luò)的最短距離，K是窮舉i,j的斷點(diǎn)，mapn,n初值應(yīng)該為0。算法過(guò)程為，首先，從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)為無(wú)窮大。然后，對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比已知的路徑更短。如果存在則更新它。代碼：templa

31、te void LGraph:Floyd(int dSizeSize,int pathSizeSize) for(int i=0;iSize;i+) for(int j=0;jSize;j+) dij=INF; pathij=-1; for(int i=0;in;i+) for(int j=0;jMi.size();j+) int t=Mij.to; dit=Mij.cost; pathit=i; for(int k=0;kn;k+) for(int i=0;in;i+) for(int j=0;jn;j+) if(dik+dkjdij) dij=dik+dkj; pathij=pathkj;

32、 程序測(cè)試：課本179頁(yè)下方圖結(jié)果正確程序測(cè)試: 課本176頁(yè)上方圖結(jié)果正確程序三：飛機(jī)換乘問(wèn)題1）設(shè)有n個(gè)城市，編號(hào)為0n-1，m條航線的起點(diǎn)和終點(diǎn)由用戶輸入提供。尋找一條換乘次數(shù)最少的線路方案。（2）參考：可以使用有向圖表示城市間的航線；只要兩城市間有航班，則圖中這兩點(diǎn)間存在一條權(quán)值為1的邊；可以使用Dijkstra算法實(shí)現(xiàn)。問(wèn)題分析:可以直接使用上面的鄰接矩陣或者鄰接表的圖來(lái)解決這個(gè)問(wèn)題，由于求的是最小換乘次數(shù)，所以如果兩個(gè)頂點(diǎn)存在航線，只要將邊的權(quán)值賦值為1，不存在航線則為INF。在Insert函數(shù)做下修改，然后直接調(diào)用Dijkstra函數(shù)即可。如果dxy=INF說(shuō)明不存在換乘方案。代碼：templateclass MGraphpublic:MGraph(int mSize);MGraph();bool Insert(int u,int v);void Dijkstra(int v,T *d,int *path);protected: int Choose(int *d,bool *s);T *a;int n,e;templateMGraph:MGraph(int mSize)n=mSize;e=0;a=new T*n;for(int i=0;in;i+) ai=new Tn; for(int j=0;jn;j+) aij=INF; aii=0;MGraph:M