《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第7章 圖》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第7章 圖（49頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第7章 圖 1 邏輯結(jié)構(gòu) 1.1 定義 G = (V, E) V是頂點(diǎn)集，E是頂點(diǎn)間二元關(guān)系的集合 內(nèi)涵越小，外延越大 與樹的區(qū)別： ①樹有特殊的根結(jié)點(diǎn)； ②樹的結(jié)點(diǎn)和關(guān)系能分成互不相交的若干子集 圖的分類： 無向圖 有向圖 邊：二元關(guān)系是無序的。 弧：二元關(guān)系是有序的。 (vi,vj)：vi,vj互為鄰接點(diǎn) ：弧頭vj、弧尾vi G1=(V1,E1) V1={v1,v2,v3,v4} E1={(v1,v2),(v1,v3), (v1,v4),(v2,v3), (v2,v4),(v3,v4)} G2=(V2,E

2、2) V2={v1,v2,v3,v4} E2={, , , } 不予討論的圖: (總能轉(zhuǎn)換為簡單圖) 1.2 基本操作 對(duì)整體的操作 (遍歷) 深度遍歷DFSTraverse、 廣度遍歷BFSTraverse 對(duì)頂點(diǎn)的操作 InsertVex、DeleteVex、GetVex、SetVex 對(duì)弧/邊的操作 InsertArc、DeleteArc、GetArc、SetArc 1.3 常見應(yīng)用 ①信息的組織：家庭照片管理…… ②運(yùn)輸問題：最短路徑問題、最優(yōu)乘車路線問題…… ③網(wǎng)絡(luò)規(guī)劃：小區(qū)設(shè)店問題

3、、區(qū)域連通的規(guī)劃問題…… ④進(jìn)度組織：工程進(jìn)度管理…… 1.4 概念 思路：考慮圖的復(fù)雜應(yīng)用，提供簡化問題的思路。 1.4.1 圖的分類 著眼點(diǎn)：存儲(chǔ)結(jié)構(gòu)的選擇。 無向完全圖 邊數(shù)：n*(n-1)/2 有向完全圖 弧數(shù)：n*(n-1) 稀疏圖 邊數(shù)≈頂點(diǎn)數(shù) 稠密圖 邊數(shù)≈頂點(diǎn)數(shù)2 帶權(quán)圖 邊或頂點(diǎn)帶權(quán)值 著眼點(diǎn)：圖的分解。 子圖 V(B)∈V(A)，E(B)∈E(A)，稱圖B是圖A的子圖。 1.4.2 頂點(diǎn)的參數(shù) 度 無向圖中，依附于某頂點(diǎn)的邊數(shù) 入度 有向圖中，以某頂點(diǎn)為弧尾的弧數(shù) 出度 有向圖中，以某頂點(diǎn)為弧頭的弧數(shù)

4、 度的應(yīng)用：以下哪個(gè)圖能夠一筆畫完成？為什么？ 一筆畫問題的本質(zhì)：圖結(jié)構(gòu)中的邊遍歷問題。 應(yīng)用領(lǐng)域：車間/廠房布置、行走路線的安排、交通設(shè)計(jì)… 1.4.3 有關(guān)路徑 著眼點(diǎn)：頂點(diǎn)間的聯(lián)系。 頂點(diǎn)間路徑 Vi,……,Vj 頂點(diǎn)間連通 若從Vi到Vj有路徑，稱Vi到Vj是連通的。 路徑長度 路徑上邊/弧的數(shù)目。 簡單路徑 路徑中所有頂點(diǎn)各不相同。 回路 路徑中，起點(diǎn)和終點(diǎn)是同一頂點(diǎn)。 簡單回路 除起點(diǎn)和終點(diǎn)外，其余頂點(diǎn)各不相同。 1.4.4 有關(guān)連通 著眼點(diǎn)：將不連通圖簡化為連通圖。 連通圖 無向圖中,任意二個(gè)頂點(diǎn)之間是連通的。

5、 無向圖的 連通分量 無向圖的極大連通子圖。 強(qiáng)連通圖 有向圖中,任意二個(gè)頂點(diǎn)之間存在來往路徑。 有向圖的 強(qiáng)連通分量 有向圖的極大強(qiáng)連通子圖。 1.4.5 生成樹 著眼點(diǎn)：將圖簡化為樹。 無向圖 生成樹 連通無向圖中，n個(gè)頂點(diǎn)和n-1條邊，構(gòu)成的連通子圖。（原連通圖的極小連通子圖） 生成森林 不連通的無向圖中，各連通分量的生成樹的集合。 有向圖 生成樹 強(qiáng)連通有向圖中，n個(gè)頂點(diǎn)和n-1條弧，構(gòu)成的單向連通子圖(vi、vj間存在一條路徑)。 一個(gè)頂點(diǎn)入度為０，其余頂點(diǎn)入度為１。 生成森林 不強(qiáng)連通的有向圖中，各有強(qiáng)連通分量的生成樹的集合。

6、 第7章 圖 2 圖的存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)應(yīng)該包含： ①頂點(diǎn)的信息；②邊/弧的信息；③權(quán)的信息。 2.1 鄰接矩陣 2.1.1 結(jié)構(gòu)圖 0, 1, 1, 0 1, 0, 0, 1 1, 0, 0, 1 0, 1, 1, 0 0, 4, 2, Inf 4, 0, Inf, 8 2, Inf, 0, 1 Inf, 8, 1, 0 0, 4, 2, Inf Inf, 0, Inf, 8 Inf, Inf, 0, Inf Inf, Inf, 1, 0 2.1.2 類的定義 cons

7、t double Inf=10000; struct Edge { int v1,v2; double weight; }; class Mgraph // 簡化版，只存儲(chǔ)了邊/弧的信息。 { int m_N; vector > *m_Es; public: MGraph(int n); ~MGraph(); void Append(vector &es); void Output(); int Degree(int k); }; 空間復(fù)雜度：O(n*n)。 適合稠密圖，當(dāng)點(diǎn)多邊少時(shí)，空間

8、浪費(fèi)多。 2.1.2 （無向圖的）類的實(shí)現(xiàn) // 構(gòu)造函數(shù) MGraph::MGraph(int n) { m_N = n; m_Es=new vector >(n,vector(n,Inf)); for(int i=0; i &es) { for(int i=0;

9、 i

10、鄰接表 2.2.1 結(jié)構(gòu)圖 圖的變化特征：頂點(diǎn)變化少，關(guān)系變化多。 頂點(diǎn)表: 順序結(jié)構(gòu)。邊/弧表：動(dòng)態(tài)鏈表。 帶權(quán)圖的鄰接表 2.2.2 類的定義 struct ArcNode // 邊、弧結(jié)構(gòu) { int adjvex; // 鄰接點(diǎn)、弧頭的編號(hào) double weight; ArcNode *nextarc; }; template struct VexNode // 頂點(diǎn)結(jié)構(gòu) { T data; ArcNode *firstarc; // 指向出邊表 }; template

11、T> class ALGraph { int m_N; vector > m_Data; // 頂點(diǎn)向量 public: ALGraph(vector vs);; ~ALGraph(); void Append(vector &es); void Output(); ……………… }; 空間復(fù)雜度：O(n+e) n是頂點(diǎn)數(shù)，e是邊/弧數(shù)。 2.2.3 類的實(shí)現(xiàn) // 構(gòu)造函數(shù) template ALGraph::ALGraph(vector vs) { m_N

12、= vs.size(); m_Data.resize(m_N); for(int i=0; i void ALGraph::Append(vector &es) { for(int i=0; i

13、 ArcNode *p=new ArcNode; p->adjvex=v2; p->weight=es[i].weight; p->nextarc=m_Data[v1].firstarc; m_Data[v1].firstarc = p; } } // 計(jì)算有向圖中頂點(diǎn)i的出度 template int ALGraph::OutDegree(int k) { int n=0; for(ArcNode *p=m_Data[k].firstarc; p; p=p->nextarc) n++; retu

14、rn n; } // 計(jì)算有向圖中頂點(diǎn)i的入度 template int ALGraph::InDegree(int k) { int n=0; for(int i=0; inextarc) if(p->adjvex==k) n++; return n; } 試題： 計(jì)算有向圖的入度表、出度表； 判斷無向圖G是否可以一筆畫。 2.2.3 擴(kuò)展思考：頂點(diǎn)的維護(hù)問題 例：刪除指定頂點(diǎn)的結(jié)構(gòu)

15、變化 原圖的結(jié)構(gòu) 刪除頂點(diǎn)2之后的圖結(jié)構(gòu) 2.3 逆鄰接表 2.3.1 結(jié)構(gòu)圖 鄰接表（出邊表） 逆鄰接表（入邊表） 思考：根據(jù)鄰接表繪制逆鄰接表。 2.3.2 類的定義 同鄰接表類 2.4 十字鏈表 2.4.1 結(jié)構(gòu)圖 將鄰接表、逆鄰接表合二為一。 主要用于表示有向圖。 和稀疏矩陣的十字鏈表結(jié)構(gòu)相比：本質(zhì)一樣。細(xì)節(jié)差別在于：行頭表和列頭表合并為了頂點(diǎn)表。 等價(jià)結(jié)構(gòu)： 2.2.2 類的定義 struct ArcNode // 弧結(jié)構(gòu) { int tailvex; // 弧尾的編號(hào) int

16、headvex; // 弧頭的編號(hào) double weight; ArcNode *tlink; // 指向弧尾相同的弧結(jié)點(diǎn) ArcNode *hlink; // 指向弧頭相同的弧結(jié)點(diǎn) }; template struct VexNode // 頂點(diǎn)結(jié)構(gòu) { T data; ArcNode *firstin; // 指向入邊表 ArcNode *firstout; // 指向出邊表 }; template class OLGraph { vector > m_D

17、ata; // 頂點(diǎn)向量 ……………… }; 2.5 鄰接多重表 2.4.1 結(jié)構(gòu)圖 無向圖的鄰接表有50%的冗余。精簡方法：每條邊對(duì)應(yīng)一個(gè)邊結(jié)點(diǎn)。 主要用于表示無向圖。 鄰接多重表結(jié)構(gòu) 2.4.2 類的定義 struct EdgeNode // 邊、弧結(jié)構(gòu) { int ivex; // 第一鄰接點(diǎn)編號(hào) int jvex; // 第二鄰接點(diǎn)編號(hào) double weight; ArcNode *ilink; // 指向第一鄰接點(diǎn)編號(hào)為i的邊結(jié)點(diǎn) ArcNode *jlink; // 指向第二鄰接點(diǎn)編號(hào)為j的邊結(jié)

18、點(diǎn) }; template struct VexNode // 頂點(diǎn)結(jié)構(gòu) { T data; ArcNode *firstedge; // 第一個(gè)邊結(jié)點(diǎn) }; template class OLGraph { vector > m_Data; // 頂點(diǎn)向量 ……………… }; 第7章 圖 3 圖的遍歷 圖遍歷：從某頂點(diǎn)出發(fā)，對(duì)每個(gè)頂點(diǎn)訪問且僅訪問一次。 圖遍歷與樹遍歷的比較： 區(qū)別 可能回到起點(diǎn)。 因?yàn)閳D不能劃分為若干個(gè)互不相交的子圖。 算法擴(kuò)展 對(duì)訪問過的頂點(diǎn)作標(biāo)記，并

19、加以識(shí)別。 3.1 深度優(yōu)先搜索DFS(Depth First Search) 3.1.1 算法 ①設(shè)置一個(gè)標(biāo)記數(shù)組，設(shè)所有頂點(diǎn)都未曾被訪問； ②從起點(diǎn)v出發(fā)，訪問此頂點(diǎn)，同時(shí)設(shè)置訪問標(biāo)記； ③依次從v的未被訪問過的鄰接點(diǎn)出發(fā)進(jìn)行DFS； （效果：所有與v連通的頂點(diǎn)都被訪問過） ④若所有頂點(diǎn)都已訪問，則完成；否則，另擇起點(diǎn)v，轉(zhuǎn)至②。 圖的邏輯結(jié)構(gòu) 圖的鄰接表存儲(chǔ)結(jié)構(gòu) 以頂點(diǎn)0為起點(diǎn)的DFS：0，1，4，3，2 以頂點(diǎn)3為起點(diǎn)的DFS：3，1，4，2，0 3.1.2 算法實(shí)現(xiàn)（遞歸） // 帽子函數(shù) template vect

20、or ALGraph::DFSTraverse() { vector vs,vs1; // 實(shí)現(xiàn)步驟① vector visited(m_Data.size(),false); // 實(shí)現(xiàn)步驟④ for(int v=0; v

21、),vs1.end()); } return vs; } template void ALGraph::DoDFSTraverse(int v,vector& visited,vector& vs) { // 實(shí)現(xiàn)步驟② vs.push_back(m_Data[v].data); visited[v]=true; // 實(shí)現(xiàn)步驟③ for(ArcNode *p=m_Data[v].firstarc; p; p=p->nextarc) { int w=p->adjvex; if(visit

22、ed[w]==false) DoDFSTraverse(w,visited,vs); } } 思考1：與樹的遞歸遍歷算法的共性。 思考2：時(shí)間復(fù)雜度？ 思考3：計(jì)算DFS生成樹的各邊。 思考4：若采用鄰接矩陣結(jié)構(gòu)，程序如何調(diào)整？ 3.1.3 調(diào)試示例 紅色邊：構(gòu)成DFS生成森林，稱為樹邊。 結(jié)點(diǎn)中的左數(shù)字：開始訪問該結(jié)點(diǎn)的步驟； 結(jié)點(diǎn)中的右數(shù)字：完成訪問該結(jié)點(diǎn)的所有鄰接點(diǎn)的步驟； 3.1.4 調(diào)試中的深入思考 搜索過程中，邊的分類： 回邊：子孫結(jié)點(diǎn)指向祖先結(jié)點(diǎn)。 前向邊：祖先結(jié)點(diǎn)指向子孫結(jié)點(diǎn)。 交叉邊：子樹/樹之間

23、的邊。 應(yīng)用：若在DFS過程中，沒有發(fā)現(xiàn)回邊，則該圖無環(huán)。 3.1.5 判斷無向圖中是否是連通，并計(jì)算連通分量的個(gè)數(shù) int ALGraph::DFSTraverse() { vector vs,vs1; int n=0; vector visited(m_Data.size(),false); for(int v=0; v

24、sited,vs1); n++; vs.insert(vs.end(),vs1.begin(),vs1.end()); } return n; } 3.1.5 判斷無向圖中是否有回路 // 不適用于有向圖 template bool ALGraph::HasCircle() { vector visited(m_N,false); for(int v=0; v

25、rcle(v,visited)==true) return true; // 存在環(huán) return false; // 所有連通分量中，不存在環(huán) } template bool ALGraph::DoHasCircle(int v,vector& visited) { visited[v]=true; for(ArcNode *p=m_Data[v].firstarc; p; p=p->nextarc) { int w=p->adjvex; if(visited[w]==true)

26、 return true; // w已被訪問過，即發(fā)現(xiàn)環(huán)路 if(DoHasCircle(w,visited)) return true; // 在以w為起點(diǎn)的DFS中發(fā)現(xiàn)環(huán)路 } return false; // 在以v為起點(diǎn)的DFS中，沒有發(fā)現(xiàn)環(huán)路 } 3.2 廣度優(yōu)先搜索BFS(breadth first search) 3.2.1 算法 ①設(shè)所有頂點(diǎn)都未曾被訪問； ②將起點(diǎn)編號(hào)加入隊(duì)列，同時(shí)設(shè)置訪問標(biāo)記； ③取隊(duì)首元素，設(shè)為v，訪問結(jié)點(diǎn)v； ④依次將v的各個(gè)未被訪問過的頂點(diǎn)加入隊(duì)列，同時(shí)設(shè)置訪問標(biāo)記； ⑤若隊(duì)

27、列不空，則循環(huán)執(zhí)行③④，否則⑥； ⑥若所有頂點(diǎn)都已訪問，則完成；否則，另擇起點(diǎn)V，轉(zhuǎn)至②。 已知鄰接表，求遍歷序列。 以頂點(diǎn)0為起點(diǎn)的BFS：0，1，3，4，2 以頂點(diǎn)3為起點(diǎn)的BFS：3，1，0，4，2 3.2.2 算法實(shí)現(xiàn) // 帽子函數(shù) template vector ALGraph::BFSTraverse() { vector vs,vs1; // 實(shí)現(xiàn)步驟① vector visited(m_Data.size(),false); // 實(shí)現(xiàn)步驟⑥ for(int v=0; v<

28、m_N; v++) if(visited[v]==false) { vs1.clear(); DoBFSTraverse(v,visited,vs1); vs.insert(vs.end(),vs1.begin(),vs1.end()); } return vs; } template void ALGraph::DoBFSTraverse(int v,vector& visited,vector& vs) { queue

29、> Q; ArcNode *p; Q.push(v); visited[v]=true; // 步驟② while(!Q.empty()) // 步驟⑤ { v=Q.front(); Q.pop(); vs.push_back(m_Data[v].data); // 步驟③ // 步驟④ for(ArcNode *p=m_Data[v].firstarc; p; p=p->nextarc) { int w=p->adjvex; if(visited[w]==false)

30、 { Q.push(w); visited[w]=true; } } } } 思考1：與樹的層次遍歷算法的共性。 思考2：時(shí)間復(fù)雜度？ 思考3：計(jì)算BFS生成樹的各邊。 思考4：計(jì)算起點(diǎn)到其余各頂點(diǎn)的最短路徑。 3.2.3 調(diào)試示例 紅色邊：構(gòu)成BFS生成森林，稱為樹邊。 結(jié)點(diǎn)數(shù)字：距離起點(diǎn)的路徑長度 3.4 生成樹、生成森林的存儲(chǔ)結(jié)構(gòu)（擴(kuò)展思考） 在遍歷中，如何將生成樹、生成森林，以孩子兄弟法存儲(chǔ)起來？ 圖的鄰接表結(jié)構(gòu) 圖的生成森林的二叉鏈表結(jié)構(gòu) 3.5 關(guān)節(jié)點(diǎn)、

31、重連通分量（擴(kuò)展思考） 3.5.1 概念 關(guān)節(jié)點(diǎn) 若刪除某頂點(diǎn)及其關(guān)聯(lián)各邊，圖的一個(gè)連通分量將分割為多個(gè)連通分量，則該頂點(diǎn)是關(guān)節(jié)點(diǎn)。 重連通分量 沒有關(guān)節(jié)點(diǎn)的連通圖。 圖的連通度 若在連通圖上至少要?jiǎng)h除k個(gè)頂點(diǎn)才能破壞圖的連通性，則該圖的圖的連通度為k。 實(shí)際意義：連通度等價(jià)于系統(tǒng)的可靠度。 算法：在DFS生成樹，根結(jié)點(diǎn)至少有2個(gè)子結(jié)點(diǎn)，則為關(guān)節(jié)點(diǎn)。 第7章 圖 專題1 圖的非遞歸深度遍歷算法 1.1 狀態(tài)的定義 struct Status // 遍歷狀態(tài)類 { int v; // 遍歷中的當(dāng)前頂點(diǎn)編號(hào) ArcNode *p;

32、// 當(dāng)前頂點(diǎn)已經(jīng)訪問的弧結(jié)點(diǎn)的指針 }; 1.2 與遞歸函數(shù)完全相同的帽子函數(shù) template vector ALGraph::DFSTraverse() { vector vs,vs1; vector visited(m_N,false); for(int v=0; v

33、 vs.insert(vs.end(),vs1.begin(),vs1.end()); } return vs; } 1.3 借助狀態(tài)棧的回溯法 // 約定每個(gè)頂點(diǎn)被訪問之后，再進(jìn)棧 與樹先根算法的區(qū)別：訪問標(biāo)記的處理 template void ALGraph::DoDFSTraverse(int v,vector& visited,vector& vs) { stack S; vs.push_back(m_Data[v].data); visited[v]=true; St

34、atus s1={v,m_Data[v].firstarc}; S.push(s1); while( !S.empty() ) { Status &s=S.top(); // s是棧頂狀態(tài)的引用 // 尋找v的下一個(gè)未訪問過的鄰接點(diǎn) for(; s.p; s.p=s.p->nextarc) if(visited[s.p->adjvex]==false) break; if(s.p) { int w=s.p->adjvex; // 頂點(diǎn)w未訪問過 vs.push_back(m_Data[w].data); v

35、isited[w]=true; Status nexts; nexts.v=w; nexts.p=m_Data[w].firstarc; S.push(nexts); } else S.pop(); // 以v為起點(diǎn)的搜索已經(jīng)完畢 } } 1.4 調(diào)試案例 訪問0 訪問1 訪問4 訪問3 訪問2 第7章 圖 專題2 地圖著色問題 2.1 地圖著色問題及其邏輯結(jié)構(gòu) 設(shè)一張地圖有n個(gè)區(qū)域，用不多

36、于4種顏色對(duì)這些區(qū)域進(jìn)行著色，相鄰區(qū)域應(yīng)具有不同的顏色。 區(qū)域圖 邏輯結(jié)構(gòu)圖 2.2 地圖著色判斷問題 試設(shè)計(jì)算法，以一種著色方案為輸入，算法對(duì)該著色方案進(jìn)行考察，判別是否滿足著色要求。 // colors[0]...colors[m_N-1]存儲(chǔ)了所有區(qū)域的顏色值 template bool ALGraph::Check(vector &colors) { for(int i=0; inextarc)

37、 if(colors[p->adjvex]==colors[i]) return false; return true; } // colors[0]...colors[n-1]存儲(chǔ)了部分區(qū)域的顏色值 template bool ALGraph::Check(vector &colors,int n) { for(int i=0; inextarc) if(p->adjvex

38、->adjvex]==colors[i]) return false; return true; } 2.3 計(jì)算所有的地圖著色方案 template vector > ALGraph::GetAllColors() { vector > allColors; // 所有的著色方案 vector Colors(m_N,0); // 當(dāng)前著色方案 GetAllColors(0,Colors,allColors); return allColors;

39、 } template void ALGraph::GetAllColors(int i, vector Colors, vector > &allColors) { if(i==m_N) { // 當(dāng)前著色方案已經(jīng)全部齊備 if(Check(Colors)) allColors.push_back(Colors); return; } for(int color=1; color<=4; color++) { Colors[i]=color; // 第i個(gè)區(qū)域設(shè)

40、置為color顏色 if(Check(Colors,i+1)) // 剪枝法：檢查局部解的合理性 GetAllColors(i+1,Colors,allColors); } } 2.3 小結(jié) 本質(zhì)上，窮舉所有的著色方案，是遍歷4叉樹所有葉子結(jié)點(diǎn)的過程。效率不高，但配合剪枝法的應(yīng)用，能較好的改善算法性能。 作業(yè)與上機(jī) 1 圖的鄰接表類 建立鄰接表類，深度、廣度遍歷之，盡可能的豐富鄰接表類的成員函數(shù)； 方向1：計(jì)算生成樹/生成森林的弧向量，進(jìn)而建立生成樹/生成森林的樹的存儲(chǔ)結(jié)構(gòu)。 方向2：判別圖中是否存在回路； 方向3：計(jì)算頂點(diǎn)之間的

41、最短的路徑長度； 方向4：計(jì)算圖中的關(guān)節(jié)點(diǎn)，進(jìn)而計(jì)算圖的連通度； 方向5：參照樹的非遞歸遍歷算法，實(shí)現(xiàn)圖的非遞歸深度遍歷算法。 方向6：計(jì)算地圖著色的一個(gè)/所有著色方案。 2 圖的應(yīng)用 Prim算法、Kruskal算法 Dijkstra算法、Floyd算法。 拓?fù)渑判蛩惴?、關(guān)鍵路徑算法。 第7章 圖 4 最小生成樹 4.1 概念 最小生成樹：各邊權(quán)值之和最小的生成樹。 原圖 生成樹一 生成樹二 生成樹三 4.2 Prim算法 4.2.1 算法思路 設(shè)圖G=(V,E)，從起點(diǎn)v出發(fā)，構(gòu)造最小生成樹T=(VT,ET)。

42、①初始化VT={v}，ET={}； ②找權(quán)值最小的(Vp,Vq), Vp∈VT, Vq∈V-VT； ③將(Vp,Vq)并入ET，同時(shí)Vq并入VT； ④重復(fù)②③步驟n-1次。 4.2.2 數(shù)據(jù)結(jié)構(gòu) ①圖的結(jié)構(gòu) 因需要頻繁地讀取邊的權(quán)值，所以采用鄰接矩陣。 調(diào)試案例：以頂點(diǎn)4為起點(diǎn)，構(gòu)造最小生成樹。 M_Data: {{ 0, 2,Inf,Inf,Inf, 7, 3,Inf,Inf}, { 2, 0, 4,Inf,Inf,Inf, 6,Inf,Inf}, {Inf, 4, 0, 2,Inf,Inf,Inf, 2,Inf}, {Inf,I

43、nf, 2, 0, 1,Inf,Inf, 8,Inf}, {Inf,Inf,Inf, 1, 0, 6,Inf,Inf, 2}, { 7,Inf,Inf,Inf, 6, 0,Inf,Inf, 5}, { 3, 6,Inf,Inf,Inf,Inf, 0, 3, 1}, {Inf,Inf, 2, 8,Inf,Inf, 3, 0, 4}, {Inf,Inf,Inf,Inf, 2, 5, 1, 4, 0} }; ②輔助結(jié)構(gòu) 針對(duì)：找權(quán)值最小的(Vp,Vq), Vp∈VT, Vq∈V-VT； 設(shè)計(jì)結(jié)構(gòu)：VT外每個(gè)頂點(diǎn)到V

44、T的最短距離。 struct ShortDist // 表示某頂點(diǎn)到VT的最短距離及對(duì)應(yīng)頂點(diǎn) { float Distance; // VT外頂點(diǎn)到VT的最短距離 int VexInTree;// VT對(duì)應(yīng)的頂點(diǎn)編號(hào) }; vector SDs; 表示所有頂點(diǎn)到VT的最短距離及對(duì)應(yīng)頂點(diǎn)。 示例：以V4為起點(diǎn)構(gòu)造最小生成樹，SDs的初始數(shù)據(jù)： 下標(biāo) 0 1 2 3 4 5 6 7 8 VexInTree 4 4 4 4 4 4 4 4 4 Distance INF INF INF 1 0 6 I

45、NF INF 2 SDs[i].Distance=0的含義：頂點(diǎn)i已在生成樹中 4.2.3 算法及分析 ① 初始化SDs； ② 在SDs中,找出Distance最小非0值的下標(biāo)k； ③ (SDs[k].VexInTree,k)為生成樹的邊； k是樹外某點(diǎn)，SDs[k].VexInTree是樹內(nèi)某點(diǎn)； ④ SDs[k].Distance=0，即頂點(diǎn)k并入生成樹； ⑤ 若cost[k][i]

46、ee 4 4 4 4 4 4 4 4 4 Distance M M M 1 0 6 M M 2 第一次循環(huán)后 VexInTree 4 4 3 4 4 4 4 3 4 Distance M M 2 0 0 6 M 8 2 第二次循環(huán)后 VexInTree 4 2 3 4 4 4 4 2 4 Distance M 4 0 0 0 6 M 2 2 設(shè)圖頂點(diǎn)數(shù)為n，時(shí)間復(fù)雜度是O(n2)，空間復(fù)雜度是O(n)。 4.2.4 算法實(shí)現(xiàn)一：求MST的所有邊 vector

47、ge> MGraph::Prim1(int startv) { int n=m_Es->size(); vector tree(n-1); vector SDs(n); for(int i=0; i

48、小非0值的下標(biāo)k if(SDs[j].Distance!=0 && SDs[j].Distance

49、tance) { SDs[j].Distance=(*m_Es)[k][j]; SDs[j].VexInTree=k; } } return tree; } 4.2.5 算法實(shí)現(xiàn)二：求MST的樹結(jié)構(gòu) // 生成一棵雙親表示法的樹，存于tree中 vector MGraph::Prim1(int startv) { int n=m_Es->size(); vector tree(n-1); vector SDs(n); for(int i=0; i

50、xInTree=startv; SDs[i].Distance=(*m_Es)[startv][i]; } for(i=0; i

51、 tree[i].weight=SDs[k].Distance; SDs[k].Distance=0; // 將頂點(diǎn)k納入生成樹中 for(j=0; j

52、4 -1 8 8 2 4 結(jié)構(gòu)解釋 4.3 Kruskal算法 4.3.1 算法思路 ①盡可能選擇n-1條權(quán)值最小的邊； ②但不能構(gòu)成回路。 4.3.2 算法步驟 ①初始化VT=V，ET={}，即n個(gè)頂點(diǎn)是n個(gè)連通分量； ②選擇權(quán)值最小的邊(Vp,Vq)； ③若Vp、Vq不屬于同一連通分量，將(Vp,Vq)并入ET；否則，舍棄。 ④重復(fù)②③，直至選取了n-1條邊。 4.3.3 連通分量表示與合并 連通分量：采用子集樹的存儲(chǔ)結(jié)構(gòu)。 vector parents(m_N,-1); 連通分量的合

53、并：子集樹的合并。 4.3.4 數(shù)據(jù)結(jié)構(gòu) struct Edge { int v1,v2; double weight; bool operator<(Edge &e) { return weight m_Es; // 有序邊集 public: Graph(int n,vector & es) { m_N=n; m_Es=es; sort(m_Es.begin(), m_Es.en

54、d()); } vector Kruskal(); ………… } 4.3.5 算法實(shí)現(xiàn) vector Graph::Kruskal() { vector tree(m_N-1); vector parents(m_N,-1); for(int k=0,i=0; i

55、ends) { parents[begins]=ends; // 合并子集樹 tree[k] =m_Es[i]; k++; if(k==m_N) return tree; // 找到了全部的樹邊 } } return tree; } // 計(jì)算頂點(diǎn)v所屬的連通分量的編號(hào) int Graph::Find(vector sets, int v) { while(sets[v]>=0) v=sets[v]; return v; } 4.3.6 調(diào)試案例 3,4:1 6

56、,8:1 4,8:2 0,1:2 2,7:2 2,3:2 0,6:3 6,7:3 1,2:4 7,8:4 5,8:5 4,5:6 1,6:6 0,5:7 3,7:8 三元組 begins ends 0 1 2 3 4 5 6 7 8 初始化 -1 -1 -1 -1 -1 -1 -1 -1 -1 3,4:1 3 4 -1 -1 -1 4 -1 -1 -1 -1 -1 6,8:1 6 8 -1 -1 -1 4 -1 -1 8 -1 -1 4,8:2 4 8 -1

57、-1 -1 4 8 -1 8 -1 -1 0,1:2 0 1 1 -1 -1 4 8 -1 8 -1 -1 2,7:2 2 7 1 -1 7 4 8 -1 8 -1 -1 2,3:2 7 8 1 -1 7 4 8 -1 8 8 -1 0,6:3 1 8 1 8 7 4 8 -1 8 8 -1 6,7:3 8 8 1,2:4 8 8 7,8:4 8 8 5,8:

58、5 5 8 1 8 7 4 8 8 8 8 -1 4.3.7 性能分析 設(shè)圖的頂點(diǎn)個(gè)數(shù)為n，邊數(shù)為e。邊數(shù)組已經(jīng)按權(quán)值有序。 空間復(fù)雜度： O(n) “選邊”的時(shí)間復(fù)雜度： 最好O(n)； 最差O(e) “求子集”的時(shí)間復(fù)雜度：最好O(log2n)；最差O(n) 4.4 暢想 Prim算法 適合稠密圖 Kruskal算法 適合稀疏圖 感受“貪心法”：用局部最優(yōu)解，組合全局最優(yōu)解。 第7章 圖 5 最短路徑 約定：路徑長度等于路徑中邊/弧權(quán)值之和；所有邊/弧權(quán)大于0。 5.1 單源點(diǎn)的最短路徑問題

59、 性質(zhì)： 最短路徑由最短子路徑組成。 策略： 由近及遠(yuǎn)計(jì)算到各頂點(diǎn)的最短路徑。 Edsger Dijkstra （1930-2002） 經(jīng)典之作：“GoTo Statement Considered Harmful”。 1972年因發(fā)明ALGOL語言而獲得圖靈獎(jiǎng)，獲獎(jiǎng)演說是“The Humble Programmer”。 在操作系統(tǒng)中，提出了PV操作；…… 5.1.1 問題與對(duì)策 ①如何存儲(chǔ)源點(diǎn)v到其余頂點(diǎn)的最短路徑長度？ vector sds; 初值：sds = (*m_Es)[v]; ②如何區(qū)

60、分已求解結(jié)點(diǎn)和未求解結(jié)點(diǎn)？ vector set(m_N,false); set[i]==true 表示頂點(diǎn)i未求解 set[i]==false 表示頂點(diǎn)i已求解 ③如何表示已求解結(jié)點(diǎn)w對(duì)未求解結(jié)點(diǎn)i的影響？ 若sds[w]+(*m_Es)[w][i]

61、選取與頂點(diǎn)v最近的結(jié)點(diǎn)w，成為已求解結(jié)點(diǎn)； ③借助結(jié)點(diǎn)w，修改從v出發(fā)到其余未求解結(jié)點(diǎn)的最短路徑長度； ④重復(fù)②③步驟N-1次。 案例演示 0,Inf,10,Inf,30,100; Inf,0,5,Inf,Inf,Inf; Inf,Inf,0,50,Inf,Inf; Inf,Inf,Inf,0,Inf,10; Inf,Inf,Inf,20,0,60; Inf,Inf,Inf,Inf,Inf,0 0 1 2 3 4 5 初始化 dist 0 Inf 10 Inf 30 100 set True false false

62、false false false path 第一次循環(huán)后 dist 0 Inf 10 60 30 100 set True false True false false false path 2 第二次循環(huán)后 dist 0 Inf 10 50 30 90 set True false True false True S path 4 4 第三次循環(huán)后 dist 0 Inf 10 50 30 60 set True false True

63、 True True false path 4 4,3 5.1.3 算法實(shí)現(xiàn)一：求最短路徑長度向量 vector MGraph::Dijkstra(int v) { vector sds=(*m_Es)[v]; vector set(m_N,false); set[v] =true; for(int i=1; i

64、set[j]==false && sds[w]+(*m_Es)[w][j] sds,vector set) { double min=Inf; int w; for(int i=0; i

65、 } 空間復(fù)雜度： O(n) 時(shí)間復(fù)雜度： O(n*n) 5.1.4 算法實(shí)現(xiàn)二：求最短路徑向量 vector > MGraph::DijkstraPath(int v) { vector sds=(*m_Es)[v]; vector > paths(m_N); vector set(m_N,false); set[v] =true; for(int i=1; i

66、 for(int j=0; jj最短路徑 A1[i][j]=min(A0[i][0]+A0[0][j],A0[i][j]) 以頂點(diǎn)0、頂點(diǎn)1為中間頂點(diǎn)的i->j最短路徑 A2[i][j]=min(A1[i][1]+A1[1][