歡迎來(lái)到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁(yè) 裝配圖網(wǎng) > 資源分類 > DOC文檔下載  

數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第7章 圖

  • 資源ID:59536243       資源大?。?span id="7jc2bsj" class="font-tahoma">5.80MB        全文頁(yè)數(shù):49頁(yè)
  • 資源格式: DOC        下載積分:16積分
快捷下載 游客一鍵下載
會(huì)員登錄下載
微信登錄下載
三方登錄下載: 微信開(kāi)放平臺(tái)登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要16積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號(hào),方便查詢和重復(fù)下載(系統(tǒng)自動(dòng)生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號(hào):
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開(kāi),此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁(yè)到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無(wú)水印,預(yù)覽文檔經(jīng)過(guò)壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒(méi)有明確說(shuō)明有答案則都視為沒(méi)有答案,請(qǐng)知曉。

數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第7章 圖

第7章 圖1 邏輯結(jié)構(gòu)1.1 定義G = (V, E) V是頂點(diǎn)集,E是頂點(diǎn)間二元關(guān)系的集合內(nèi)涵越小,外延越大與樹(shù)的區(qū)別: 樹(shù)有特殊的根結(jié)點(diǎn); 樹(shù)的結(jié)點(diǎn)和關(guān)系能分成互不相交的若干子集圖的分類: 無(wú)向圖有向圖邊:二元關(guān)系是無(wú)序的?;。憾P(guān)系是有序的。(vi,vj):vi,vj互為鄰接點(diǎn)<vi,vj>:弧頭vj、弧尾viG1=(V1,E1)V1=v1,v2,v3,v4E1=(v1,v2),(v1,v3),(v1,v4),(v2,v3), (v2,v4),(v3,v4)G2=(V2,E2)V2=v1,v2,v3,v4E2=<v1,v2>, <v2,v1>,<v2,v3>, <v4,v3>不予討論的圖: (總能轉(zhuǎn)換為簡(jiǎn)單圖)1.2 基本操作對(duì)整體的操作(遍歷)深度遍歷DFSTraverse、廣度遍歷BFSTraverse對(duì)頂點(diǎn)的操作InsertVex、DeleteVex、GetVex、SetVex對(duì)弧/邊的操作InsertArc、DeleteArc、GetArc、SetArc1.3 常見(jiàn)應(yīng)用信息的組織:家庭照片管理運(yùn)輸問(wèn)題:最短路徑問(wèn)題、最優(yōu)乘車路線問(wèn)題網(wǎng)絡(luò)規(guī)劃:小區(qū)設(shè)店問(wèn)題、區(qū)域連通的規(guī)劃問(wèn)題進(jìn)度組織:工程進(jìn)度管理1.4 概念 思路:考慮圖的復(fù)雜應(yīng)用,提供簡(jiǎn)化問(wèn)題的思路。1.4.1 圖的分類 著眼點(diǎn):存儲(chǔ)結(jié)構(gòu)的選擇。無(wú)向完全圖邊數(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ù)度無(wú)向圖中,依附于某頂點(diǎn)的邊數(shù)入度有向圖中,以某頂點(diǎn)為弧尾的弧數(shù)出度有向圖中,以某頂點(diǎn)為弧頭的弧數(shù)度的應(yīng)用:以下哪個(gè)圖能夠一筆畫完成?為什么? 一筆畫問(wèn)題的本質(zhì):圖結(jié)構(gòu)中的邊遍歷問(wèn)題。 應(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是連通的。路徑長(zhǎng)度路徑上邊/弧的數(shù)目。簡(jiǎn)單路徑路徑中所有頂點(diǎn)各不相同?;芈仿窂街?,起點(diǎn)和終點(diǎn)是同一頂點(diǎn)。簡(jiǎn)單回路除起點(diǎn)和終點(diǎn)外,其余頂點(diǎn)各不相同。1.4.4 有關(guān)連通著眼點(diǎn):將不連通圖簡(jiǎn)化為連通圖。連通圖無(wú)向圖中,任意二個(gè)頂點(diǎn)之間是連通的。無(wú)向圖的連通分量無(wú)向圖的極大連通子圖。強(qiáng)連通圖有向圖中,任意二個(gè)頂點(diǎn)之間存在來(lái)往路徑。有向圖的強(qiáng)連通分量有向圖的極大強(qiáng)連通子圖。1.4.5 生成樹(shù)著眼點(diǎn):將圖簡(jiǎn)化為樹(shù)。無(wú)向圖生成樹(shù)連通無(wú)向圖中,n個(gè)頂點(diǎn)和n-1條邊,構(gòu)成的連通子圖。(原連通圖的極小連通子圖)生成森林不連通的無(wú)向圖中,各連通分量的生成樹(shù)的集合。有向圖生成樹(shù)強(qiáng)連通有向圖中,n個(gè)頂點(diǎn)和n-1條弧,構(gòu)成的單向連通子圖(vi、vj間存在一條路徑)。一個(gè)頂點(diǎn)入度為,其余頂點(diǎn)入度為。生成森林不強(qiáng)連通的有向圖中,各有強(qiáng)連通分量的生成樹(shù)的集合。第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, 01, 0, 0, 11, 0, 0, 10, 1, 1, 00, 4, 2, Inf4, 0, Inf, 82, Inf, 0, 1Inf, 8, 1, 0 0, 4, 2, InfInf, 0, Inf, 8Inf, Inf, 0, InfInf, Inf, 1, 02.1.2 類的定義const double Inf=10000;struct Edge int v1,v2; double weight;class Mgraph / 簡(jiǎn)化版,只存儲(chǔ)了邊/弧的信息。 int m_N; vector<vector<double> > *m_Es;public: MGraph(int n); MGraph(); void Append(vector<Edge> &es); void Output(); int Degree(int k);空間復(fù)雜度:O(n*n)。適合稠密圖,當(dāng)點(diǎn)多邊少時(shí),空間浪費(fèi)多。 2.1.2 (無(wú)向圖的)類的實(shí)現(xiàn)/ 構(gòu)造函數(shù)MGraph:MGraph(int n) m_N = n; m_Es=new vector<vector<double> >(n,vector<double>(n,Inf); for(int i=0; i<m_N; i+) (*m_Es)ii=0;/ 析構(gòu)函數(shù)MGraph:MGraph() delete m_Es; / 添加邊集void MGraph:Append(vector<Edge> &es) for(int i=0; i<es.size(); i+) int v1=esi.v1, v2=esi.v2; (*m_Es)v1v2=esi.weight; (*m_Es)v2v1=esi.weight; / 計(jì)算頂點(diǎn)的度int MGraph:Degree(int k) int n=0; for(int i=0; i<m_N; i+) if(*m_Es)ki!=0 && (*m_Es)ki!=Inf) n+; return n; 2.2鄰接表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<class T>struct VexNode / 頂點(diǎn)結(jié)構(gòu) T data; ArcNode *firstarc; / 指向出邊表;template<class T>class ALGraph int m_N; vector<VexNode<T> > m_Data; / 頂點(diǎn)向量public: ALGraph(vector<T> vs); ALGraph(); void Append(vector<Edge> &es); void Output();空間復(fù)雜度:O(n+e) n是頂點(diǎn)數(shù),e是邊/弧數(shù)。2.2.3 類的實(shí)現(xiàn)/ 構(gòu)造函數(shù)template<class T>ALGraph<T>:ALGraph(vector<T> vs) m_N = vs.size(); m_Data.resize(m_N); for(int i=0; i<m_N; i+) m_Datai.data=vsi; m_Datai.firstarc=NULL; / 添加弧集/ 留意:用不同插入方法,得到鄰接表不一樣。template<class T>void ALGraph<T>:Append(vector<Edge> &es) for(int i=0; i<es.size(); i+) int v1=esi.v1, v2=esi.v2; ArcNode *p=new ArcNode; p->adjvex=v2; p->weight=esi.weight; p->nextarc=m_Datav1.firstarc; m_Datav1.firstarc = p; / 計(jì)算有向圖中頂點(diǎn)i的出度template<class T>int ALGraph<T>:OutDegree(int k) int n=0; for(ArcNode *p=m_Datak.firstarc; p; p=p->nextarc) n+; return n;/ 計(jì)算有向圖中頂點(diǎn)i的入度template<class T>int ALGraph<T>:InDegree(int k) int n=0; for(int i=0; i<m_N; i+) for(ArcNode *p=m_Datai.firstarc; p; p=p->nextarc) if(p->adjvex=k) n+; return n;試題: 計(jì)算有向圖的入度表、出度表; 判斷無(wú)向圖G是否可以一筆畫。2.2.3 擴(kuò)展思考:頂點(diǎn)的維護(hù)問(wèn)題例:刪除指定頂點(diǎn)的結(jié)構(gòu)變化原圖的結(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 headvex; / 弧頭的編號(hào) double weight; ArcNode *tlink; / 指向弧尾相同的弧結(jié)點(diǎn) ArcNode *hlink; / 指向弧頭相同的弧結(jié)點(diǎn);template<class T>struct VexNode / 頂點(diǎn)結(jié)構(gòu) T data; ArcNode *firstin; / 指向入邊表 ArcNode *firstout; / 指向出邊表;template<class T>class OLGraph vector<VexNode<T> > m_Data; / 頂點(diǎn)向量;2.5 鄰接多重表2.4.1 結(jié)構(gòu)圖 無(wú)向圖的鄰接表有50%的冗余。精簡(jiǎn)方法:每條邊對(duì)應(yīng)一個(gè)邊結(jié)點(diǎn)。主要用于表示無(wú)向圖。 鄰接多重表結(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é)點(diǎn);template<class T>struct VexNode / 頂點(diǎn)結(jié)構(gòu) T data; ArcNode *firstedge; / 第一個(gè)邊結(jié)點(diǎn);template<class T>class OLGraph vector<VexNode<T> > m_Data; / 頂點(diǎn)向量;第7章 圖3 圖的遍歷圖遍歷:從某頂點(diǎn)出發(fā),對(duì)每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次。圖遍歷與樹(shù)遍歷的比較:區(qū)別可能回到起點(diǎn)。因?yàn)閳D不能劃分為若干個(gè)互不相交的子圖。算法擴(kuò)展對(duì)訪問(wèn)過(guò)的頂點(diǎn)作標(biāo)記,并加以識(shí)別。3.1 深度優(yōu)先搜索DFS(Depth First Search)3.1.1 算法設(shè)置一個(gè)標(biāo)記數(shù)組,設(shè)所有頂點(diǎn)都未曾被訪問(wèn); 從起點(diǎn)v出發(fā),訪問(wèn)此頂點(diǎn),同時(shí)設(shè)置訪問(wèn)標(biāo)記;依次從v的未被訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)進(jìn)行DFS;(效果:所有與v連通的頂點(diǎn)都被訪問(wèn)過(guò))若所有頂點(diǎn)都已訪問(wèn),則完成;否則,另?yè)衿瘘c(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,03.1.2 算法實(shí)現(xiàn)(遞歸)/ 帽子函數(shù)template<class T>vector<T> ALGraph<T>:DFSTraverse() vector<T> vs,vs1; / 實(shí)現(xiàn)步驟 vector<bool> visited(m_Data.size(),false); / 實(shí)現(xiàn)步驟 for(int v=0; v<m_N; v+) if(visitedv=false) vs1.clear(); DoDFSTraverse(v,visited,vs1); vs.insert(vs.end(),vs1.begin(),vs1.end(); return vs;template<class T>void ALGraph<T>:DoDFSTraverse(int v,vector<bool>& visited,vector<T>& vs) / 實(shí)現(xiàn)步驟 vs.push_back(m_Datav.data); visitedv=true; / 實(shí)現(xiàn)步驟 for(ArcNode *p=m_Datav.firstarc; p; p=p->nextarc) int w=p->adjvex; if(visitedw=false) DoDFSTraverse(w,visited,vs); 思考1:與樹(shù)的遞歸遍歷算法的共性。思考2:時(shí)間復(fù)雜度? 思考3:計(jì)算DFS生成樹(shù)的各邊。思考4:若采用鄰接矩陣結(jié)構(gòu),程序如何調(diào)整?3.1.3 調(diào)試示例紅色邊:構(gòu)成DFS生成森林,稱為樹(shù)邊。結(jié)點(diǎn)中的左數(shù)字:開(kāi)始訪問(wèn)該結(jié)點(diǎn)的步驟;結(jié)點(diǎn)中的右數(shù)字:完成訪問(wèn)該結(jié)點(diǎn)的所有鄰接點(diǎn)的步驟;3.1.4 調(diào)試中的深入思考搜索過(guò)程中,邊的分類: 回邊:子孫結(jié)點(diǎn)指向祖先結(jié)點(diǎn)。 前向邊:祖先結(jié)點(diǎn)指向子孫結(jié)點(diǎn)。 交叉邊:子樹(shù)/樹(shù)之間的邊。應(yīng)用:若在DFS過(guò)程中,沒(méi)有發(fā)現(xiàn)回邊,則該圖無(wú)環(huán)。3.1.5 判斷無(wú)向圖中是否是連通,并計(jì)算連通分量的個(gè)數(shù)int ALGraph<T>:DFSTraverse() vector<T> vs,vs1; int n=0; vector<bool> visited(m_Data.size(),false); for(int v=0; v<m_N; v+) if(visitedv=false) vs1.clear(); DoDFSTraverse(v,visited,vs1); n+; vs.insert(vs.end(),vs1.begin(),vs1.end(); return n;3.1.5 判斷無(wú)向圖中是否有回路/ 不適用于有向圖template<class T>bool ALGraph<T>:HasCircle() vector<bool> visited(m_N,false); for(int v=0; v<m_N; v+) if(visitedv=false) if(DoHasCircle(v,visited)=true) return true; / 存在環(huán) return false; / 所有連通分量中,不存在環(huán)template<class T>bool ALGraph<T>:DoHasCircle(int v,vector<bool>& visited) visitedv=true; for(ArcNode *p=m_Datav.firstarc; p; p=p->nextarc) int w=p->adjvex; if(visitedw=true) return true; / w已被訪問(wèn)過(guò),即發(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中,沒(méi)有發(fā)現(xiàn)環(huán)路3.2 廣度優(yōu)先搜索BFS(breadth first search)3.2.1 算法設(shè)所有頂點(diǎn)都未曾被訪問(wèn);將起點(diǎn)編號(hào)加入隊(duì)列,同時(shí)設(shè)置訪問(wèn)標(biāo)記;取隊(duì)首元素,設(shè)為v,訪問(wèn)結(jié)點(diǎn)v;依次將v的各個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)加入隊(duì)列,同時(shí)設(shè)置訪問(wèn)標(biāo)記; 若隊(duì)列不空,則循環(huán)執(zhí)行,否則;若所有頂點(diǎn)都已訪問(wèn),則完成;否則,另?yè)衿瘘c(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,23.2.2 算法實(shí)現(xiàn)/ 帽子函數(shù)template<class T>vector<T> ALGraph<T>:BFSTraverse() vector<T> vs,vs1; / 實(shí)現(xiàn)步驟 vector<bool> visited(m_Data.size(),false); / 實(shí)現(xiàn)步驟 for(int v=0; v<m_N; v+) if(visitedv=false) vs1.clear(); DoBFSTraverse(v,visited,vs1); vs.insert(vs.end(),vs1.begin(),vs1.end(); return vs;template<class T>void ALGraph<T>:DoBFSTraverse(int v,vector<bool>& visited,vector<T>& vs) queue<int> Q; ArcNode *p; Q.push(v); visitedv=true; / 步驟 while(!Q.empty() / 步驟 v=Q.front(); Q.pop(); vs.push_back(m_Datav.data); / 步驟 / 步驟 for(ArcNode *p=m_Datav.firstarc; p; p=p->nextarc) int w=p->adjvex; if(visitedw=false) Q.push(w); visitedw=true; 思考1:與樹(shù)的層次遍歷算法的共性。思考2:時(shí)間復(fù)雜度? 思考3:計(jì)算BFS生成樹(shù)的各邊。思考4:計(jì)算起點(diǎn)到其余各頂點(diǎn)的最短路徑。3.2.3 調(diào)試示例紅色邊:構(gòu)成BFS生成森林,稱為樹(shù)邊。結(jié)點(diǎn)數(shù)字:距離起點(diǎn)的路徑長(zhǎng)度 3.4 生成樹(shù)、生成森林的存儲(chǔ)結(jié)構(gòu)(擴(kuò)展思考)在遍歷中,如何將生成樹(shù)、生成森林,以孩子兄弟法存儲(chǔ)起來(lái)?圖的鄰接表結(jié)構(gòu)圖的生成森林的二叉鏈表結(jié)構(gòu)3.5 關(guān)節(jié)點(diǎn)、重連通分量(擴(kuò)展思考)3.5.1 概念關(guān)節(jié)點(diǎn)若刪除某頂點(diǎn)及其關(guān)聯(lián)各邊,圖的一個(gè)連通分量將分割為多個(gè)連通分量,則該頂點(diǎn)是關(guān)節(jié)點(diǎn)。重連通分量沒(méi)有關(guān)節(jié)點(diǎn)的連通圖。圖的連通度若在連通圖上至少要?jiǎng)h除k個(gè)頂點(diǎn)才能破壞圖的連通性,則該圖的圖的連通度為k。實(shí)際意義:連通度等價(jià)于系統(tǒng)的可靠度。算法:在DFS生成樹(shù),根結(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; / 當(dāng)前頂點(diǎn)已經(jīng)訪問(wèn)的弧結(jié)點(diǎn)的指針;1.2 與遞歸函數(shù)完全相同的帽子函數(shù)template<class T>vector<T> ALGraph<T>:DFSTraverse() vector<T> vs,vs1; vector<bool> visited(m_N,false); for(int v=0; v<m_N; v+) if(visitedv=false) vs1.clear(); DoDFSTraverse(v,visited,vs1); vs.insert(vs.end(),vs1.begin(),vs1.end(); return vs;1.3 借助狀態(tài)棧的回溯法 / 約定每個(gè)頂點(diǎn)被訪問(wèn)之后,再進(jìn)棧與樹(shù)先根算法的區(qū)別:訪問(wèn)標(biāo)記的處理template<class T>void ALGraph<T>:DoDFSTraverse(int v,vector<bool>& visited,vector<T>& vs) stack<Status> S; vs.push_back(m_Datav.data); visitedv=true; Status s1=v,m_Datav.firstarc; S.push(s1); while( !S.empty() ) Status &s=S.top(); / s是棧頂狀態(tài)的引用 / 尋找v的下一個(gè)未訪問(wèn)過(guò)的鄰接點(diǎn) for(; s.p; s.p=s.p->nextarc) if(visiteds.p->adjvex=false) break; if(s.p) int w=s.p->adjvex; / 頂點(diǎn)w未訪問(wèn)過(guò) vs.push_back(m_Dataw.data); visitedw=true; Status nexts; nexts.v=w; nexts.p=m_Dataw.firstarc; S.push(nexts); else S.pop(); / 以v為起點(diǎn)的搜索已經(jīng)完畢 1.4 調(diào)試案例訪問(wèn)0訪問(wèn)1訪問(wèn)4訪問(wèn)3訪問(wèn)2第7章 圖專題2 地圖著色問(wèn)題2.1 地圖著色問(wèn)題及其邏輯結(jié)構(gòu) 設(shè)一張地圖有n個(gè)區(qū)域,用不多于4種顏色對(duì)這些區(qū)域進(jìn)行著色,相鄰區(qū)域應(yīng)具有不同的顏色。 區(qū)域圖邏輯結(jié)構(gòu)圖2.2 地圖著色判斷問(wèn)題 試設(shè)計(jì)算法,以一種著色方案為輸入,算法對(duì)該著色方案進(jìn)行考察,判別是否滿足著色要求。/ colors0.colorsm_N-1存儲(chǔ)了所有區(qū)域的顏色值template<class T>bool ALGraph<T>:Check(vector<int> &colors) for(int i=0; i<m_N; i+) for(ArcNode *p=m_Datai.firstarc; p; p=p->nextarc) if(colorsp->adjvex=colorsi) return false; return true;/ colors0.colorsn-1存儲(chǔ)了部分區(qū)域的顏色值template<class T>bool ALGraph<T>:Check(vector<int> &colors,int n) for(int i=0; i<n; i+) for(ArcNode *p=m_Datai.firstarc; p; p=p->nextarc) if(p->adjvex<n && colorsp->adjvex=colorsi) return false; return true;2.3 計(jì)算所有的地圖著色方案template<class T>vector<vector<int> > ALGraph<T>:GetAllColors() vector<vector<int> > allColors; / 所有的著色方案 vector<int> Colors(m_N,0); / 當(dāng)前著色方案 GetAllColors(0,Colors,allColors); return allColors;template<class T>void ALGraph<T>:GetAllColors(int i, vector<int> Colors, vector<vector<int> > &allColors) if(i=m_N) / 當(dāng)前著色方案已經(jīng)全部齊備 if(Check(Colors) allColors.push_back(Colors); return; for(int color=1; color<=4; color+) Colorsi=color; / 第i個(gè)區(qū)域設(shè)置為color顏色 if(Check(Colors,i+1) / 剪枝法:檢查局部解的合理性 GetAllColors(i+1,Colors,allColors); 2.3 小結(jié) 本質(zhì)上,窮舉所有的著色方案,是遍歷4叉樹(shù)所有葉子結(jié)點(diǎn)的過(guò)程。效率不高,但配合剪枝法的應(yīng)用,能較好的改善算法性能。作業(yè)與上機(jī)1 圖的鄰接表類建立鄰接表類,深度、廣度遍歷之,盡可能的豐富鄰接表類的成員函數(shù);方向1:計(jì)算生成樹(shù)/生成森林的弧向量,進(jìn)而建立生成樹(shù)/生成森林的樹(shù)的存儲(chǔ)結(jié)構(gòu)。方向2:判別圖中是否存在回路;方向3:計(jì)算頂點(diǎn)之間的最短的路徑長(zhǎng)度;方向4:計(jì)算圖中的關(guān)節(jié)點(diǎn),進(jìn)而計(jì)算圖的連通度;方向5:參照樹(shù)的非遞歸遍歷算法,實(shí)現(xiàn)圖的非遞歸深度遍歷算法。方向6:計(jì)算地圖著色的一個(gè)/所有著色方案。2 圖的應(yīng)用 Prim算法、Kruskal算法 Dijkstra算法、Floyd算法。 拓?fù)渑判蛩惴ā㈥P(guān)鍵路徑算法。第7章 圖4 最小生成樹(shù)4.1 概念最小生成樹(shù):各邊權(quán)值之和最小的生成樹(shù)。原圖生成樹(shù)一生成樹(shù)二生成樹(shù)三4.2 Prim算法4.2.1 算法思路設(shè)圖G=(V,E),從起點(diǎn)v出發(fā),構(gòu)造最小生成樹(shù)T=(VT,ET)。初始化VT=v,ET=;找權(quán)值最小的(Vp,Vq), VpVT, VqV-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)造最小生成樹(shù)。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,Inf, 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), VpVT, VqV-VT;設(shè)計(jì)結(jié)構(gòu):VT外每個(gè)頂點(diǎn)到VT的最短距離。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<ShortDist> SDs;表示所有頂點(diǎn)到VT的最短距離及對(duì)應(yīng)頂點(diǎn)。示例:以V4為起點(diǎn)構(gòu)造最小生成樹(shù),SDs的初始數(shù)據(jù):下標(biāo)012345678VexInTree444444444DistanceINFINFINF106INFINF2SDsi.Distance=0的含義:頂點(diǎn)i已在生成樹(shù)中4.2.3 算法及分析 初始化SDs; 在SDs中,找出Distance最小非0值的下標(biāo)k; (SDsk.VexInTree,k)為生成樹(shù)的邊; k是樹(shù)外某點(diǎn),SDsk.VexInTree是樹(shù)內(nèi)某點(diǎn); SDsk.Distance=0,即頂點(diǎn)k并入生成樹(shù); 若costki<SDsi.Distance,修改SDsi; n-1次重復(fù)。012345678初始化VexInTree444444444DistanceMMM106MM2第一次循環(huán)后VexInTree443444434DistanceMM2006M82第二次循環(huán)后VexInTree423444424DistanceM40006M22設(shè)圖頂點(diǎn)數(shù)為n,時(shí)間復(fù)雜度是O(n2),空間復(fù)雜度是O(n)。4.2.4 算法實(shí)現(xiàn)一:求MST的所有邊vector<Edge> MGraph:Prim1(int startv) int n=m_Es->size(); vector<Edge> tree(n-1); vector<ShortDist> SDs(n); for(int i=0; i<n; i+) SDsi.VexInTree=startv; SDsi.Distance=(*m_Es)startvi; for(i=0; i<n-1; i+) double min=Inf; int k; for(int j=0; j<n; j+) / 找最小非0值的下標(biāo)k if(SDsj.Distance!=0 && SDsj.Distance<min) min=SDsj.Distance; k=j; treei.v1=SDsk.VexInTree; treei.v2=k; treei.weight=SDsk.Distance; SDsk.Distance=0; / 將頂點(diǎn)k納入生成樹(shù)中 for(j=0; j<n; j+) / 修改SDs if(*m_Es)kj<SDsj.Distance) SDsj.Distance=(*m_Es)kj; SDsj.VexInTree=k; return tree;4.2.5 算法實(shí)現(xiàn)二:求MST的樹(shù)結(jié)構(gòu)/ 生成一棵雙親表示法的樹(shù),存于tree中vector<Edge> MGraph:Prim1(int startv) int n=m_Es->size(); vector<Edge> tree(n-1); vector<ShortDist> SDs(n); for(int i=0; i<n; i+) SDsi.VexInTree=startv; SDsi.Distance=(*m_Es)startvi; for(i=0; i<n-1; i+) double min=Inf; int k; for(int j=0; j<n; j+) / 找最小非0值的下標(biāo)k if(SDsj.Distance!=0 && SDsj.Distance<min) min=SDsj.Distance; k=j; treei.v1=SDsk.VexInTree; treei.v2=k; treei.weight=SDsk.Distance; SDsk.Distance=0; / 將頂點(diǎn)k納入生成樹(shù)中 for(j=0; j<n; j+) / 修改SDs if(*m_Es)kj<SDsj.Distance) SDsj.Distance=(*m_Es)kj; SDsj.VexInTree=k; return tree;運(yùn)行結(jié)果:下標(biāo)012345678tree6034-18824結(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 連通分量表示與合并 連通分量:采用子集樹(shù)的存儲(chǔ)結(jié)構(gòu)。 vector<int> parents(m_N,-1); 連通分量的合并:子集樹(shù)的合并。4.3.4 數(shù)據(jù)結(jié)構(gòu)struct Edge int v1,v2; double weight; bool operator<(Edge &e) return weight<e.weight; ;class Graph int m_N; / 頂點(diǎn)數(shù) vector<Edge> m_Es; / 有序邊集public: Graph(int n,vector<Edge> & es) m_N=n; m_Es=es; sort(m_Es.begin(), m_Es.end(); vector<Edge> Kruskal(); 4.3.5 算法實(shí)現(xiàn)vector<Edge> Graph:Kruskal() vector<Edge> tree(m_N-1); vector<int> parents(m_N,-1); for(int k=0,i=0; i<m_Es.size(); i+) int begins=Find(parents, m_Esi.v1); int ends =Find(parents, m_Esi.v2); if(begins!=ends) parentsbegins=ends; / 合并子集樹(shù) treek =m_Esi; k+; if(k=m_N) return tree; / 找到了全部的樹(shù)邊 return tree;/ 計(jì)算頂點(diǎn)v所屬的連通分量的編號(hào)int Graph:Find(vector<int> sets, int v) while(setsv>=0) v=setsv; return v;4.3.6 調(diào)試案例3,4:1 6,8:14,8:2 0,1:22,7:2 2,3:20,6:3 6,7:3 1,2:4 7,8:45,8:5 4,5:61,6:6 0,5:73,7:8三元組beginsends012345678初始化-1-1-1-1-1-1-1-1-13,4:134-1-1-14-1-1-1-1-16,8:168-1-1-14-1-18-1-14,8:248-1-1-148-18-1-10,1:2011-1-148-18-1-12,7:2271-1748-18-1-12,3:2781-1748-188-10,6:31818748-188-16,7:3881,2:4887,8:4885,8:55818748888-14.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 最短路徑約定:路徑長(zhǎng)度等于路徑中邊/弧權(quán)值之和;所有邊/弧權(quán)大于0。5.1 單源點(diǎn)的最短路徑問(wèn)題性質(zhì): 最短路徑由最短子路徑組成。策略: 由近及遠(yuǎn)計(jì)算到各頂點(diǎn)的最短路徑。Edsger Dijkstra(1930-2002)經(jīng)典之作:“GoTo Statement Considered Harmful”。 1972年因發(fā)明ALGOL語(yǔ)言而獲得圖靈獎(jiǎng),獲獎(jiǎng)演說(shuō)是“The Humble Programmer”。 在操作系統(tǒng)中,提出了PV操作;5.1.1 問(wèn)題與對(duì)策 如何存儲(chǔ)源點(diǎn)v到其余頂點(diǎn)的最短路徑長(zhǎng)度? vector<double> sds; 初值:sds = (*m_Es)v; 如何區(qū)分已求解結(jié)點(diǎn)和未求解結(jié)點(diǎn)? vector<bool> set(m_N,false); seti=true 表示頂點(diǎn)i未求解 seti=false表示頂點(diǎn)i已求解 如何表示已求解結(jié)點(diǎn)w對(duì)未求解結(jié)點(diǎn)i的影響? 若sdsw+(*m_Es)wi<sdsi,則 sdsi=sdsw+(*m_Es)wi; 圖的存儲(chǔ)結(jié)構(gòu)采用哪種形式? 因需要多次隨機(jī)讀取邊的信息,所以采用鄰接矩陣。5.1.2 算法步驟 根據(jù)源點(diǎn)v,初始化sds、set; 在已求解結(jié)點(diǎn)集中,選取與頂點(diǎn)v最近的結(jié)點(diǎn)w,成為已求解結(jié)點(diǎn); 借助結(jié)點(diǎn)w,修改從v出發(fā)到其余未求解結(jié)點(diǎn)的最短路徑長(zhǎng)度; 重復(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,0012345初始化dist0Inf10Inf30100setTruefalsefalsefalsefalsefalsepath第一次循環(huán)后dist0Inf106030100setTruefalseTruefalsefalsefalsepath2第二次循環(huán)后dist0Inf10503090setTruefalseTruefalseTrueSpath44第三次循環(huán)后dist0Inf10503060setTruefalseTrueTrueTruefalsepath44,35.1.3 算法實(shí)現(xiàn)一:求最短路徑長(zhǎng)度向量vector<double> MGraph:Dijkstra(int v) vector<double> sds=(*m_Es)v; vector<bool> set(m_N,false); setv =true; for(int i=1; i<m_N; i+) int w = MinCost(sds,set); setw=true; for(int j=0; j<m_N; j+) if(setj=false && sdsw+(*m_Es)wj<sdsj) sdsj=sdsw+(*m_Es)wj; return sds;int MGraph:MinCost(vector<double> sds,vector<bool> set) double min=Inf; int w; for(int i=0; i<m_N; i+) if(seti=false && sdsi<=min) min=sdsi; w=i; return w; 空間復(fù)雜度: O(n) 時(shí)間復(fù)雜度: O(n*n)5.1.4 算法實(shí)現(xiàn)二:求最短路徑向量vector<vector<int> > MGraph:DijkstraPath(int v) vector<double> sds=(*m_Es)v; vector<vector<int> > paths(m_N); vector<bool> set(m_N,false); setv =true; for(int i=1; i<m_N; i+) int w = MinCost(sds,set); setw=true; for(int j=0; j<m_N; j+) if(setj=false && sdsw+(*m_Es)wj<sdsj) sdsj=sdsw+(*m_Es)wj; pathsj=pathsw; pathsj.push_back(w); / 調(diào)整路徑 return paths;5.2 多源點(diǎn)的最短路徑問(wèn)題方法之一:重復(fù)Dijkstra算法,時(shí)間復(fù)雜度為O(N3)。5.2.1 Floyd算法思路 N個(gè)頂點(diǎn)的圖種,最短路徑的長(zhǎng)度小于N。 頂點(diǎn)i到頂點(diǎn)j的最短路徑:每個(gè)頂點(diǎn)都可能成為中間頂點(diǎn)。無(wú)中間結(jié)點(diǎn)時(shí)的最短路徑A0ij=costij以頂點(diǎn)0為中間頂點(diǎn)的i->j最短路徑A1ij=min(A0i0+A00j,A0ij)以頂點(diǎn)0、頂點(diǎn)1為中間頂點(diǎn)的i->j最短路徑A2ij=min(A1i1+A11

注意事項(xiàng)

本文(數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第7章 圖)為本站會(huì)員(da****ge)主動(dòng)上傳,裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請(qǐng)重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!