6圖6.1圖的概述6.2圖的存儲結(jié)構(gòu)6.3圖的遍歷6.4圖的最小生成樹6.5最短路徑6.6拓撲排序6.7在線題目求解學(xué)習(xí)目標1.記憶和理解圖結(jié)構(gòu)相關(guān)的基本概念和術(shù)語。2.學(xué)會合理選擇圖的存儲結(jié)構(gòu)。3.學(xué)會運用圖的遍歷算法求解具體問題。4.掌握圖的最小生成樹、最短路徑等相關(guān)算法，并能運用這些算法求解具體問題。5.掌握拓撲排序的方法，理解拓撲排序的算法實現(xiàn)。6圖6.1圖的概述圖的定義圖G是由一個頂點集V和一個邊集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，表示為G=(V,E)，其中V是圖G中頂點的集合，E是圖G中頂點之間邊的集合。若頂點v和w之間的邊沒有方向，則稱這條邊為無向邊，表示為無序?qū)?v,w)。若圖中的邊都是無向邊，則該圖稱為無向圖。有G1=(V1,E1)V1={A,B,C,D,E,F}E1={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}則G1對應(yīng)的無向圖如右圖所示6.1圖的概述圖的定義若從頂點v到w的邊有方向，則稱這條邊為有向邊（又稱為?。硎緸橛行?qū)?lt;v,w>，有向邊的箭頭端稱為弧頭，非箭頭端稱為弧尾。若圖中的邊都是有向邊，則該圖稱為有向圖。有G2=(V2,E2)V2={A,B,C,D,E}E2={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}則G2對應(yīng)的有向圖如右圖所示6.1圖的概述圖的基本術(shù)語圖的基本術(shù)語包括網(wǎng)、子圖、完全圖、稀疏圖、稠密圖、鄰接點、度、入度、出度、路徑、路徑長度、簡單路徑、簡單回路、連通圖、連通分量、強連通圖、強連通分量、生成樹和生成森林等。帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。右圖中，(a)為有向網(wǎng)，(b)為無向網(wǎng)。右圖（后2）是右圖（前1）的兩個子圖。設(shè)圖G=(V,E)和圖G1=(V1,E1)，若滿足、，則稱G1為G的子圖。6.1圖的概述圖的基本術(shù)語假設(shè)圖中有n個頂點，m條邊，則含有m=n(n-1)/2條邊的無向圖稱作無向完全圖；含有m=n(n-1)條弧的有向圖稱作有向完全圖。若圖中的邊或弧的個數(shù)m<nlog2n，則該圖稱作稀疏圖，否則稱作稠密圖。對無向圖而言，若頂點v和頂點w之間存在一條邊，則稱頂點v和w互為鄰接點，邊(v,w)和頂點v和w相關(guān)聯(lián)，和頂點v關(guān)聯(lián)的邊的數(shù)目定義為頂點v的度，記作TD(v)。右圖中，A、B互為鄰接點，邊(A,B)與頂點A、B相關(guān)聯(lián)，TD(B)=3、TD(A)=2。6.1圖的概述圖的基本術(shù)語對有向圖而言，頂點的度包括入度和出度。其中，頂點的入度是以該頂點為弧頭的弧的數(shù)目，對于頂點v，其入度記作ID(v)；頂點的出度是以該頂點為弧尾的弧的數(shù)目，對于頂點v，其出度記作OD(v)；頂點的度等于入度和出度之和，對于頂點v，其度TD(v)=ID(v)+OD(v)。例如，右圖中，ID(B)=2，OD(B)=1，TD(B)=3。設(shè)圖G=(V,E)中的一個頂點序列{u=vi,0,vi,1,…,vi,k=w}中，有(vi,j-1,vi,j)

E,1≤j≤k，則稱從頂點u到頂點w之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長度。例如，右上圖中，路徑{A,B,C,D}的路徑長度3。6.1圖的概述圖的基本術(shù)語簡單路徑是頂點序列中頂點不重復(fù)出現(xiàn)的路徑。右圖中，路徑{A,B,C,D}是一條簡單路徑。簡單回路是頂點序列中第一個頂點和最后一個頂點相同的路徑。右圖中，路徑{A,B,C,D,A}是一個簡單回路。對于無向圖，若圖中任意兩個頂點之間都有路徑相通，則此圖稱為連通圖，否則稱為非連通圖；對于非連通圖，圖中各個極大連通子圖稱作此圖的連通分量。右圖中，前圖為連通圖，后圖為非連通圖；后圖中的上、下兩個連通圖為該圖的連通分量。6.1圖的概述圖的基本術(shù)語對于有向圖，若圖中任意兩個頂點之間都存在一條有向路徑，則此有向圖稱為強連通圖，否則稱為非強連通圖；非強連通圖中的各個強連通子圖稱作它的強連通分量。例如，下圖（左）是一個強連通圖，下圖（中）是一個非強連通圖，下圖（右）是下圖（中）的一個強連通分量。6.1圖的概述圖的基本術(shù)語假設(shè)一個連通圖有n個頂點和m條邊，其中n-1條邊和n個頂點構(gòu)成的一個極小連通子圖稱為該連通圖的生成樹。例如，右圖（后）是右圖（前）的一個生成樹。對于非連通圖，各個連通分量的生成樹構(gòu)成此非連通圖的生成森林。例如，右圖（后2）是右圖（前）的一個生成森林。6.1圖的概述圖的基本術(shù)語線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)的邏輯結(jié)構(gòu)關(guān)系對比：（1）在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系，元素之間的關(guān)系為前驅(qū)和后繼；（2）在樹結(jié)構(gòu)中，結(jié)點之間具有層次關(guān)系，結(jié)點之間的關(guān)系為雙親和孩子；（3）在圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系，頂點之間的關(guān)系為鄰接。6.2圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)包含鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表等。這里主要介紹鄰接矩陣、鄰接表。鄰接矩陣基礎(chǔ)鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。設(shè)圖G=(V,E)共有n個頂點，則圖G的鄰接矩陣是一個n階方陣，其中，鄰接矩陣A的元素定義如下：上式的含義：若頂點i，j之間有邊，則鄰接矩陣元素的值為1，否則為0。說明：i，j實際上是頂點的下標，但本章不嚴格區(qū)分頂點與頂點的下標。6.2圖的存儲結(jié)構(gòu)鄰接矩陣基礎(chǔ)右圖（前）是右圖（后）的鄰接矩陣。無向圖的鄰接矩陣是按主對角線對稱的。編程實現(xiàn)時，鄰接矩陣以二維數(shù)組表達。無向圖鄰接矩陣表示法特點（1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；（2）頂點的度等于二維數(shù)組對應(yīng)行（或列）中1的個數(shù)；（3）判斷兩個頂點v、u是否為鄰接點，只需判二維數(shù)組對應(yīng)分量是否為1；（4）在圖中增加、刪除邊，只需對二維數(shù)組對應(yīng)分量賦值1或清0；（5）占用存儲空間只與圖中頂點數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖。6.2圖的存儲結(jié)構(gòu)鄰接矩陣基礎(chǔ)右圖（前）是右圖（后）的鄰接矩陣。通常，有向圖的鄰接矩陣是不對稱的；但有時也是對稱的，例如，有向完全圖的鄰接矩陣是對稱的。采用鄰接矩陣存儲結(jié)構(gòu)，如何編寫算法求有向圖中各頂點的度？6.2圖的存儲結(jié)構(gòu)鄰接矩陣實現(xiàn)作為示例，基本操作僅給出初始化圖和創(chuàng)建圖的實現(xiàn)，其他操作可根據(jù)需要補充。constintN=100;structMGraph{

//圖的定義

intmat[N][N];//邊的信息

intvexnum;//頂點數(shù)

voidInitG(intn);//初始化圖

voidCreateG(intn,intm);//建圖

//其他基本操作，根據(jù)需要自行補充完整};//初始化一個頂點總數(shù)為n的圖voidMGraph::InitG(intn){

vexnum=n;

fill(&mat[0][0],&mat[n-1][n-1]+1,0);}6.2圖的存儲結(jié)構(gòu)鄰接矩陣實現(xiàn)若頂點數(shù)較多，則在結(jié)構(gòu)體中定義mat數(shù)組可能超出棧區(qū)內(nèi)存大小限制，此時可以考慮使用動態(tài)數(shù)組，也可以直接把表示鄰接矩陣的mat數(shù)組作為外部數(shù)組處理。//創(chuàng)建n個頂點，m條邊的無向圖voidMGraph::CreateG(intn,intm){

InitG(n);

for(intj=0;j<m;j++){

inta,b;

cin>>a>>b;

mat[a][b]=1;

mat[b][a]=1;

//

若是有向圖，則省略本語句

}}6.2圖的存儲結(jié)構(gòu)網(wǎng)的鄰接矩陣網(wǎng)是邊上帶權(quán)值的圖，其鄰接矩陣需把權(quán)值表達出來，對于網(wǎng)G=(V,E)，鄰接矩陣A的元素定義如下：其中，

表示邊(i,j)或弧<i,j>上的權(quán)值。如下網(wǎng)對應(yīng)的鄰接矩陣如右所示：6.2圖的存儲結(jié)構(gòu)網(wǎng)的鄰接矩陣實現(xiàn)constintMaxVal=1001;

//

設(shè)邊長不超過1000

//初始化一個頂點總數(shù)為n的網(wǎng)voidMGraph::InitG(intn){

vexnum=n;

fill(&mat[0][0],&mat[n-1][n-1]+1,MaxVal);

for(inti=0;i<n;i++)mat[i][i]=0;}6.2圖的存儲結(jié)構(gòu)網(wǎng)的鄰接矩陣實現(xiàn)//創(chuàng)建n個頂點，m條邊的無向網(wǎng)voidMGraph::CreateG(intn,intm){

InitG(n);

for(intj=0;j<m;j++){

inta,b,c;

cin>>a>>b>>c;

//

a、b是頂點，c為邊(a,b)上的權(quán)值

mat[a][b]=c;

//

a、b之間有邊，則其為邊上的權(quán)值

mat[b][a]=c;

//

若是有向網(wǎng)，則省略本語句

}}6.2圖的存儲結(jié)構(gòu)圖的鄰接表圖的鄰接表包含兩部分，左邊是表頭結(jié)點表，存放頂點信息（包括數(shù)據(jù)域信息和指向鄰接點鏈表的頭指針），右邊是由各個頂點的鄰接點鏈表構(gòu)成的邊表。若有向圖的邊表中存放的鄰接點是弧頭結(jié)點，則稱為有向圖的鄰接表，在有向圖的鄰接表中容易找到由該頂點所指向的弧，但不易找到指向該頂點的弧。若有向圖的邊表中存放的鄰接點是弧尾結(jié)點，則稱為有向圖的逆鄰接表，在逆鄰接表中容易找到指向該頂點的弧。6.2圖的存儲結(jié)構(gòu)圖的鄰接表示例，下圖（左）的鄰接表如下圖（中），逆鄰接表如下圖（右）邊表結(jié)點數(shù)據(jù)域存放的是鄰接點在表頭結(jié)點表中的下標。簡單操作起見，每個新的鄰接點結(jié)點可鏈接到相應(yīng)鏈表的頭部。有向圖采用鄰接表存儲結(jié)構(gòu)，如何編寫算法求各頂點的度？6.2圖的存儲結(jié)構(gòu)網(wǎng)的鄰接表基礎(chǔ)對于網(wǎng)，鄰接表或逆鄰接表中需把邊上的權(quán)值表達出來，因此在鏈表結(jié)點中增加一個權(quán)值域。示例，下圖（左1、左2）的鄰接表如下圖（右1、右2）所示鄰接表占用的存儲空間與頂點數(shù)、邊數(shù)均有關(guān)，適用于稀疏圖。無向圖和有向圖的鄰接表各有什么特點？6.2圖的存儲結(jié)構(gòu)網(wǎng)的鄰接表實現(xiàn)typedefintInfoType;typedefcharVertexType;structArcNode{

intadjvex;

//該弧所指向的頂點的位置

ArcNode*nextarc;//指向下一條弧

InfoTypeweight;//弧上的權(quán)值};

structVNode{

VertexTypedata;//頂點信息

ArcNode*firstarc;//指向第一條依附該頂點的弧};有向網(wǎng)的鄰接表實現(xiàn)6.2圖的存儲結(jié)構(gòu)網(wǎng)的鄰接表實現(xiàn)structALGraph{//鄰接表

VNode*head;

//指向表頭結(jié)點表的首元素

int

vexnum;

//頂點數(shù)

voidInitG(intnum);//初始化圖

voidInsertArc(intfrom,intto,intweight);//增加弧

//其他基本操作};有向網(wǎng)的鄰接表實現(xiàn)

采用鄰接表存儲圖，則可能導(dǎo)致編碼工作量較大。為提高編碼效率，可用vector<int>類型的數(shù)組和鏈式前向星模擬實現(xiàn)鄰接表。6.2圖的存儲結(jié)構(gòu)網(wǎng)的鄰接表實現(xiàn)//初始化一個頂點總數(shù)為num的圖voidALGraph::InitG(intnum){

vexnum=num;

head=newVNode[vexnum];

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

head[i].firstarc=NULL;//指向第一條弧的指針置為空指針

cin>>head[i].data;

//輸入頂點信息

}}有向網(wǎng)的鄰接表實現(xiàn)6.2圖的存儲結(jié)構(gòu)網(wǎng)的鄰接表實現(xiàn)//有向網(wǎng)增加弧(<from,to>,weight)的算法voidALGraph::InsertArc(intfrom,intto,intweight){

ArcNode*s=newArcNode;

s->weight=weight;

s->adjvex=to;

s->nextarc=head[from].firstarc;//插到from頂點對應(yīng)鏈表的頭部

head[from].firstarc=s;}有向網(wǎng)的鄰接表實現(xiàn)

對于無向網(wǎng)，一條邊在鄰接表中存儲兩次，增加邊時需同時調(diào)用InsertArc(from,to,weight)和InsertArc(to,from,weight)。對于圖，增加邊操作可以自定義僅包含from和to參數(shù)的基本操作，也可以為InsertArc函數(shù)的weight參數(shù)增加默認值0。6.3圖的遍歷圖的遍歷是指從圖中某個頂點出發(fā)，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。常見的遍歷方法包括深度優(yōu)先搜索（DepthFirstSearch，DFS）和廣度優(yōu)先搜索（BreadthFirstSearch，BFS）。深度優(yōu)先搜索（DFS）連通圖的DFS算法思想：從圖中某個頂點u出發(fā)，訪問此頂點，然后依次從u的各個未被訪問的鄰接點出發(fā)進行深度優(yōu)先搜索，直至圖中所有和u有路徑相通的頂點都被訪問到。深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先序遍歷。6.3圖的遍歷深度優(yōu)先搜索（DFS）例6.3.1DFS遍歷序列及其生成樹寫出右圖從頂點1出發(fā)DFS的遍歷序列（編號小的頂點優(yōu)先訪問），并畫出對應(yīng)的DFS生成樹。從頂點1出發(fā)DFS的遍歷序列為1234567，對應(yīng)的DFS生成樹如下：6.3圖的遍歷深度優(yōu)先搜索（DFS）連通圖的DFS算法實現(xiàn)voidDFS(MGraphG,intu){

//

采用鄰接矩陣G存儲圖

visited[u]=true;

//

置起點u訪問標記為true

cout<<u;

//

訪問起點u

for(intv=0;v<G.vexnum;v++)//

檢查每個頂點v

if(G.mat[u][v]&&!visited[v])//

若v是鄰接點且未被訪問

DFS(G,v);//

則從頂點v出發(fā)進行深度優(yōu)先搜索}訪問標記數(shù)組“boolvisited[n]”，一開始n個頂點的標記都設(shè)為false，一旦某個頂點已被訪問，就更改其標記為true。6.3圖的遍歷深度優(yōu)先搜索（DFS）非連通圖的DFS算法實現(xiàn)對于非連通圖，若要進行DFS，則先將每個頂點的訪問標記設(shè)為false，之后搜索圖中每個頂點，若未被訪問，則以該頂點為起點進行DFS。voidDFSTraverse(MGraphG){//深度優(yōu)先遍歷

//初始化訪問標記數(shù)組

fill(visited,visited+G.vexnum,false);

for(intv=0;v<G.vexnum;v++)

if(!visited[v])DFS(G,v);//對尚未訪問的頂點調(diào)用DFS}6.3圖的遍歷廣度優(yōu)先搜索（BFS）對于連通圖，從起始點u到其余各頂點必定存在路徑。BFS類似于樹的層次遍歷，依據(jù)路徑長度遞增的順序訪問各個頂點。連通圖的BFS算法思想：從圖中某個頂點u出發(fā)，并在訪問此頂點之后依次訪問u的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有頂點都被訪問到。6.3圖的遍歷廣度優(yōu)先搜索（BFS）例6.3.2BFS遍歷序列及其生成樹寫出右圖從頂點1出發(fā)BFS的遍歷序列（編號小的頂點優(yōu)先訪問），并畫出對應(yīng)的BFS生成樹。從頂點1出發(fā)BFS的遍歷序列為1256734，BFS生成樹如下：6.3圖的遍歷廣度優(yōu)先搜索（BFS）根據(jù)連通圖的BFS算法思想，若頂點u先于頂點v被訪問，則頂點u的鄰接點優(yōu)先于頂點v的鄰接點被訪問，具有“先進先出”的特點，因此借助數(shù)據(jù)結(jié)構(gòu)“隊列”實現(xiàn)BFS算法。首先起點入隊，并置已訪問標記，當隊列非空時，取隊頭元素（設(shè)為u）訪問并出隊，然后把u的所有鄰接點入隊并置已訪問標記。6.3圖的遍歷廣度優(yōu)先搜索（BFS）連通圖的BFS算法實現(xiàn)voidBFS(MGraphG,ints){

//

從s出發(fā)進行廣度優(yōu)先搜索遍歷連通圖

queue<int>Q;Q.push(s);//

起點入隊

visited[s]=true;

//

設(shè)置訪問標記

while(!Q.empty()){//當隊列非空時，重復(fù)執(zhí)行intu=Q.front();

//

取隊頭元素u

cout<<u;

//

輸出u

Q.pop();

//

隊頭元素出隊

for(intv=0;v<G.vexnum;v++){//

u的每個未訪問的鄰接點入隊

if(G.mat[u][v]&&visited[v]==false){

visited[v]=true;

Q.push(v);

}

}

}}6.3圖的遍歷廣度優(yōu)先搜索（BFS）非連通圖的BFS算法實現(xiàn)

對于非連通圖，從某個頂點出發(fā)不能訪遍所有頂點，可不斷選圖中未被訪問的頂點作起始點進行廣度優(yōu)先搜索，直至圖中所有頂點都被訪問到為止。voidBFSTraverse(MGraphG){

//

非連通圖的廣度優(yōu)先遍歷

fill(visited,visited+G.vexnum,false);//

初始化visited數(shù)組

for(intv=0;v<G.vexnum;v++){

if(visited[v]==true)continue;//

若v已訪問，則跳過

BFS(G,v);

//

以頂點v為起始點調(diào)用連通圖的BFS

}}6.4圖的最小生成樹連通網(wǎng)的最小生成樹（MinimumcostSpanningTree，MST）是圖的一個重要應(yīng)用，常用Prim（普里姆）算法和Kruskal（克魯斯卡爾）算法求解。n個頂點的連通圖G的生成樹是包含G中全部頂點的一個極小連通子圖（含有n-1條邊）。連通網(wǎng)的生成樹上各邊的權(quán)值之和稱為該生成樹的代價。連通網(wǎng)中的代價最小的生成樹稱為最小生成樹。Prim算法基礎(chǔ)知識Prim算法的基本思想：對于連通網(wǎng)G=(V,E)，從已有頂點集U（初始時可選第一個頂點作為起始點置于U中）中的頂點出發(fā)，不斷找權(quán)值最小的邊加入（相應(yīng)的在V-U中的鄰接點加入U中），直至包含n個頂點為止。注意，在加邊過程中不能構(gòu)成回路。6.4圖的最小生成樹Prim算法基礎(chǔ)知識例6.4.1用Prim算法求解最小生成樹用Prim算法構(gòu)造右圖中連通網(wǎng)的最小生成樹，要求寫出求解過程。設(shè)邊以三元組(from,to,weight)表示，其中，from是起點、to是終點、weight是權(quán)值。令初始已有點集U={1}。簡單求解過程為依次選邊如下：(1,6,1)(1,5,2)(5,4,5)(1,2,7)(2,3,4)最終得到最小生成樹如下：所得最小生成樹的代價=1+2+5+7+4=19。最小生成樹的求解過程也可畫圖表示。6.4圖的最小生成樹Prim算法的輔助數(shù)組頂點數(shù)設(shè)為n標記數(shù)組visited[n]：初值都為false，visited[i]=true表示把頂點i加入已有點集U中；（當前）最短邊權(quán)值數(shù)組dist[n]：dist[i]表示當前（從已有頂點）進入頂點i的最短邊的權(quán)值。累加dist數(shù)組元素即得最小生成樹代價。鄰接點數(shù)組adjvex[n]：adjvex[i]表示頂點i的鄰接點（與當前進入i的最短邊相關(guān)聯(lián)）的下標。掃描adjvex數(shù)組可得最小生成樹的構(gòu)造情況（即由哪些邊構(gòu)成）。初始時，若無從已有點集U中的頂點到下標為i的頂點的邊，則adjvex[i]=-1。6.4圖的最小生成樹Prim算法的偽代碼1.初始化輔助數(shù)組visited，dist和adjvex；2.將起始頂點u加入已有頂點集合U中；3.重復(fù)執(zhí)行下列操作n-1次：（1）在dist中求得最小值（相應(yīng)頂點在V-U中）的下標為k；（2）將頂點k加入集合U中；（3）調(diào)整數(shù)組dist和adjvex。6.4圖的最小生成樹Prim算法的實現(xiàn)constintMaxVal=INT_MAX;

//用MaxVal表示無窮大constintN=100;

//最大的頂點數(shù)intn;

//實際頂點數(shù)boolvisited[N];

//標記數(shù)組intdist[N];

//最短邊權(quán)值數(shù)組intadjvex[N];

//鄰接點數(shù)組intMinVertex();

//求V-U中未被標記，且dist值最小的頂點//從頂點u出發(fā)構(gòu)造連通網(wǎng)（采用鄰接矩陣存儲）的最小生成樹intPrim(MGraphG,intu){

inti,j,k,cost=0;

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

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

dist[i]=G.mat[u][i];

visited[i]=false;

if(G.mat[u][i]<MaxVal)adjvex[i]=u;

elseadjvex[i]=-1;

}6.4圖的最小生成樹Prim算法的實現(xiàn)

visited[u]=true;

//初始，U＝{u}

for(i=0;i<n-1;i++){//選擇n-1個頂點(邊)

k=MinVertex();

//加入生成樹的下一個頂點(k)

visited[k]=true;

//新節(jié)點加入集合U

//調(diào)整集合V-U中剩余頂點到集合U的最短邊權(quán)值

for(j=0;j<n;j++){

if(visited[j]==false&&G.mat[k][j]<dist[j]){

dist[j]=G.mat[k][j];//更新到j(luò)的最短邊權(quán)值

adjvex[j]=k;//更新j的鄰接點為k

}

}

}

for(i=0;i<n;i++)cost+=dist[i];//計算最小生成樹的代價

returncost;}6.4圖的最小生成樹Prim算法的實現(xiàn)//尋找V-U中未被標記，且dist最小的頂點（下標）intMinVertex(){

intk=-1;

intmin=MaxVal;

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

if(dist[i]<min&&visited[i]==false){

min=dist[i];

k=i;

}

}

returnk;}MinVertex算法的時間復(fù)雜度為O(n)，Prim算法需要進行n-1次循環(huán)，每次調(diào)用MinVertex函數(shù)，故其時間復(fù)雜度為O(n2)。6.4圖的最小生成樹Kruskal算法基礎(chǔ)知識Kruskal算法考慮問題的出發(fā)點：為使生成樹上邊的權(quán)值之和達到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。Kruskal算法采用貪心思想，每次從所有邊中選擇權(quán)值最小的邊加入生成樹。當然，在加邊過程中不能構(gòu)成回路。Kruskal算法思想：初始狀態(tài)為一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG中加入這條邊，如此重復(fù)，直至加入n-1條邊為止。6.4圖的最小生成樹Kruskal算法基礎(chǔ)知識例6.4.2用Kruskal算法求解最小生成樹用Kruskal算法構(gòu)造右圖中連通網(wǎng)的最小生成樹，要求寫出求解過程。設(shè)邊以三元組(from,to,weight)表示，其中，from是起點、to是終點、weight是權(quán)值。令初始狀態(tài)為所有頂點。簡單求解過程為依次選邊如下：(1,6,1)(1,5,2)(2,3,4)(4,

5,5)(1,2,7)最終得到最小生成樹如下：所得最小生成樹的代價=1+2+5+7+4=19。最小生成樹的求解過程也可畫圖表示。6.4圖的最小生成樹Kruskal算法實現(xiàn)Kruskal算法的實現(xiàn)主要考慮兩點，一是每次選一條最小權(quán)值的邊加入SG，二是確保加邊過程中不構(gòu)成回路。為方便選擇權(quán)值最小的邊加入SG，可以先把所有邊按權(quán)值從小到大排序。加邊過程中不構(gòu)成回路可使用并查集的并操作Union來確保。因此，Kruskal算法的實現(xiàn)之前，應(yīng)先引入并查集的初始化、查操作、并操作（詳見5.7節(jié)）。6.4圖的最小生成樹Kruskal算法實現(xiàn)//并查集相關(guān)代碼，詳見5.7節(jié)structEdge{

//

邊的結(jié)構(gòu)體類型

intfrom,to;

intweight;};//比較函數(shù)，邊按權(quán)值小者優(yōu)先，權(quán)值相等時按起點編號小者優(yōu)先，//否則按終點編號小者優(yōu)先boolcmp(Edgee1,Edgee2){

if(e1.weight!=e2.weight)

returne1.weight<e2.weight;

//

權(quán)值小者優(yōu)先

if(e1.from!=e2.from)

returne1.from<e2.from;

//

起點小者優(yōu)先

returne1.to<e2.to;

//

終點小者優(yōu)先}6.4圖的最小生成樹Kruskal算法實現(xiàn)vector<Edge>result;

//

保存結(jié)果邊集的向量//Kruskal算法：求n個頂點m條邊（保存在edges數(shù)組中）的無向網(wǎng)的最小生成樹intKruskal(intn,intm,Edgeedges[]){

result.clear();

sort(edges,edges+m,cmp);

//

對邊數(shù)組排序

Init(n);

//

初始化并查集，詳見5.7節(jié)

if(m<n-1)return-1;

//

總邊數(shù)少于n-1，則不連通

intcost=0,cnt=0;

//

代價，選邊計數(shù)器

for(inti=0;cnt<n-1&&i<m;i++){

//最多選出n-1條邊

//用并查集的并操作（詳見5.7節(jié)）判斷不構(gòu)成回路

if(Union(edges[i].from,edges[i].to)==true){

cnt++;

//

計數(shù)器增1

cost+=edges[i].weight;//

邊權(quán)值累加到代價中

result.push_back(edges[i]);//

選邊加入結(jié)果邊集

}

6.4圖的最小生成樹Kruskal算法實現(xiàn)

}

if(cnt!=n-1)return-1;

//

選邊數(shù)不足n-1，則不連通

elsereturncost;}Kruskal算法中，sort函數(shù)的平均時間復(fù)雜度為O(mlog2m)；選邊過程中，每次Union操作的時間復(fù)雜度為O(log2m)，共執(zhí)行min(n-1,m)次，通常m>n-1，故選邊的for循環(huán)的時間復(fù)雜度可用O(mlog2m)衡量；因此，Kruskal算法的平均時間復(fù)雜度為O(mlog2m)，與邊數(shù)相關(guān)。較之Prim算法，Kruskal算法更適合于求稀疏圖的最小生成樹。6.5最短路徑最短路徑求解算法：Dijkstra（迪杰斯特拉）算法、Floyd（弗洛伊德）算法Dijkstra算法適用于求從某個源點到其余各點的最短路徑，F(xiàn)loyd算法適用于求每一對頂點之間的最短路徑Dijkstra算法基礎(chǔ)Dijkstra算法按最短路徑長度遞增的次序求得各條路徑。其中，第一條最短路徑是一條從源點出發(fā)的邊，并且這條邊的權(quán)值最??；而源點到其余頂點的最短路徑或者是直接從源點到該頂點（只含1條邊），或者是從源點經(jīng)過已求得最短路徑的頂點、再到達該頂點。6.5最短路徑Dijkstra算法基礎(chǔ)Dijkstra算法思想：把圖G=(V,E)的頂點集V分為兩個集合S和V-S，其中S是已有頂點集合（已有點集），V-S是剩余頂點集合；S存放已經(jīng)求得最短路徑的頂點（S初始狀態(tài)只包含源點v，每求得一條最短路徑(v,…,k)，就將k加入S，并更新從v到k的鄰接點w的最短路徑長度），按最短路徑長度遞增的次序把V-S中的頂點逐個加入到S中，直到S=V。例6.5.1單源點最短路徑請用Dijkstra算法求解右圖的有向網(wǎng)中從頂點A到其余各點的最短路徑，要求寫出求解過程。6.5最短路徑Dijkstra算法基礎(chǔ)例6.5.1單源點最短路徑求解過程6.5最短路徑Dijkstra算法實現(xiàn)設(shè)置三個輔助數(shù)組dist、visited、adjvexdist[w]表示當前求得的從源點到頂點w的最短路徑長度。dist[w]的取值dist[w]=<源點到頂點w的邊上的權(quán)值>；或者dist[w]=<源點到其他頂點的路徑長度>+

<其他頂點到頂點w的邊上的權(quán)值>設(shè)當前求得最短路徑的頂點為k，dist數(shù)組的更新方式：dist[w]=min(dist[w],dist[k]+G.mat[k][w])6.5最短路徑Dijkstra算法實現(xiàn)Dijkstra算法的偽代碼1.初始化輔助數(shù)組visited，dist和adjvex；2.將起始頂點u加入已有點集合S中；3.重復(fù)執(zhí)行下列操作n-1次：（1）在dist中求得最小值（相應(yīng)頂點在V-S中）的下標為k；（2）將頂點k加入集合S中；（3）調(diào)整數(shù)組dist和adjvex。6.5最短路徑Dijkstra算法實現(xiàn)constintMaxVal=1000*99+1;//設(shè)最多100個頂點，邊上權(quán)值最大為1000constintN=100;

//最大結(jié)點數(shù)intn;

//實際頂點數(shù)boolvisited[N];

//標記數(shù)組intdist[N];

//最短路徑長度數(shù)組intadjvex[N];

//鄰接點數(shù)組intMinVertex();

//與Prim算法相同，具體定義詳見6.4.1節(jié)

structMGraph{

//鄰接矩陣結(jié)構(gòu)

intmat[N][N];

intvexnum;};6.5最短路徑Dijkstra算法實現(xiàn)//求圖G（采用鄰接矩陣）從頂點v出發(fā)的單源最短路徑voidDijkstra(MGraphG,intv){

inti;

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

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

dist[i]=G.mat[v][i];

visited[i]=false;

if(G.mat[v][i]<MaxVal)adjvex[i]=v;

elseadjvex[i]=-1;

}

visited[v]=true;

//頂點v加入已有點集S中

for(i=1;i<=n-1;i++){//循環(huán)n-1次

intk=MinVertex();//針對V-S集合，求dist最小的頂點下標

visited[k]=true;

//頂點k加入已有點集S中6.5最短路徑Dijkstra算法實現(xiàn)

for(intw=0;w<n;w++){//調(diào)整數(shù)組dist和adjvex

if(dist[w]>dist[k]+G.mat[k][w]&&visited[w]==false){

dist[w]=dist[k]+G.mat[k][w];

adjvex[w]=k;

}

}

}

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

if(i>0)cout<<"";

cout<<dist[i];

}

cout<<endl;}MinVertex算法的時間復(fù)雜度為O(n)，Dijkstra算法需要進行n-1次循環(huán)，每次調(diào)用MinVertex函數(shù)，因此時間復(fù)雜度為O(n2)。6.5最短路徑Floyd算法基礎(chǔ)對于網(wǎng)中任意一對頂點之間的最短路徑的問題，可每次以一個頂點為源點，共調(diào)用Dijkstra算法n次。顯然，時間復(fù)雜度為O(n3)。任意一對頂點之間的最短路徑的問題采用Floyd算法求解時代碼更加簡潔，其時間復(fù)雜度也是O(n3)。Floyd算法基本思想：對于從頂點（下標）i到j(luò)的路徑，進行n次試探：首先考慮路徑(i,0,j)（即增加中間頂點0）是否存在，如果存在，則比較(i,j)和(i,0,j)的路徑長度，取其中較短者，從而得到從頂點i到j(luò)的中間頂點不大于0的最短路徑。然后在路徑上再增加一個中間頂點1，依此類推，直到增加中間頂點n-1，在經(jīng)過n次試探后，最后求得的必是從頂點i到頂點j的最短路徑的長度。6.5最短路徑Floyd算法基礎(chǔ)設(shè)圖G的鄰接矩陣為mat，定義D為n階方陣，其中D(k)[i][j]表示從頂點i到j(luò)的最短路徑的長度（中間所經(jīng)過的頂點不大于k），則D(n-1)[i][j]就是最終的結(jié)果。令初始狀態(tài)D(-1)[i][j]=G.mat[i][j]，即方陣D初始為圖G的鄰接矩陣，F(xiàn)loyd算法的遞推公式如下：D(k)[i][j]=min{D(k-1)[i][k]+D(k-1)[k][j],D(k-1)[i][j]}，k=0,

1,

2,

…

,

n-1其中，D(k-1)[i][k]+D(k-1)[k][j]表示經(jīng)過中間點kD(k-1)[i][j]表示不經(jīng)過中間點k。6.5最短路徑Floyd算法基礎(chǔ)例6.5.2任意兩點之間的最短路徑用Floyd算法求解右圖的有向網(wǎng)中任意兩個頂點之間的最短路徑，要求寫出求解過程。求解過程如下，D(3)為最終結(jié)果：6.5最短路徑Floyd算法實現(xiàn)//Floyd算法，求網(wǎng)G中每對頂點間最短路徑長度//結(jié)果通過二維數(shù)組參數(shù)D返回，N為最大的頂點數(shù)voidFloyd(MGraphG,intD[N][N]){

intn=G.vexnum;

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

for(intj=0;j<n;j++)

D[i][j]=G.mat[i][j];//初始化輔助數(shù)組

//遞推求解每對頂點間最短路徑長度，若鄰接矩陣以二維數(shù)組D表示，則僅需以下代碼

for(intk=0;k<n;k++)

//n次試探，中間經(jīng)過的頂點編號不大于k

for(inti=0;i<n;i++)//遍歷求解頂點對(i,j)之間的最短路徑長度

for(intj=0;j<n;j++)

D[i][j]=min(D[i][k]+D[k][j],D[i][j]);}6.6拓撲排序拓撲排序基礎(chǔ)在一個有向圖中，若用頂點表示活動、用弧表示活動之間的優(yōu)先關(guān)系，則稱這樣的有向圖為頂點表示活動的網(wǎng)（ActivityOnVertexNetwork，AOVN），其特點如下：（1）AOVN中的弧表示活動之間存在的某種制約關(guān)系；（2）AOVN中不能出現(xiàn)回路（環(huán)）。有向無環(huán)圖（DirectedAcyclineGraph，DAG）是指不存在回路的有向圖。顯然，AOVN是DAG。如何判斷一個有向圖是否存在回路？可以對有向圖進行拓撲排序，若能得到拓撲序列，則不存在回路，否則存在回路。AOVN6.6拓撲排序拓撲排序基礎(chǔ)拓撲排序的方法具體如下：（1）從有向圖中選取一個沒有前驅(qū)的頂點，并輸出；（2）從有向圖中刪去此頂點以及所有以它為尾的??；（3）重復(fù)上述兩步，直到全部頂點都被輸出，或圖中不再存在無前驅(qū)的頂點。例6.6.1拓撲序列寫出右圖的有向圖的拓撲序列（至少寫6個）。ABCDGHFE；ABCHDGFE；ABHCDGFE；ACBDGHFE；ACDBGHFE；ACDBHGFE。6.6拓撲排序拓撲排序算法實現(xiàn)考慮算法實現(xiàn)，前述拓撲排序方法中的定性描述轉(zhuǎn)換為定量表達（1）“沒有前驅(qū)的頂點”用“入度為零的頂點”替代（2）“刪除頂點及以它為尾的弧”用“待刪頂點相關(guān)聯(lián)弧的弧頭頂點的入度減1”替代拓撲排序的算法實現(xiàn)通?？紤]采用鄰接表存儲圖，如此可以取得較高的效率。鄰接表的表頭結(jié)點表中的頂點結(jié)構(gòu)包括頂點信息vertex，指向第一條弧的指針first；邊表中的結(jié)點包含鄰接點域adjvex和指向下一條弧的指針域next。對于n個頂點，使用入度數(shù)組in[n]保存各頂點的入度。6.6拓撲排序拓撲排序算法實現(xiàn)拓撲排序偽代碼1.計數(shù)器cnt初始化；2.掃描入度數(shù)組，將入度為0的頂點入隊；3.當隊列非空時進行循環(huán)：（1）取隊頭元素v并輸出，隊頭元素出隊，cnt++；（2）將頂點v的各個鄰接點的入度減1，若產(chǎn)生新的入度為0的頂點，則把它入隊；4.如果cnt<頂點數(shù)n，則輸出有回路信息（拓撲排序失?。?。6.6拓撲排序拓撲排序算法實現(xiàn)structArcNode{

//邊表結(jié)點結(jié)構(gòu)

intadjvex;//該弧所指向的頂點的位置

ArcNode*next;

//指向下一條弧};

structVNode{

//表頭結(jié)點表結(jié)構(gòu)

intvertex;

//頂點信息

ArcNode*first;

//指向第一條依附該頂點的弧};

constintN=100;

//最大頂點數(shù)intin[N];

//入度數(shù)組voidCountInDegree(VNodeadjList[],intn);//統(tǒng)計各頂點的入度6.6拓撲排序拓撲排序算法實現(xiàn)//拓撲排序算法，對n個頂點的有向圖（以鄰接表adjList存儲）進行拓撲排序voidTopSort(VNodeadjList[],intn){

queue<int>Q;

//定義隊列Q

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

if(in[i]==0)Q.push(i);//入度為零的頂點（下標）入隊

}

intcnt=0;

//定義計數(shù)器

while(Q.empty()==false){

//隊列非空時循環(huán)

intv=Q.front();

//取隊頭元素（下標）v

if(cnt>0)cout<<"";

//控制每兩個頂點之間留一個空格

cout<<adjList[v].vertex;//輸出隊頭元素

Q.pop();

//出隊

cnt++;

//計數(shù)器加1

6.6拓撲排序拓撲排序算法實現(xiàn)

ArcNode*p=adjList[v].first;//p指向v為弧尾的鄰接點鏈表

while(p!=NULL){//對以v為弧尾的每個鄰接點入度減1

intw=p->adjvex;//取鄰接點w

in[w]--;

//弧頭頂點的入度減1

if(in[w]==0)Q.push(w);//入度為零的頂點入隊

p=p->next;

//p指向下一個結(jié)點

}

}

if(cnt<n)cout<<"Fail";

//拓撲排序失敗

cout<<endl;}6.6拓撲排序拓撲排序算法實現(xiàn)//對各頂點求入度，存放到數(shù)組in中voidCountInDegree(VNodeadjList[],intn){

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

in[i]=0;

//初始化

}

for(intj=0;j<n;j++){

ArcNode*p=adjList[j].first;//p指向j為弧尾的鄰接點鏈表

while(p!=NULL){

//對以v為弧尾的每個鄰接點入度增1

intw=p->adjvex;//取鄰接點w

in[w]++;

//弧頭頂點的入度增1

p=p->next;

//p指向下一個結(jié)點

}

}}6.7在線題目求解例6.7.1暢通工程

某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表，表中列出了每條道路直接連通的城鎮(zhèn)。省政府“暢通工程”的目標是使全省任何兩個城鎮(zhèn)間都可以相互可達（但不一定有直接的道路相連，只要互相間接通過道路可達即可）。問最少還需要建設(shè)多少條道路？輸入:

測試數(shù)據(jù)有多組。對于每組測試，先輸入兩個正整數(shù)，分別是城鎮(zhèn)數(shù)目n(1<n<1000)和道路數(shù)目M；隨后的M行對應(yīng)M條道路，每行給出一對正整數(shù)，分別是該條道路直接連通的兩個城鎮(zhèn)的編號。為簡單起見，城鎮(zhèn)從1到n編號。

注意：兩個城市之間可以有多條道路相通，也就是說如下輸入也是合法的。6.7在線題目求解例6.7.1暢通工程33121221當n為0時，輸入結(jié)束。輸出:對于每組測試，輸出一行，包含一個整數(shù)，表示最少還需要建設(shè)的道路數(shù)目。輸入樣例:4213430輸出樣例:1解析：本題實際上是求非連通圖共有幾個連通分量，可以從未被訪問頂點出發(fā)調(diào)用連通圖的DFS或BFS求解，每調(diào)用一次則計數(shù)器cnt加1，最后結(jié)果為cnt-1。由于頂點數(shù)較多，直接使用外部數(shù)組表示鄰接矩陣。6.7在線題目求解例6.7.1暢通工程#include<iostream>#include<queue>usingnamespacestd;constintN=1000;intmat[N][N];boolvisited[N];intn;voiddfs(inti){

visited[i]=true;

for(intj=0;j<n;j++){

if(visited[j]==false&&mat[i][j]==1)dfs(j);

}}6.7在線題目求解例6.7.1暢通工程voidbfs(ints){

queue<int>Q;

visited[s]=true;

Q.push(s);

while(Q.empty()==false){

intv=Q.front();

Q.pop();

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

if(mat[v][i]==1&&visited[i]==false){

visited[i]=true;

Q.push(i);

}

}

}}6.7在線題目求解例6.7.1暢通工程intmain(){

while(true){

inti,m,a,b;

cin>>n;

if(n==0)break;

cin>>m;

fill(&mat[0][0],&mat[n-1][n-1]+1,0);

fill(visited,visited+n,false);

for(i=0;i<m;i++){

cin>>a>>b;

a--;

b--;

mat[a][b]=1;

mat[b][a]=1;

}6.7在線題目求解例6.7.1暢通工程

intcnt=0;

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

if(visited[i]==true)continue;

cnt++;

dfs(i);

//bfs(i);

}

cout<<cnt-1<<endl;

}

return0;}6.7在線題目求解例6.7.2還是暢通工程

某省調(diào)查鄉(xiāng)村交通狀況，得到的統(tǒng)計表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可），并要求鋪設(shè)的公路總長度為最小。請計算最小的公路總長度。輸入:

測試數(shù)據(jù)有多組。每組測試數(shù)據(jù)的第一行輸入村莊數(shù)目N（N<100）；隨后的N(N-1)/2行對應(yīng)村莊間的距離，每行給出一對正整數(shù)，分別是兩個村莊的編號，以及此兩村莊間的距離（<1000）。簡單起見，村莊從1到N編號。

當輸入N為0時，表示輸入結(jié)束。輸出:

對于每組測試，在一行上輸出最小的公路總長度。6.7在線題目求解例6.7.2還是暢通工程輸入樣例:31211322340輸出樣例:3解析：依題意易知，本題是一個最小生成樹問題。本題的頂點數(shù)最多100個，采用自定義圖的鄰接矩陣存儲圖，最小生成樹的代價直接以Prim算法求解。6.7在線題目求解例6.7.2還是暢通工程#include<iostream>usingnamespacestd;

constintN=100,Max=1000;structG{

intn;

intmat[N][N];

voidInit(intn);

voidCreateG(intn,intm);};6.7在線題目求解例6.7.2還是暢通工程voidG::Init(intnum){

n=num;

fill(&mat[0][0],&mat[n-1][n-1]+1,Max);

for(inti=0;i<n;i++)mat[i][i]=0;}voidG::CreateG(intnum,intm){

Init(num);

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

inta,b,c;

cin>>a>>b>>c;

a--;

b--;

mat[a][b]=mat[b][a]=c;

}}6.7在線題目求解例6.7.2還是暢通工程intdist[N];boolvisited[N];

intmin(Gg){

intk=-1;

intm=Max;

for(inti=0;i<g.n;i++){

if(dist[i]<m&&visited[i]==false){

m=dist[i];

k=i;

}

}

returnk;}6.7在線題目求解例6.7.2還是暢通工程intPrim(Gg,ints){

inti;

for(i=0;i<g.n;i++){

dist[i]=g.mat[s][i];

visited[i]=false;

}

visited[s]=true;

for(i=0;i<g.n-1;i++){

intk=min(g);

visited[k]=true;

for(intj=0;j<g.n;j++){

if(g.mat[k][j]<dist[j]&&visited[j]==false){

dist[j]=g.mat[k][j];

}

}6.7在線題目求解例6.7.2還是暢通工程

}

intsum=0;

for(i=0;i<g.n;i++){

sum+=dist[i];

}

returnsum;}6.7在線題目求解例6.7.2還是暢通工程intmain(){

while(true){

Gg;

intn,m;

cin>>n;

if(n==0)break;

m=n*(n-1)/2;

g.CreateG(n,m);

intcost=Prim(g,0);

cout<<cost<<endl;

}

return0;}6.7在線題目求解例6.7.3旅游規(guī)劃

有一張自駕旅游路線圖，已給定城市間的高速公路長度以及該公路要收取的過路費。請編寫程序，幫助前來咨詢的游客找一條出發(fā)地和目的地之間的最短路徑。如果有若干條路徑都是最短的，那么需要輸出最便宜的一條路徑。輸入:

每組測試數(shù)據(jù)第1行輸入4個正整數(shù)N、M、S、D，其中N（2≤N≤500）表示城市的個數(shù)，城市的編號為0~N-1；M是高速公路的條數(shù)；S是出發(fā)地的城市編號；D是目的地的城市編號；隨后的M行中，每行輸入一條高速公路的信息，分別是：城市1、城市2、高速公路長度、收費額，中間用空格分開，數(shù)字均為整數(shù)且不超過500。輸入保證解的存在。6.7在線題目求解例6.7.3旅游規(guī)劃輸出:

在一行上輸出路徑的長度和收費總額，每兩個數(shù)字之間以一個空格分隔。輸入樣例:45030112013230034100222023120輸出樣例:340解析：本題是一個綜合考慮路徑長度和費用的二維最短路徑問題?？梢孕薷腄ijkstra算法，把路徑長度和收費都考慮進去。這里把每個城市作為一個頂點，兩個頂點之間的路徑長度和收費作為一個整體（聲明一個結(jié)構(gòu)體類型P）。鄰接矩陣以P類型的二維向量表示，標記數(shù)組visited、保存最短路徑長度的數(shù)組dist、保存最小費用的數(shù)組cost都以一維向量表示。6.7在線題目求解例6.7.3旅游規(guī)劃#include<iostream>#include<vector>usingnamespacestd;

constintMAX=501*501;structP{

intd,c;};vector<vector<P>>mat;vector<bool>visited;vector<int>dist;vector<int>cost;intn;6.7在線題目求解例6.7.3旅游規(guī)劃intminVertex(){

intnext=-1;

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

if(!visited[i]&&(next==-1||dist[i]<dist[next]||

(dist[i]==dist[next]&&cost[i]<cost[next])))

next=i;

}

returnnext;}6.7在線題目求解例6.7.3旅游規(guī)劃voidDijkstra(intsource){

inti;

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

dist[i]=mat[source][i].d;

cost[i]=mat[source][i].c;

}

fill(visited.begin(),visited.end(),false);

visited[source]=true;

while(true){

intnext=minVertex();

if(next==-1)break;

visited[next]=true;6.7在線題目求解例6.7.3旅游規(guī)劃

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

if(!visited[i]&&(dist[i]>mat[next][i].d+dist[next]||

(dist[i]==mat[next][i].d+dist[next]&&

cost[i]>mat[next][i].c+c