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

2、運(yùn)算，包括插入邊，移除邊，判斷邊是否存在，深度優(yōu)先遍歷DFS,寬度優(yōu)先遍歷BFS,單源最短路Dijkstra算法，多源最短路Floyd算法，以及最小生成樹prim算法。程序定義了一個圖類包含三個數(shù)據(jù)成員，分別是指向二維數(shù)據(jù)的指針T*a，記錄頂點(diǎn)數(shù)的n和記錄邊數(shù)量的e。構(gòu)造函數(shù)負(fù)責(zé)申請二維數(shù)組動態(tài)空間，析構(gòu)函數(shù)負(fù)責(zé)釋放空間。類的聲明：templateclassMGraphpublic:MGraph(intmSize);MGraph();boolInsert(intu,intv,intw);boolRemove(intu,intv);boolExist(intu,intv)const;voidDF

3、S();voidBFS();voidDijkstra(intv,T*d,int*path);voidFloyd(intdSize,intpathSize);voidprim(intk,int*nearest,T*lowcost);protected:intChoose(int*d,bool*s);voidDFS(intv,bool*visited);voidBFS(intv,bool*visited);T*a;intn,e;(1)深度優(yōu)先遍歷DFS算法圖的深度優(yōu)先遍歷重載了兩個DFS函數(shù)，分別是面向用戶的DFS()和私有成員DFS(intv,bool*visited)。面向用戶的不帶參數(shù)版本，

4、首先定義一個一位數(shù)組visited來標(biāo)記當(dāng)前已經(jīng)訪問過的結(jié)點(diǎn)，并初始化為false。為了防止圖不是一個連通圖，在外層DFS中，要通過一個循環(huán)一遍一遍的調(diào)用帶參數(shù)版本的DFS(i,visited),如果圖是一個連通圖，那么在第一次調(diào)用之后，所以的visited都變成true，后續(xù)就不再調(diào)用，如果圖不是一個連通圖，那么還要多次調(diào)用帶參數(shù)版本DFS(i,visited)通過這個方法，也可以用來判斷圖是不是一個連通圖。代碼：templatevoidMGraph:DFS()inti;bool*visited=newbooln;for(i=0;in;i+)visitedi=false;for(i=0;in

5、;i+)if(visitedi=false)DFS(i,visited);coutendl;deletevisited;templatevoidMGraph:DFS(intv,bool*visited)visitedv=true;printf(%d,v);for(intu=0;un;u+)false)if(avu!=INF&visitedu=DFS(u,visited);算法分析：深度優(yōu)先遍歷，沒嵌套調(diào)用一次，實(shí)際是對一個頂點(diǎn)V查看所有的鄰接點(diǎn),設(shè)圖有n個頂點(diǎn)，時間復(fù)雜度是O(2)空間復(fù)雜度：由于要定義一個臨時數(shù)組標(biāo)記訪問過的頂點(diǎn)，所以空間復(fù)雜度是O(n)。(2)寬度優(yōu)先遍歷BFS圖的寬度優(yōu)先

6、遍歷BFS重載了兩個版本，一個是面向用戶的不帶參數(shù)版本，一個是帶參數(shù)版本。不帶參數(shù)版本的作用主要是為了防止圖不是一個連通圖，導(dǎo)致不能訪問所有頂點(diǎn)，所有通過一個循環(huán)來一遍一遍調(diào)用帶參數(shù)版本BFS，與DFS類似，如果圖是一個連通圖，那么第一次調(diào)用就能訪問所有頂點(diǎn)，如果不是連通圖，得多次調(diào)用，通過此方法也可以判斷是不是連通圖。帶參數(shù)版本BFS通過隊列來實(shí)現(xiàn)寬度優(yōu)先遍歷，首先將第一個頂點(diǎn)加入隊列，然后，每次從隊列取出一個頂點(diǎn)，并將與之相鄰并且還沒有訪問過的頂點(diǎn)加入到隊列，直到隊列為空停止。為了代碼簡潔，隊列使用了STL庫的queue頭文件。代碼：templatevoidMGraph:BFS()inti

7、;bool*visited=newbooln;for(i=0;in;i+)visitedi=false;for(i=0;in;i+)if(visitedi=false)BFS(i,visited);coutendl;deletevisited;templatevoidMGraph:BFS(intv,bool*visited)queueQ;visitedv=true;Q.push(v);while(!Q.empty()v=Q.front();Q.pop();coutv;for(inti=0;in;i+)if(visitedi=false&avi!=INF)visitedi=true;Q.push

8、(i);算法分析：每個頂點(diǎn)只進(jìn)入一次隊列，對于每個從隊列取走的點(diǎn)，都查看其所有的鄰接點(diǎn)，設(shè)頂點(diǎn)數(shù)是n,邊數(shù)是e,時間復(fù)雜度是O(2)空間復(fù)雜度：同樣需要定義臨時數(shù)組標(biāo)記訪問過的頂點(diǎn),隊列中元素個數(shù)不超過n個，所以空間復(fù)雜度是O(n)。(3)prim最小生成樹算法prim算法的整體思路為，首先加入一個頂點(diǎn)到生成樹中,然后，每次加入一條代價最小的邊，邊的一個頂點(diǎn)已被加入生成樹，一個頂點(diǎn)未被加入生成樹，然后標(biāo)記這個邊的頂點(diǎn)，表示將這個頂點(diǎn)也加入，加入之后更新其lowcost數(shù)組，然后繼續(xù)選邊，直到所有頂點(diǎn)都被標(biāo)記。定義三個臨時數(shù)組，mark數(shù)組來實(shí)現(xiàn)上述標(biāo)記，lowcostj記錄與頂點(diǎn)j相接的邊中最

9、小的權(quán)值（邊的另一個頂點(diǎn)未被標(biāo)記)，nearestj表示頂點(diǎn)j上述最小權(quán)值邊的另一個頂點(diǎn)。主函數(shù)打印最小生成樹的邊集(nearestj,j,lowcostj)代碼：templatevoidMGraph:prim(intk,int*nearest,T*lowcost)bool*mark=newbooln;if(kn-1)printf(outofboundsn);return;for(inti=0;in;i+)nearesti=-1;lowcosti=INF;marki=false;lowcostk=0;nearestk=k;markk=true;intcnt=n-1;while(cnt-)for

10、(inti=0;iaki)lowcosti=aki;nearesti=k;Tminn=INF;for(intj=0;jn;j+)if(!markj)&(lowcostjminn)minn=lowcostj;k=j;markk=true;算法分析：由于要加入n個頂點(diǎn)，每次加入都要找最小邊和更新lowcost,所以時間復(fù)雜度是O(nA2)o空間復(fù)雜度：定義兩個一維數(shù)組，空間復(fù)雜度是O(n)Dijkstra單源最短路算法Dijkstra的整體思路是，首先加入起點(diǎn)到s集合中，然后更新與之相鄰的頂點(diǎn)的數(shù)組d的值，然后每次選擇不在s中并且dj最小的頂點(diǎn)，將頂點(diǎn)加入到s集合，并更新與這個頂點(diǎn)相鄰的頂點(diǎn)dj的

11、值，然后再選擇不在s中并且dj最小的頂點(diǎn)，如此重復(fù)n-1次，將所有頂點(diǎn)都加入s中。利用s數(shù)組來標(biāo)記是不是在集合s中，調(diào)用choose函數(shù)來選擇不在s中且d最小的頂點(diǎn)，每次更新d的時候也要更新path數(shù)組來記錄路徑。代碼：templatevoidMGraph:Dijkstra(intv,T*d,int*path)inti,k,w;if(vn-1)coutoutofbounds!endl;return;bool*s=newbooln;for(i=0;in;i+)si=false;di=avi;if(i!=v&diINF)pathi=v;elsepathi=-1;sv=true;dv=0;for(i

12、=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個頂點(diǎn)，每次加入都要調(diào)用choose函數(shù),choose函數(shù)時間復(fù)雜度是O(n),綜上,時間復(fù)雜度是0(22)。空間復(fù)雜度：定義path數(shù)組，d數(shù)組，和s數(shù)組，都是一維數(shù)組，空間復(fù)雜度是O(n)。(5)Floyd多源最短路算法Floyd算法又稱為插點(diǎn)法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法其狀態(tài)轉(zhuǎn)移方程如下：mapi,j:=minmapi,k+mapk,j,mapi,j；mapi,j表示

13、i到j(luò)的最短距離，K是窮舉i,j的斷點(diǎn)，mapn,n初值應(yīng)該為0，或者按照題目意思來做。算法過程為，首先，從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。然后，對于每一對頂點(diǎn)u和v,看看是否存在一個頂點(diǎn)w使得從u到w再到v比已知的路徑更短。如果存在則更新它。代碼：templatevoidMGraph:Floyd(intdSize,intpathSize)inti,j,k;for(inti=0;in;i+)for(intj=0;jn;j+)dij=aij;if(i!=j&aijINF)pathij=i;elsepathij=-1;for(k=0;kn;k

14、+)for(i=0;in;i+)for(j=0;jn;j+)if(dik+dkjdij)dij=dik+dkj;pathij=pathkj;算法分析：時間復(fù)雜度是O(3)，用二維數(shù)組保存結(jié)果，空間復(fù)雜度是O(2)。程序測試：輸入課本179頁下方圖結(jié)果正確程序測試:176頁上方圖結(jié)果正確。程序二：鄰接表表示的圖的基本運(yùn)算本程序包含鄰接表表示的圖的基本運(yùn)算，包括插入邊，移除邊，判斷邊是否存在，深度優(yōu)先遍歷DFS,寬度優(yōu)先遍歷BFS，單源最短路Dijkstra算法，多源最短路Floyd算法，以及最小生成樹prim算法。程序定義了一個圖類包含三個數(shù)據(jù)成員，分別是指向vector的數(shù)組的指針,記錄頂點(diǎn)數(shù)

15、的n和記錄邊數(shù)量的e。構(gòu)造函數(shù)負(fù)責(zé)申請n個vector數(shù)組，Mi為一個vector數(shù)組，存放頂點(diǎn)i相接的邊，相當(dāng)于鏈表，為了代碼的簡潔，程序用STL庫的vector代替了鏈表。析構(gòu)函數(shù)負(fù)責(zé)釋放空間。Vector的元素類型為定義的結(jié)構(gòu)體表示的邊，邊上有兩個屬性，分別是邊的另一側(cè)的頂點(diǎn)值，和邊的權(quán)值。表示邊的結(jié)構(gòu)體：structedgeintto;intcost;edge(intx,inty)to=x;cost=y;表示邊的圖例說明：類的聲明：templateclassLGraphprivate:vector*M;intn;inte;voidDFS(intu,bool*vis);voidBFS(i

16、ntv,bool*vis);public:LGraph(intmSize);LGraph();boolInsert(intu,intv,intw);boolExist(intu,intv);boolRemove(intu,intv);voidDijkstra(intv,T*d,int*path);voidprim(intk,int*nearest,T*lowcost);voidFloyd(intdSize,intpathSize);voidDFS();voidBFS();類的圖例說明:(1)構(gòu)造函數(shù)負(fù)責(zé)申請n個vector數(shù)組，用來存放鄰接邊代碼：templateLGraph:LGraph(i

17、ntmSize)M=newvectormSize;n=mSize;e=0;(2)插入函數(shù)InsertInsert函數(shù)首先判斷插入的邊是否存在，如果存在返回false不存在則插入邊，插入的時候首先構(gòu)造一個邊，然后調(diào)用vector的push_back函數(shù)插入。代碼：templateboolLGraph:Insert(intu,intv,intw)inti;if(u0|un-1|un-1)returnfalse;for(i=0;iboolLGraph:Remove(intu,intv)inti;if(u0|vn-1|vn-1)returnfalse;for(i=0;iMu.size();i+)if(

18、Mui.to=v)Mu.erase(Mu.begin()+i);returntrue;returnfalse;(4)深度優(yōu)先遍歷DFS與上面鄰接矩陣的DFS類似，鄰接表由于直接記錄與當(dāng)前頂點(diǎn)相鄰的頂點(diǎn)，所有循環(huán)的時候不需要遍歷所有頂點(diǎn)判斷INF,循環(huán)的時間復(fù)雜度更加低。思路與鄰接矩陣類似，但是由于鄰接表在插入的時候沒有考慮順序，導(dǎo)致每個頂點(diǎn)后面接的頂點(diǎn)不一定按照從小到大的順序排列，而鄰接矩陣循環(huán)是從0到n-1按照從小到大的順序來的，所以為了保持和鄰接矩陣的一致性，在DFS的時候第一步首先將每個vector進(jìn)行排序，將vector中元素按照邊的另一頭頂點(diǎn)從小到大的順序排列，調(diào)用STL中的頭文件中

19、的sort傳入函數(shù)參數(shù)cmpcmp定義：intcmp(edgea,edgeb)returna.tob.to;DFS代碼：templatevoidLGraph:DFS()for(inti=0;in;i+)sort(Mi.begin(),Mi.end(),cmp);inti;bool*vis=newbooln+1;for(i=0;in;i+)visi=false;for(i=0;in;i+)if(visi=false)DFS(i,vis);deletevis;coutendl;templatevoidLGraph:DFS(intv,bool*vis)visv=true;printf(%d,v);i

20、nti;for(i=0;iMv.size();i+)intt=Mvi.to;if(vist=false)DFS(t,vis);算法分析：深度優(yōu)先遍歷，沒嵌套調(diào)用一次，實(shí)際是對一個頂點(diǎn)v查看所有的鄰接點(diǎn)，設(shè)圖有n個頂點(diǎn)，時間復(fù)雜度是O(n+e)。空間復(fù)雜度是O(n)。(5)寬度優(yōu)先遍歷BFSBFS與鄰接矩陣類似，重載了兩個版本，一個是面向用戶的不帶參數(shù)版本，一個是帶參數(shù)版本。不帶參數(shù)版本的作用主要是為了防止圖不是一個連通圖，導(dǎo)致不能訪問所有頂點(diǎn)，所有通過一個循環(huán)來一遍一遍調(diào)用帶參數(shù)版本BFS,與DFS類似，如果圖是一個連通圖，那么第一次調(diào)用就能訪問所有頂點(diǎn)，如果不是連通圖，得多次調(diào)用，通過此方法

21、也可以判斷是不是連通圖。帶參數(shù)版本BFS通過隊列來實(shí)現(xiàn)寬度優(yōu)先遍歷，首先將第一個頂點(diǎn)加入隊列，然后，每次從隊列取出一個頂點(diǎn)，并將與之相鄰并且還沒有訪問過的頂點(diǎn)加入到隊列，直到隊列為空停止。為了代碼簡潔，隊列使用了STL庫的queue頭文件。代碼：templatevoidLGraph:BFS()inti;bool*vi=newbooln;for(i=0;in;i+)vii=false;for(i=0;in;i+)if(vii=false)BFS(i,vi);coutendl;deletevi;templatevoidLGraph:BFS(intv,bool*vi)inti;viv=true;qu

22、eueQ;Q.push(v);while(!Q.empty()v=Q.front();printf(%d,v);Q.pop();for(i=0;iMv.size();i+)intt=Mvi.to;if(vit=false)Q.push(t);vit=true;算法分析：每個頂點(diǎn)只進(jìn)入一次隊列，對于每個從隊列取走的點(diǎn)，都查看其所有的鄰接點(diǎn)，設(shè)頂點(diǎn)數(shù)是n,邊數(shù)是e,時間復(fù)雜度是O(n+e)?？臻g復(fù)雜度：隊列中元素個數(shù)不超過n個，同時需要定義數(shù)組標(biāo)記已訪問過的頂點(diǎn)，所以空間復(fù)雜度是O(n)。(6)prim最小生成樹算法鄰接表的prim算法與鄰接矩陣類似，只是在循環(huán)的時候稍有不同，要注意鄰接點(diǎn)是edg

23、e中的to元素。算法的整體思路為，首先加入一個頂點(diǎn)到生成樹中，然后，每次加入一條代價最小的邊，邊的一個頂點(diǎn)已被加入生成樹，一個頂點(diǎn)未被加入生成樹，然后標(biāo)記這個邊的頂點(diǎn)，表示將這個頂點(diǎn)也加入，加入之后更新其lowcost數(shù)組，然后繼續(xù)選邊，直到所有頂點(diǎn)都被標(biāo)記。定義三個臨時數(shù)組，mark數(shù)組來實(shí)現(xiàn)上述標(biāo)記，lowcostj記錄與頂點(diǎn)j相接的邊中最小的權(quán)值(邊的另一個頂點(diǎn)未被標(biāo)記)，nearestj表示頂點(diǎn)j上述最小權(quán)值邊的另一個頂點(diǎn)。主函數(shù)打印最小生成樹的邊集(nearestj,j,lowcostj)代碼：templatevoidLGraph:prim(intk,int*nearest,T*lo

24、wcost)bool*mark=newbooln+1;for(inti=0;in;i+)nearesti=-1;marki=false;lowcosti=INF;markk=true;lowcostk=0;nearestk=k;for(inti=1;in;i+)for(intj=0;jMkj.cost&!(markt)lowcostt=Mkj.cost;nearestt=k;intmin=INF;for(intj=0;jn;j+)if(!markj&lowcostjmin)min=lowcostj;k=j;markk=true;deletemark;算法分析：由于要加入n個頂點(diǎn)，每次加入都要找

25、最小邊和更新lowcost，所以時間復(fù)雜度是O(2)。空間復(fù)雜度：定義兩個一維數(shù)組，空間復(fù)雜度是O(n)(7)Dijkstra單源最短路算法算法思路與鄰接矩陣類似，不同的地方是開始的時候要將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集合，并更新與這個頂點(diǎn)相鄰的頂點(diǎn)dj的值，然后再選擇不在s中并且dj最小的頂點(diǎn)，如此重復(fù)n-1次，將所有頂點(diǎn)都加入s中。利用s數(shù)組來標(biāo)記是不是在集合s中，調(diào)用choo

26、se函數(shù)來選擇不在s中且d最小的頂點(diǎn)，每次更新d的時候也要更新path數(shù)組來記錄路徑。代碼：templatevoidLGraph:Dijkstra(intv,T*d,int*path)inti;bool*s=newbooln;for(i=0;in;i+)di=INF;pathi=-1;si=false;for(i=0;iMv.size();i+)intt=Mvi.to;dt=Mvi.cost;patht=v;sv=true;dv=0;for(i=1;in;i+)intindex=-1;intmin=INF;for(intj=0;jn;j+)if(sj=false&dj=min)min=dj;i

27、ndex=j;sindex=true;for(intk=0;kMindex.size();k+)intt=Mindexk.to;if(dindex+Mindexk.costdt&st=false)dt=dindex+Mindexk.cost;patht=index;deletes;算法復(fù)雜度：要加入n-1個頂點(diǎn)，每次加入都要調(diào)用choose函數(shù)，choose函數(shù)時間復(fù)雜度是O(n),綜上，時間復(fù)雜度是O(nA2)o空間復(fù)雜度：定義path數(shù)組，d數(shù)組，和s數(shù)組，都是一維數(shù)組，空間復(fù)雜度是O(n)。(8)Floyd多源最短路算法算法與鄰接矩陣類似，要做稍微改動，首先要將d和path數(shù)組分別賦值為

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

29、ph:Floyd(intdSizeSize,intpathSizeSize)for(inti=0;iSize;i+)for(intj=0;jSize;j+)dij=INF;pathij=-1;for(inti=0;in;i+)for(intj=0;jMi.size();j+)intt=Mij.to;dit=Mij.cost;pathit=i;for(intk=0;kn;k+)for(inti=0;in;i+)for(intj=0;jn;j+)if(dik+dkjdij)dij=dik+dkj;pathij=pathkj;程序測試：課本179頁下方圖C:Use5ZLDesktopXexercis

30、:鄒擺表binDebug圄請靛6悟輸入枸壟有問至込是無向團(tuán)？1，無冇囹2.苣向艮請輸入有巨邊門個頻11請輸入&條有向邊015041Up70b210(20H21Ri3_202315bJJk330Fi)FLuytl請端/、起屯和終點(diǎn)02-3-1-MFLuyd請綣人起巨和終點(diǎn).F.最短路長克足：煮路徑為:FLuyd請綣人起巨和終點(diǎn).2最毎路匚麥足：4路徑為:2-3-1-4FLoyd請綣/、起巨f口餐點(diǎn)、000000停止:停止:停止:停止:輸入2愉入2愉入結(jié)果正確程序測試:課本176頁上方圖匚:UsersZLDesktapexercise圏迪觀耘JbinDebug刮，”一請輸入頂佢數(shù):6帯鉞杓茬有冃至

31、込是無向罰1無冇團(tuán)-有問屋1謂輸入無向邊的個數(shù)1J請輸入2GEGGC0條兀向邊n-.只035021TOC o 1-5 h z1b3512ini254pHEZ-5hoyd請編人起點(diǎn)和終點(diǎn)，輸入00停止:1尉亙路匸走足:蹈徑再:1-/4FLoyd請獻(xiàn)起點(diǎn)和終點(diǎn)，輸入00停止:4u尉亙路氏袞是：7臨錚:4：2：0結(jié)果正確程序三：飛機(jī)換乘問題1)設(shè)有n個城市，編號為0n-1,m條航線的起點(diǎn)和終點(diǎn)由用戶輸入提供。尋找一條換乘次數(shù)最少的線路方案。(2)參考：可以使用有向圖表示城市間的航線；只要兩城市間有航班，則圖中這兩點(diǎn)間存在一條權(quán)值為1的邊；可以使用Dijkstra算法實(shí)現(xiàn)。問題分析:可以直接使用上面的

32、鄰接矩陣或者鄰接表的圖來解決這個問題，由于求的是最小換乘次數(shù)，所以如果兩個頂點(diǎn)存在航線，只要將邊的權(quán)值賦值為1，不存在航線則為INF。在Insert函數(shù)做下修改，然后直接調(diào)用Dijkstra函數(shù)即可。如果dxy=INF說明不存在換乘方案。代碼：templateclassMGraphpublic:MGraph(intmSize);MGraph();boolInsert(intu,intv);voidDijkstra(intv,T*d,int*path);protected:intChoose(int*d,bool*s);T*a;intn,e;templateMGraph:MGraph(intmSize)n=mSize;e=0;a=newT*n;for(inti=0;in;i+)ai=newTn;for(intj=0;jn;j+)aij=INF;aii=0;MGraph:MGraph()for(inti=0;in;i+)deleteai;deletea;templateboolMGraph:Insert(intu,intv)if(u0|vn-1|vn-1|u=v)returnfalse;if(auv!=INF)returnfalse