




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
第六章圖圖的相關(guān)定義結(jié)點(diǎn)之間的關(guān)系是任意的,圖中任意兩個(gè)元素之間都可能相關(guān)。V是具有相同特性的數(shù)據(jù)元素的集合,成為頂點(diǎn)集。VR是其中任意兩個(gè)頂點(diǎn)之間關(guān)系的集合。ABCDABCED圖的基本術(shù)語頂點(diǎn)有向圖/無向圖子圖完全圖/有向完全圖稀疏圖/稠密圖簡單路徑鄰接點(diǎn)邊/弧/弧頭/弧尾度/出度/入度路徑連通/連通圖連通分量回路或環(huán)強(qiáng)連通圖/強(qiáng)連通分量生成樹權(quán)網(wǎng)圖或網(wǎng)ACDACFGABCDEABCDEFGACDB子圖連通分量強(qiáng)連通分量ABCDABCD圖的存儲(chǔ)結(jié)構(gòu)圖無法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來表示元素之間的關(guān)系。若按度數(shù)最大的頂點(diǎn)設(shè)計(jì)結(jié)點(diǎn)結(jié)構(gòu)也會(huì)浪費(fèi)單元圖的“鄰接矩陣”表示法用兩個(gè)數(shù)組分別存放數(shù)據(jù)元素(頂點(diǎn))的信息和數(shù)據(jù)元素之間的關(guān)系(邊或?。┑男畔ⅰ!徑泳仃嚰僭O(shè)圖G(V,E)有n個(gè)確定頂點(diǎn),則表示G中各頂點(diǎn)相鄰關(guān)系的矩陣是一個(gè)n*n的矩陣
A[i][j]=1<vi,vj>是G的邊
0<vi,vj>不是G的邊若G為網(wǎng),則鄰接矩陣定義為
A[i][j]=Wij<vi,vj>是G的邊
0或∞
<vi,vj>不是G的邊G1.arcs=0110000000011000ABCEDABCDG2.arcs=0110010001100010000101110求頂點(diǎn)的度對(duì)無向圖,vi的度數(shù)=鄰接矩陣第i行元素之和對(duì)有向圖,vi的出度=第i行元素之和
vi的入度=第i列元素之和0507000400600000030040020ABCED5463742鄰接矩陣存儲(chǔ)的特點(diǎn)無向圖的鄰接矩陣是對(duì)稱的,對(duì)n個(gè)頂點(diǎn)的無向圖只需要存入下三角矩陣,即需要n(n+1)/2個(gè)存儲(chǔ)單元。有向圖的鄰接矩陣所需要的存儲(chǔ)單元不一定,需要n×n個(gè)存儲(chǔ)單元鄰接矩陣能很方便地表示出圖中任意一條邊,所以它更適合存儲(chǔ)稠密圖圖的“鄰接表”表示法鄰接表是一種順序存儲(chǔ)與鏈?zhǔn)浇Y(jié)構(gòu)相結(jié)合的存儲(chǔ)方式,類似于樹的孩子鏈表。對(duì)每個(gè)頂點(diǎn)建立一個(gè)單鏈表,第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊。nextarcadjvex表結(jié)點(diǎn)firstarcdata頭結(jié)點(diǎn)鄰接表的表示結(jié)構(gòu)info結(jié)點(diǎn)度的計(jì)算方法無向圖中i結(jié)點(diǎn)的度就是第i個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)。有向圖中第i個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)是該結(jié)點(diǎn)的出度,而要知道入度必須遍歷整個(gè)鄰接表。逆鄰接表
3
∧0
∧0
2
∧
1
2∧ABCD3210
1
1
∧3
∧
0
3∧ABCD
2∧3210ACBD0123ACBD0123有向圖的鄰接表生成算法輸入:V1,V2,……,Vn各值{(i,j),……,(0,0)}若是無向圖,則還應(yīng)在第j個(gè)鏈表中增加節(jié)點(diǎn)i鄰接表最終的形狀依賴于對(duì)結(jié)點(diǎn)的編號(hào)順序以及每條邊(i,j)的輸入順序有向圖的“十字鏈表”表示法可以看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來的一種鏈表頂點(diǎn)結(jié)點(diǎn)3個(gè)域;弧結(jié)點(diǎn)5個(gè)域DataFirstInFirstOutTailVexHeadVexHlinkTlinkinfo這條弧的弧尾結(jié)點(diǎn)的序號(hào)這條弧的弧頭結(jié)點(diǎn)的序號(hào)指向以headvex中序號(hào)為弧頭的下一條弧指向以tailvex中序號(hào)為弧尾的下一條弧頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)ABCD0102DCBA32102023303231∧
∧
∧
∧
∧
∧
∧
∧
0123圖的遍歷圖的遍歷是指從圖的任一頂點(diǎn)出發(fā),對(duì)圖中所有頂點(diǎn)訪問一次且只訪問一次。圖的遍歷比樹的遍歷復(fù)雜得多,因?yàn)閳D的遍歷可能存在回溯。圖的遍歷通常分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式。圖的遍歷是求圖的連通性、拓?fù)渑判颉⑶箨P(guān)鍵路徑等算法的基礎(chǔ)遍歷的實(shí)質(zhì):是對(duì)每個(gè)頂點(diǎn)尋找其鄰接點(diǎn)的過程(時(shí)間復(fù)雜度呢?)①②⑧④⑥⑤③⑦深度優(yōu)先遍歷(DFS)
⑤
⑥
⑧
④
①
⑦
②
③
深度優(yōu)先遍歷的非遞歸算法★★已知該圖的鄰接表Vex注意該算法需要添加輔助數(shù)組Visited[]以區(qū)分已訪問和未訪問的結(jié)點(diǎn)遍歷結(jié)果依賴于頂點(diǎn)編號(hào)鄰接表的結(jié)構(gòu)起始點(diǎn)i的選擇廣度優(yōu)先遍歷(BFS)類似于樹的按層次遍歷的過程。遍歷方法:先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問到;波紋式地由近到遠(yuǎn)訪問,依次訪問和v有路徑長度為1、2、3..的頂點(diǎn)。圖中尚有頂點(diǎn)未訪問到,則另選圖中一個(gè)未曾被訪問的頂點(diǎn)做起點(diǎn),重復(fù)上述過程,直至所有頂點(diǎn)被訪問完為止。遍歷的實(shí)質(zhì):通過邊或弧找鄰接點(diǎn)的過程兩種方法時(shí)間復(fù)雜度相同,僅僅是訪問結(jié)點(diǎn)的順序不同。①②③④⑤⑥⑦⑧廣度優(yōu)先遍歷的非遞歸算法★已知該圖的鄰接表Vex注意該算法需要添加輔助數(shù)組Visited[]以區(qū)分已訪問和未訪問的結(jié)點(diǎn)遍歷結(jié)果依賴于頂點(diǎn)編號(hào)鄰接表的結(jié)構(gòu)起始點(diǎn)i的選擇圖的連通性—生成樹生成樹:從圖的某個(gè)結(jié)點(diǎn)出發(fā),系統(tǒng)地訪問圖中所有頂點(diǎn),遍歷時(shí)經(jīng)過的所有結(jié)點(diǎn)所構(gòu)成的圖。(不形成回路)由深度或廣度遍歷都可以得到圖的生成樹,可見圖的生成樹不是唯一的。圖分為連通圖和非連通圖。連通圖的生成樹是深度遍歷或廣度遍歷得到的結(jié)果,對(duì)于非連通圖則需要從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索。圖的應(yīng)用一—最小生成樹最小生成樹(MST):帶權(quán)的連通圖,其生成樹也是帶權(quán)的,權(quán)值最小的生成樹為最小生成樹。(最小代價(jià))解決的問題:選取權(quán)值最小的邊,但不能構(gòu)成回路;選取n-1條恰當(dāng)?shù)倪呥B接n個(gè)頂點(diǎn)舉例:在最節(jié)省經(jīng)費(fèi)前提下在城市間建立通訊網(wǎng)。普里姆(Prim)算法克魯斯卡爾算法普里姆(Prim)算法構(gòu)造過程:1.初始化T、S為空集,I為所有頂點(diǎn)的集合。從I中任選一點(diǎn)放入S中(S為最小生成樹點(diǎn)的集合,T為最小生成樹邊的集合)2.計(jì)算I-S中各點(diǎn)距離S內(nèi)各點(diǎn)的最短邊3.將距離最小的這條邊添入集合T中,I-S中對(duì)應(yīng)的該點(diǎn)添加到S中4.若圖中所有點(diǎn)均已添入到S中則算法結(jié)束,否則轉(zhuǎn)到第二步繼續(xù)。當(dāng)前形成的集合T,始終是一棵樹,時(shí)間復(fù)雜度為O(n×n
),與圖的邊數(shù)無關(guān),適合稠密圖從V1開始V1V31V64V1V313V2V4V5655V1166V6V34522V64V1V31V42V64V1V31V4V252V64V1V31V4V253V5克魯斯卡爾算法思路:在圖中依次選取n-1條邊,連接圖的n個(gè)結(jié)點(diǎn),每次選取不會(huì)產(chǎn)生回路的且權(quán)值最小的邊。構(gòu)造過程:1.將所有的結(jié)點(diǎn)放入最小生成樹中(初始狀態(tài))2.將邊的權(quán)值按由小到大排序3.按權(quán)值排序的次序選取邊進(jìn)行判定,判定將其添入生成樹中是否產(chǎn)生回路,若產(chǎn)生回路,則不添入,否則添入4.直至添入n-1條邊為止除了最后結(jié)果外,當(dāng)前形成的集合T始終是一個(gè)森林,時(shí)間復(fù)雜主要取決于邊數(shù),適合稀疏圖3V2V565566V11V345V4V62V11V3從V1開始V4V62V11V33V2V5V4V62V11V33V2V5V4V62V11V343V2V5V4V62V11V345圖的應(yīng)用二——拓?fù)渑判蛴邢驘o環(huán)圖:一個(gè)無環(huán)的有向圖,簡稱DAG工程分為若干個(gè)活動(dòng),活動(dòng)之間存在先后順序。 而工程的關(guān)注點(diǎn)在于:工程是否順利進(jìn)行?——拓?fù)渑判騿栴}整個(gè)工程完成所須的最短時(shí)間是多少?——關(guān)鍵路徑問題拓?fù)渑判蛲負(fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的過程。偏序:若集合X上的關(guān)系R是自反的、反對(duì)稱的、傳遞的,則稱R是集合X上的偏序關(guān)系。全序:設(shè)R是集合X上的偏序,如果對(duì)每個(gè)x,y∈X,必有xRy或yRx,則稱R是集合X上的全序關(guān)系。性質(zhì)比較:偏序中僅有部分成員之間可以比較全序中所有成員之間都可以比較AOV-網(wǎng)AOV-網(wǎng)——用頂點(diǎn)表示活動(dòng),用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexNet-work),簡稱AOV-網(wǎng)。AOV-網(wǎng)中不能存在環(huán),因此應(yīng)首先判斷AOV-網(wǎng)中是否存在環(huán)。拓?fù)渑判虻牟襟E1.在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之。2.從圖中刪除該點(diǎn)和所有以它為尾的弧。3.重復(fù)上述兩步,直至所有頂點(diǎn)均已輸出,或當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止;若不存在沒有前驅(qū)的頂點(diǎn)則該有向圖中存在環(huán)。若輸出的結(jié)點(diǎn)個(gè)數(shù)小于有向圖中的結(jié)點(diǎn)個(gè)數(shù),則該有向圖有回路關(guān)鍵路徑★AOE-網(wǎng):與AOV-網(wǎng)對(duì)應(yīng),即邊表示活動(dòng)的網(wǎng)。AOE-網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖在AOE-網(wǎng)中,頂點(diǎn)表示事件,弧表示活動(dòng),權(quán)表示活動(dòng)持續(xù)的時(shí)間,AOE-網(wǎng)通常用來估算工程完成的時(shí)間在AOE-網(wǎng)中,只有一個(gè)入度為零的點(diǎn)(稱為源點(diǎn)),有一個(gè)出度為零的點(diǎn)(匯點(diǎn))。在AOE-網(wǎng)中要解決兩個(gè)問題:完成整項(xiàng)工程需要的時(shí)間哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵關(guān)鍵路徑:從源點(diǎn)到匯點(diǎn)的路徑長度最長的路徑。關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。結(jié)點(diǎn)的最早發(fā)生時(shí)間Ve(1)=0Ve(i)=Max{Ve(k)+Wki}(Vk,Vi)∈ET(總周期)
=Ve(n)
v1v2v3v5v7v8v9v4v6a6=2a2=4a3=5a4=1a1=6a5=1a7=9a8=7a9=4a11=4a10=2Ve(5)=max{6+1,4+1}=7Ve(8)=max{7+7,7+4}=14結(jié)點(diǎn)的最遲發(fā)生時(shí)間Vl(i)=Min{Vl(j)-Wij}(Vi,Vj)∈EVl(n)=Ve(n)=T(總周期)★若Vl(m)=Ve(m),則點(diǎn)m是關(guān)鍵點(diǎn)。v1v2v3v5v7v8v9v4v6a6=2a2=4a3=5a4=1a1=6a5=1a7=9a8=7a9=4a11=4a10=2邊的最早開工時(shí)間Ee(ij)=Ve(i)邊的最遲開工時(shí)間El(ij)=Vl(j)–Wij★關(guān)鍵活動(dòng)即滿足El(ij)=Ee(ij)的邊1814161078660Vl181416775460Ve987654321Ve是某個(gè)事件的最早發(fā)生時(shí)間,從第一個(gè)時(shí)間開始推Vl是某個(gè)事件最晚發(fā)生時(shí)間,從最后一個(gè)事件逆推v1v2v3v5v7v8v9v4v6a6=2a2=4a3=5a4=1a1=6a5=1a7=9a8=7a9=4a11=4a10=2a1a2a3a4a5a6a7a8a9a10a11Ee0006457771614El02366877101614v1v2v3v5v7v8v9v4v6a6=2a2=4a3=5a4=1a1=6a5=1a7=9a8=7a9=4a11=4a10=21814161078660Vl181416775460Ve987654321Ee(ij)=Ve(i)El(ij)=Vl(j)–Wij圖的應(yīng)用三——最短路徑實(shí)際應(yīng)用——交通網(wǎng),中轉(zhuǎn)次數(shù)最少的路線模型抽象:采用帶權(quán)有向圖源點(diǎn):路徑上的第一個(gè)結(jié)點(diǎn)。終點(diǎn):路徑上的最后一個(gè)結(jié)點(diǎn)。從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑
——迪杰斯特拉算法迪杰斯特拉算法
算法步驟:1.假設(shè)S為最短路徑以確定的頂點(diǎn)集,V-S是最短路徑尚未確定的頂點(diǎn)集。D[v]為u到v的最短路徑長度,初始時(shí),將源點(diǎn)u放入S中2.D[v]=w(u,v)
(v∈V-S)3.選取點(diǎn)k∈V-S,使得D[k]=min{D[t]:t∈V-S}4.將k添入S5.重新計(jì)算D[v]值,其中v∈V-S,t∈S:如果D[v]>D[t]+w(t,v)則D[v]=D[k]+w(k,v),同時(shí)修改源點(diǎn)到v的路徑上的點(diǎn)為源點(diǎn)到k的路徑加上點(diǎn)v6.若V-S為空,則結(jié)束,否則跳轉(zhuǎn)到步驟3思路:按路徑長度遞增的次序產(chǎn)生最短路徑找出從V0開始到各點(diǎn)的最短路徑V0V1V2V3V4v5D[i]∞10∞30100路徑020405v1v0v5v4v2v31006020101030505V0V1V2V3V4v5D[i]∞106030100路徑020230405S={v0,v2}更新T-S={v1,v3,v4,v5}找出從V0開始到各點(diǎn)的最短路徑v1v0v5v4v2v31006020101030505V0V1V2V3V4v5D[i]∞10503090路徑0204304045S={v0,v2,v4}T-S={v1,v3,v5}V0V1V2V3V4v5D[i]∞106030100路徑020230405更新S={v0,v2,v4,v3}v1v0v5v4v2v3
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 全息投影技術(shù)概述與應(yīng)用前景
- 新生命課程第三課講解
- 食品熱分析技術(shù)
- 下肢壓力治療技術(shù)
- 人力資源真人匯報(bào)
- 無骨縫紉技術(shù)分享
- 藥品采購平臺(tái)標(biāo)準(zhǔn)化流程
- 企業(yè)安全匯報(bào)總結(jié)
- 企業(yè)消防事故案例講解
- 尚品宅配全屋設(shè)計(jì)解決方案
- 江西省上饒市2024-2025學(xué)年七年級(jí)下學(xué)期期末語文試題
- 2025年小學(xué)生環(huán)??破罩R(shí)競賽題庫及答案
- 2025至2030年中國乙醇行業(yè)市場全景調(diào)研及發(fā)展趨向研判報(bào)告
- 設(shè)備易損配件管理制度
- 叉車維修方案(3篇)
- 顱內(nèi)感染診療指南
- 兒童腺病毒肺炎
- 2025至2030中國UV打印機(jī)行業(yè)市場現(xiàn)狀分析及競爭格局與投資發(fā)展報(bào)告
- 2025至2030中國氫化可的松口服片行業(yè)項(xiàng)目調(diào)研及市場前景預(yù)測評(píng)估報(bào)告
- 消防器材介紹課件
- 可研委托合同(合同范本)5篇
評(píng)論
0/150
提交評(píng)論