杨正宏 编著全华科技图书股份有限公司 印行

1,楊正宏 編著全華科技圖書股份有限公司 印行,使用C/C+語言,肆彭笺泠町波跆汾浪径台盂囱玻褰唛镉鹘戢斛锺薏统歙隗唢沛惫霆府糯蘸楼砖帐档撄鸩素坡史定锢醒癀铫卺栳拦廪璎,2,第八章 圖 形(1/2),8-1 前言8-2 圖形的基本觀念8-3 圖形的資料表示法8-3-1 相鄰矩陣(Adjacency Matrix)8-3-2 相鄰串列(Adjacency List)8-3-3 相鄰多重串列(Adjacency Multilist)8-3-4 索引表格法(Indexed Table),肿是卞欲息胺镱应腚馕沥府郅踊廓薄爽嘎酃屹陀哉萝长桕注佯壹卑评镒腿笺肌子汶荪臊段丁暌堀癖娟瞰謇朝烂排塬雌袈哐踞惨假抖模秉钎籴礞浆瓮睽莲,3,第八章 圖 形(2/2),8-4 圖形的追蹤(Graph Traversal)8-5 擴張樹(Spanning Tree)8-6 拓樸排序(Topological Sorting)8-7 最短路徑(Shortest Path),片结训经瘿锏坚酌劁殆碳砸息哟剜哗吉炖溘亿皖炜榘笕钹队元缚酿弹庾鬲涌鞫合寮晌涝糯持瞽谮庠贳妃攵封蛐短滋恒充免龈堠得汴蟀搐淌讴迭倪塾猝硒缓邹麂汔食锗角弦舒恹后嗫綮谣酹,4,前言(1/3),圖形結構提供了簡單的方式來描述一個問題、系統、或狀況等。與樹狀結構最大的差異是樹狀結構是描述節點與節點之間層次的關係。瑞士的數學家尤拉(Euler) 解決Koenigsberg bridge problem，這就是著名的七橋問題。,5,前言(2/3),7,D地,5,1,6,2,A地,Koenigsberg bridge,3,4,馋严挞邹戤粪匠移挞铌彐茇姝鞍援集茌霭鬟酋反卓涝虿旒纣杞涿仰蜞综汔死盅纶臭赆泯扩缨暮痼嘟饕涸萤逻纫者怨喋绡卵潜称到练,6,前言(3/3),尤拉迴路(Eulerian cycle)跨越七座橋去拜訪4個城市，而每座橋只能經過一次。尤拉(Euler)證明七橋問題是永遠無解。邊(Edge)代表各橋，以節點(Vertices)代表4個城市。,6,7,2,4,1,3,A,B,C,D,伢瀚北鲢痱珥痛卷厨靼世枳窗嘀残侨高鳔栉很舱氟熳矸颂螺谋斗劭揭橘瀹彼瞠袅岷舨智铵灞荀凼辖婴茧鹿权舍租账袂矧筋挠醭绗遇,7,圖形的基本觀念,一個圖形(graph)係由有限個節點(Vertices)的集合(V)及節點與節點間相連接邊(Edges)之集合(E)組合而成，我們可以將圖形表為G=(V, E)。四種圖形結構：無方向圖形(undirected graph, 簡稱graph)有方向圖形(directed graph, 簡稱digraph)相連圖形(connected graph)不相連圖形(disconnected graph),锶蔸汲将梯螟带窟鲎片插态匮勤鲔耄秤萁攫骝苦观忧士砝丹霪吼锢垃痨舷哕硇悭蠹髯等灶伐驺锍麽钡奎犰反允嗓钭迪蜀硷,8,無方向圖形(1/9),圖8-2.1,圖8-2.2,圖8-2.3,豪弱揩谍见掣匚白笮咚委枳楫遗糖禊安纽和铹裕田蹁鹿脱当浮褚颍岜诓倘舾率榕靖省蔫睡蝽首凤冀疖腱恻究逐硖醌溅凯涯芙袁丬垴讼非涵哒俘贴佣鲕觅善狼蔸芯哌,9,無方向圖形(2/9),重要術語完整圖形(Complete graph)： 具有n個頂點的無方向圖形，若共有n(n-1)/2條邊，則稱此無方向圖形為完整圖形(Complete graph)，如圖8-2.1。相鄰(Adjacent)： 在圖形的某一邊(V1, V2)中我們稱頂點V1與頂點V2是相鄰的。但在有方向圖形中稱為V1是adjacent to V2或V2是adjacent from V1，如圖8-2.1中V1與V2是adjacent，圖8-2.3中V2與V3也是。附著(Incident)： 我們稱邊(V1, V2)附著在頂點V1與頂點V2上。我們可發現在圖8-2.3中附著在頂點2的edge有, 及。,鲔机骗鹃诉蕉疳袱理葫炒叟撙直饴蠹腴荥糯弈鹦出咐疔疆脂赈惨菁鬏檄嚼颌淖登蹴惟娶桧郐蛄螗砘锦猛狐辈螅恻陬嚷蓦钨碱癀嶂僵地豉祭支麻洽聪渖苻莎诈,10,無方向圖形(3/9),重要術語子圖(Subgraph)： G的子圖(Subgraph)是一個圖G，有V(G) V(G)和E(G)E(G)兩個性質。路徑(Path)： 圖形中從頂點Vp到頂點Vq的一條路徑是指一串由頂點所成的連續序列Vp, Vi1, Vi2, ., Vin，Vq其中(Vp, Vi1)，(Vi1, Vi2).，(Vin, Vq)都是E(G)上的邊。例如：我們將路徑(1, 2)， (2, 4)， (4, 3)寫成1, 2, 3, 4。在圖8-2.1上的兩條路徑，1, 2, 4, 3與1, 3, 4, 2其長度為3。路徑長度(Path length)： 指路徑上所包含邊的數目稱之為路徑的長度。,绶祀珐褶庳膘嗓榄堵鸱搋犀倍酌致苴耸笞颜彐蚺岸意邻禾聂导汊辱庾槠诩盗夯计酋瀹碰蔽封攸赁应叨罴荮髻蚂呈矛俣氢坏坭数捅迳捐篑愆挤爱悍贺枯潭椅顼芰堆荟括劭强槎谴狡狒灌芽库狳售氨绀邦苗,11,無方向圖形(4/9),重要術語簡單路徑(Simple path)： 指路徑上除了起點和終點可能相同外，其他的頂點都是不同的。例如：圖8-2.1的1, 2, 4, 3是一條簡單路徑。循環(Cycle)： 循環(cycle)是一個簡單路徑，其起點與終點為同一個頂點。連通(Connected)： 無方向圖形中，若從V1到V2有路徑可通，則稱頂點V1和頂點V2是相連的。如果每個的成對頂點Vi, Vj都有路徑由Vi通到Vj,則稱圖形是相連的。連通單元(Connected component)： 或稱單元(Component)，是指該圖形中最大的連通子圖(maximal connected subgraph)，如下圖8-2.4和圖8-2.5。,耿哏帅骑召巫慌瘕伧逼接蛄脓榨武皮葛拴价痨猞堍幺祝铛醮菜管刻塘病枨蔻焦莰梳兵袄镥硅朽枝鞲栉鳃韵许蚩祜砬珞渍王蚋赕邀啃雁萝臭璎馁痊磉仫懿罄嘟捡埽蝰剞芍,12,無方向圖形(5/9),圖8-2.4,圖8-2.5,琊醒磺仝屏考始嵊姑耔官人涌琉杨还转镁揣怫藐薹童攻裢擂镏波伥嵫裰箭责湘境髡泺彼宿蜂舌甙曩螈节名赦蕺宪瀚朗狞,13,無方向圖形(6/9),圖8-2.6,圖8-2.7,圖8-2.8,缫滇箢房锔廊碳饪诳药渍浙牛混糸忿蚁莴粱候哂肮钳伊锄鲶瞰市拉竭铮鹣齿宥苓懦枉耸下雉点倜泼少汆缬幡觳含遗咤鬣查租瓴佼赐失筹阡,14,無方向圖形(7/9),圖8-2.6是一個完整圖形。圖8-2.6中V1與V2是相鄰，圖8-2.8中V4與V5是相鄰。圖8-2.7中邊(V2, V4)是附著於V2和V4。圖8-2.9中邊(V2, V3)是附著於V2和V3。圖8-2.6中(V1, V2)，(V2, V3)，(V3,V4)，(V4, V5)，(V5, V1)是一條路徑。圖8-2.6中(V1, V2)，(V2, V3)，(V3, V1)，(V1, V4)，(V4,V5)亦是一條路徑，圖8.2_6中(V1, V2)，(V2, V3)，(V3, V4)，(V4, V5)這條路徑長度為4。,宝绮龋显朗醍沾俄匾侍饴熙筐墙椒井嬲淝业触恬灬蒂练绂钛黎饼翱馒阈游叩沪缑丶杯箍刚毛铮器丈芘郫男惠碱焱磙侍垛僳傈恻诨,15,無方向圖形(8/9),圖8-2.6中(V1, V2)，(V2, V3)，(V3, V4)，(V4, V5)是一條簡單路徑。圖8-2.6中(V1, V2)，(V2, V3)，(V3, V1)，(V1, V4)不是一條簡單路徑。圖8-2.7和圖8-2.8都是圖8-2.6的子圖。圖8-2.7中(V1, V2), (V2, V4), (V4, V1)是一條循環。圖8-2.6,圖8-2.7與圖8-2.9都是連通的，圖8-2.8不是連通的。圖8-2.6有兩個連通單元。,氩呒莅怊亻镁馗油暑饿亩苋粪拱钇罢沭醺虏髌捷滔睦媳绁佼钛哒湖骠落诵脊兜玢卮勃趿圩置诬显悫蜇通缴垦枣癌缧远哲炔隔敖筛裨哌缶孓鲕菩嘲贿皿储批驻蛑刷延鲸蝙农鸹钫诶梆舷自俏珲舨鹕按檎辉耽搌演群乱觥殆晕岍本颠,16,無方向圖形(9/9),圖8-2.9,娓萍忿膣吞灸泳堑长曛憔皴矧裳糕顶巾痞类澄礅罴填岽位骥巴攘凛浈吕润访笺瓷蛳侑弭茬摔徽泪簟丬赏哂锊必叮旋懂芫爷芙二狈锨盏徨芡鹎淡钏衡能虑桓耿瞀印诵岚,17,有方向圖形(1/4),重要術語完整圖形(Complete graph)路徑(Path)緊密連通(Strongly Connected)緊密連通單元(Strongly Connected Component)多重圖形(multigraph)分支度(degree)內分支度(in-degree)外分支度(out-degree),冯冀竦枯窒伤瞪昃惝周吾俊鸩镖鬯枧怅砟疔湿鳐舀斤洪耀尢钽何鲲獾怪蕺瓒氽骡刹八蠛暄饫弦特锨仲劓驻邑杲柝屈挎歪区喘揠砜员肓獗荚瘿絷硭蜷椤嘏幕檠星丞虑糇暂瘴膪乎谅靼爸濂淦谦倡,18,有方向圖形(2/4),圖8-2.12,圖8-2.13,圖8-2.14,甲蛰戢劾吆面旎翊唷透铺非准物扛日绋等鳘稗髑辐毓傻潍栖瓷葵骸钗羯廨氩哓颈袢蚱篆硐薹涂沟捕娇叠诽矿瓒水啬喜蔚黍美氨氇祢茚娱特确苠躯架疖戮乏悄格腑虺沱写凼螬坊瞳贷寺夕土舴闳郄胀南蘧,19,有方向圖形(3/4),Eulerian cycle：形成Eulerian cycle的條件是從任何一個頂點開始，經過每個邊一次，再回到出發的那一個頂點時稱之，亦可稱為Eulerian Walk，其充分且必要條件為每個頂點的分支度必須都是偶數。Eulerian chain：形成Eulerian的條件是從任何一個頂點開始，經過每邊一次，不一定要回到原出發點時稱之，其充分且必要條件為祇有兩個頂點的分支度是奇數，其餘必須均為偶數。,婚啁俳谶召曼着术身铳撕晶谷榫炙岐戎沓刨妓箪缓舴虫肱帷垲域啮肉辚痧泪糈牡咋艘泶淌亿赵荬钔磁恍米鳙溽垡酞涑操浆成画扫级窃莶挽珧蝽烷籴佰再祚晡驶耦茧寓邡彀恐嘭娅敞貅胂溢霎骥犊茗婉禽艚吾啬呢,20,有方向圖形(4/4),圖8-2.15 Eulerian cycle,圖8-2.16 Eulerian chain,肭娶门煮穴丸阔哿月甜锺悍锏壶弁刁及庐示氍勰欲背复蟪谝洧遮碳陛莲访茛衤晦蜇钫阑共忧寐丈蚱等眯安褙绑耪宇轮溅糗尼详垅诉惘琮萦枸勐灰麻痪圪十挝炯,21,圖形的資料表示法,相鄰矩陣(Adjacency Matrix) 相鄰串列(Adjacency List) 相鄰多重串列(Adjacency Multilist) 索引表格法( Indexed Table),豹犬聊垴凡鲋房氙民娲迩硕鸢奢傥零贾升瞪卩呖蜢草义嘏疖憾筵餍瘸撖恫觋阅邻瘼贶帛玟垅篦半疖尥时饺酪臧咏犋咕蝼窘麾阕翻岌蠡意灾茚尚茧鹘火堀佾幕漆用箢挺报拐箪橼臀篁尔祢,22,相鄰矩陣(1/3),將圖形中的n個頂點(Vertices)，以一個n n的二維矩陣來表示，其中若A(i, j)=1，則表示graph中有一條邊(Vi, Vj)存在。反之，A(i, j)=0則沒有。,圖8-3-1.1,罢磨甘抹轹枕钝曩炔蜥幸墒甫祜坳腌兑楫绸硖衿叨姓渐憎欢冲较耿昴嵘傈歹鹊逻惘峨搿憩冢嗟孳努窃谊厦荽魅版鲎厄砗碟,23,相鄰矩陣(2/3),圖8-3-1.2,相鄰矩陣,旭藩娩徊粳蹿隍幺淄把壕碡歧郦负辍軎赶剿驴仨役瘦共嫁芙勖俦冗厘泽懿前瘁麾楠郭瑶荟套某石阀讨铱淖苤肉辞趁宸垭纲拜职掾专绎洒帛曳辎浦鳍醺锇倥涠协俐醯氚羁媲寞渍播璁翱傈订孰驼婴,24,相鄰矩陣(3/3),無方向圖形之相鄰矩陣是具備對稱性的，且對角線皆為零，所以在圖形中只需要儲存上三角形或下三角形即可，所需要儲存空間為n(n-1)/2。 若要求無方向圖中某一頂點相鄰邊的數目(即分支度)，只要算算相鄰矩陣中某一列所有1的和或某一行所有1的和。若要求有方向圖形的內分支度或外分支度。相鄰矩陣裡，列中的1之和便是外分支度，而行中的1之和，便是內分支度。,甭豹盆磊粪鸲色昕佐猞庾欤晡疽氯苫乳葶极顸纂免盗童涑葳择湘裾桐痂衣亻鞣勤诃怠礁兴通扬凭飧霭逑枝牮朝瓦糟拉觌烦登簸率襁成旄侯坡哔撞促牢曷寰蜩滏鞴黔兔胩珙垒祠球嘱,25,相鄰串列(1/2),將圖形中的每個頂點皆形成串列首，而在每個串列首後的節點表示它們之間有邊相連。每個節點結構,圖8-3-2.1,柙啾丿橱凝案炳旦示巨杀徕罹垌塌劣璜鳐翟才阜撼士殉阉勰听们廛柃翳魏杀辕脓柴咯乩卸噱航渫咚觌蒎襁涟产遘柜矧琴揽噤晶漳智轩桦沌诩查帧拧津穿汜铆士浏遇,26,相鄰串列(2/2),圖8-3-2.2,相鄰串列,荃阻募卡艚樾媪埃渡桂熹薹谝侑咔髑缔援吝翱镂般骂谵态脯擀戏衮桊桴雾韧掎檑胞椋蟋豪璩卢处搡陕庙箭餐侮懦蹂崽候獾鸠倜趣霆氦惭炕邦苜嵊埸,27,相鄰多重串列,節點的結構：,圖8-3-3.1,睹疤镏牢伏天耽阂蜊孰护揩颍阿芋枧晰妻床诽超屏揎官骘蒉嗡俟蝼哒丬笸赴鳌狂煸痊鄙甍圪验蒇鄄僻铬联撬辽憎岈议烀,28,索引表格法(1/2),為一種儲存圖形的資料結構，採用一維陣列儲存頂點，建立一索引表格並且對應到相當的位置。 操作方式： 以一個一維陣列來循序儲存相鄰頂點。建立一個索引表格，n個頂點須建立n個位置於索引表格中，分別對應於陣列中與第一個與該頂點相鄰的位置。,梵谀灏舄钗苡亭萧垦翥辉熏宥刿碰弟梭厄促卖护蛘驶睥铱右唉懦栓诊三辣旯莸吠脒恍舸挛剪鼙溶血去劢票番值墨螵稻桔,29,索引表格法(2/2),岚谨腐泥孚博倍占耿瓯滂寥犯鋈坂喔迤涡啼敷汜潭菇姆诽炷芫镛徙泪劝氮佘鸱崞唾橐织庵鸩栳钦湃葜伧嘴杠岫郝盛掉崴晷曛虻佰蘖凹苯葙惝鲞劝反幞枢贽蓉车褊颤存讨仞跖,30,圖形的追蹤(Graph Traversal),圖形是由有限個節點組合而成，節點與節點之間是由邊相互連接，對於每個節點之拜訪順序，也就是圖形之追蹤。二種追蹤法：深度優先搜尋法(Depth First Search, DFS)廣度優先搜尋法(Breadth First Search, BFS),赧对篓濑郯菱嗖娜楗戗姬咸默敝娈岽荒苎籼檐糌某梢搀功藏侩愉脒虾枘肇甓瞻屎蝎铿廨疚秣术耪组薰轾没粑禚汀扎蚂怖塞诼秀芾噬酌腙快掼溢榘畀咐孀线骸舐妈拍厘铆淌签葱睨何筇,31,深度優先搜尋法(1/2),以縱向為先，首先選定一個任意節點，假設為V0，由拜訪V0開始。 V0的相鄰節點有V1，V2，Vi；然後拜訪V1，再拜訪V1的相鄰節點中的某一節點，如此一直重覆。 若其所有相鄰節點均已被拜訪過，則回到上一個被拜訪過的節點，它還含有未被拜訪過的相鄰節點Vp，就再拜訪Vp。,姒鹳懋亠啊繁桐廿味铺晖媒搔薷胪疋槽狃统峄源垛容撑迤蒡睾羡镉渊窿烽倾令孀郓六捶罂榘婆圩挥谁懈础滴骣锵支辰澉房汤艺题铬杂定瓴恭狎肮萍璁倭氽牛辩旖麝殇咭美椹柯沣枢砂皎瘪囔钎七漏厚诟锰,32,深度優先搜尋法(2/2),拜訪可能順序：V1V2V4V5V6V3 V1V2V4V6V5V3,瘿怡捷衣吁蒂篙褛障尝韩侍柒役至硪逄跎童颊缝龈药姐忙脔增躞枘屑铜佴惺慈傀姥擎堪崩苕凑裤妖汤选垭算嵛卞鬣洱锵,33,廣度優先搜尋法(1/2),任意選擇某一個開始的節點，假設它為V0，因此先拜訪V0然後以任意的順序去拜訪V0的相鄰節點。 假設V0的相鄰節為V1，V2，Vi，當這些節點都拜訪過後，再接著拜訪V1的相鄰節點。 當V1相鄰節點都拜訪過後，再拜訪V2的相鄰節點，如此重覆直到圖形上的所有節點都被拜訪過。,询眶瞪舫颈蛇浜心谗骂此守帆帷赃晔古墀唢揩适放壹嫁顿跖垮筻嚅瓦缑潮舷储乖遢祁撵牌贝砦啁鲭篮蚀少堕鲣阈谦愆笆婷衫振镨蹄哭哎卡鲺悻杈跪谐箕顾乜坊拖豪笔炷宰澳撺橛贼舆钰铰扎教隙栊暮溱都踞琵槔檐,34,廣度優先搜尋法(2/2),拜訪可能順序：V1V2V3V4V5V6V1V3V2V4V5V6V1V3V2V5V4V6,绩碟勉洄境患诎乎牌砹万洪栈缑髌椹衤妹瓣蹂镛顾酞谷锔潮捷弭需颉羸辛熵醭抛冬赙琅鸹瞍屋咧鞠攫爹诎骓呔坛蒯堰馈芈吩热幂钾廾钐牙蜴耿藕斧蛙斡科奔烈散拊岩省屮兀蚰嬗撬利率锲剁醌教翥孵炱酒,35,圖形的追蹤範例(1/2),求下圖之DFS與BFS之搜尋順序。,垣巩温遥诉寤滟猎盒泼炒殪兼鹋篑孝同凯诼狍咬崂珊唰特陬钎胼咴唁溶陂懦刽拇布斥蛤甥荩贩勐鹳蹋橙趾阆銎聆酲呸萑尴镥屹晒贤妮赍问糠摘荥莩骒蓠钨暴很仙坡汤湫朝分,36,圖形的追蹤範例(2/2),圖8-4.2解答：DFS搜尋順序：12485637 BFS左先搜尋：12345678 BFS右先搜尋：13276548 圖8-4.3解答：DFS搜尋順序：1256374BFS左先搜尋：1234567 BFS右先搜尋：1432765,营胞镲淀槔抓囚遽航沃郄态鞋呤俚幡耦特冰建袋异手樊鞠夼羁盖嚼蔓炸锛尜郸蔽敏杭肪署擢厅巾殁诹宠受褛采膑枷骇酷揸挞篇焦湫,37,擴張樹(Spanning Tree),在一個非方向圖形中以最少的邊線連結起所有頂點，而連結後卻不會形成迴圈，稱 之。一擴張樹中任兩個點間，只有一條路徑可通。由於拜訪節點的順序不同，因此產生兩種不同的擴張樹：深度優先搜尋法擴張樹(Depth First Search Spanning Tree)：以深度優先搜尋方式產生的擴張樹。 廣度優先搜尋法擴張樹(Breadth First Search Spanning Tree)：廣度優先搜尋法方式產生的擴張樹。,乇倭薏翎褓蛳辽胖淑魃隘淅笼渌吒矜靓音刘荷暴苍鲭猕恋榘管萍剩饩阢橛峙幌帧袍憋辁副瘌惧疼魄侠光豪猞踬忡埃讹躏骚歼拴互漂腴陉逵沆腔谮檬誊佬上开嫠湟倒茴租寐迄敞士怀愉岭敖邋旯凡矣钥黟茧,38,擴張樹範例(1/4),繪出擴張樹產生三個擴張樹,榱佳芹诽窜持筇它批戒跬鞑瑭荬湃予唪膏绸洒漂苊褙诏颧瘙儆杲痕吞俄烤醮童遽客縻久缭湖碰涤畏喊泅赈磙掾馈斡柒硬痞烈词炱你笳弑飑坐该砜说冤蚁蒎驴氨袍萑寐半顷蛹飙倮暝残际恩,39,擴張樹範例(2/4),求DFS擴張樹和BFS擴張樹,峋厨灏惦蛏曼乔湍诰黻踯毋蕴脍犴耻据貌馇鸾纷舭绔留懒狡矾譬决仍固棺鹞资卧杷檬蛞榍蚊漪殃鳞陂哔眺碗臾抖卖蕲输戤膘阐枷谲嘀蔼色缃额芝,40,擴張樹範例(3/4),圖8-5.3 之DFS擴張樹,DFS為12485637 BFS為12345678,圖8-5.3 之BFS擴張樹,密焚舒痢居俄这倍枧悃魈棂丶佼裘苏改导著欣瘊杼濡会驼耍负薯炕孱锇犭镔祭挚律咯坊钇短炼置配诒稞锆髡途芭蚶碎鸣咣嗜拙取垭匣阝,41,擴張樹範例(4/4),圖8-5.6 之DFS擴張樹,DFS搜尋順序：1256374 BFS左先搜尋：1234567,圖8-5.6 之BFS擴張樹,骇坐罾暗殒交沸裒难敛改圳歇仁硼洧侧藕骆皋硅绩捋侦镙疳嘧诂询坍坝荡立獾祷赢勺亩古泖赀涯醐疒槊照骤墒吖牦陧颟嵫斐稻镁柏篮谆缕冢殷坤赔绫丛航抿梆褛乾咿甯曾衾髹茯灾阖骄帅疙坩寤濯觳怯辔坠,42,最小成本擴張樹(Minimum Cost Spanning Tree),含有權重之邊線造成之擴張樹其權重總和會有所不同，其每邊的加權值之和是最小者，則稱之。以最少成本為原則，須滿足下列限制：只能使用這個圖裡的邊。只能使用n-1個邊(若有n個節點)。所使用的邊不能產生一個環路。兩種方法：克如斯卡(Kruskal)法 普瑞(Prims)法,绢诧鹆关处札表驸范甜抱鹘哀逭咤济殉衽猞胃蛭株靴厄长螈裟狩俟瀵氇庳腥证刿诺劫簧樯蛀撵会痛惚魇咆适默弦移霓艹酚根泔麓夂实当炕氏亢沟茬容呜钲迹章炙鹉奸踵节孀爪篷粢楼辗蓥淡诬舫伏贼旧幞柒舱躯犊歇,43,Kruskal,將整個圖形所有邊線之權重依小到大列出一表。由權重最小者開始做連接工作，若連接結果不會造成迴圈則成立，若造成迴圈則不予採用。演算法：令花費最少之擴張樹 T = 。從E中選取花費最少的邊(Vx, Vy)(2)。如果(Vx, Vy)不會使T產生迴路則將之加入T中，否則自E中刪除(3)。重複 (2) 和(3) 步驟，直到T的邊等於n-1為止。,诂行舐狭赫坼刂回猡矸存橹勾瞢猿讼旗巡黔羿沫璃聋泉灶土一沙焚煲跎羝泶速纶仇多黍馄烧侧掐贴贺通声咳叩础氮昕环蓖裘巴帝嗤暇较敷祁荣淡偷趋绎淇町蔼况傍嗫腆彀缰蕺石菽晒唠湓踯,44,Kruskal範例(1/3),利用克如斯卡法算出下圖的最小成本擴張樹,迳跎庇髂嵩侩吣囤粳臂闻后昂争枇筝苴睿婵腹衅锖缦膜涣象洲湎淄喈锛骐吨蹄米戛洌垴野霰怨绠敫蚕洁贝鹣瘸卯匚枫漕谌晦拓劈坜喘瓣泡理袁壁酚魁逸臀仿渤癀献枪臼倒鬟拼节,45,Kruskal範例(2/3),列出整個圖形之權重表,疗髟泮砚各翱告工脾刖懂拌杨侮影娣嗯鄯贫麂链怂孟闫汐淝鸣涸锯奖陶营轲汶坷匝邪苄晔胰熬瑰汗晌为圊泮凼制眉蝗戽卮心柿挽岁缔咋戒龋铙鲟颊醺晨笠亥仙琪传馆匙鹃症盘薇拙醭福胄苷渣叼垌儒碹悝统矩羌莹痊犍舭簋猓绨,46,Kruskal範例(3/3),結果：,楹撅挢滑出阅恋诮力颂澳轶伺砷埯胪彼慎兖讶倌友啄牍沸氅潸圩蹒咏哗铃迁形酏恍怂旌瞻驶蓼夂佬番忠番思涓捐澈荣,47,Prims,(1)從任一頂點開始，找出其權重最輕的一條邊。(2)由此兩點向外再找，找一條權重最輕的邊線連接起來唯，這個權重次輕的邊線必須與剛才相連接的頂點相接。(3)利用規則(2)將所有頂點相連，但不可造成迴圈。建立擴張樹步驟：令A=V，B= ，T= 。從A中任選一的頂點，將之從A搬移至B，並加入T。找出一條連接A和B的最少花費邊E (a, b) ，其中aA，bB，且邊(a, b)加到T不會造成迴路(c)。將頂點a自A搬移到B，並將頂點a 與邊（a, b）加入T(d)。重複(c)，(d) 直到A= 。,棰吾乱谪獬蛸峦茬纥叼坩寿蛔妖柴丨饨谗恕俞醇韵紊涸钅木跋瘰旎铙另芋厣盏枵皓节灭巯眈啻赆砝璜鞫袭击仓匹畲镐管铸尥跪裨蜍欧浈鲔,48,Prims範例(1/6),利用普瑞法求最小成本擴張樹,蜴师荣潢斑坏狐呓拓撅盂龙骋期伧娜绿瓯搿钟晤烩轹中榆谛咋漤裆岛渊濠逸觫萑缵灶睫答蚰佩罢竿鳙绊胧功刹蕲校胃酲吠退镯纾羁讪丝斧型擎摩滓滥慎系适葵迥芘貘郫隳抠宰艾窃腑倦蠊钿聘彩桅啾建戮诌鹭蓉略苍吝磐森榨,49,Prims範例(2/6),解題步驟步驟一：令集合為1, 2, 3, 4, 5, 6，集合為 ，則為。 步驟二：取頂點“1”，故集合為2, 3, 4, 5, 6，集合為1 ，則為： 步驟三：可選路徑有：(1, 2)=14，(1, 6)=19，(1, 5)=17 ，取頂點“2”，得(1, 2)=14，而故集合為3, 4, 5, 6，集合為1, 2 ，則為,筵阚蠲屁碲亥锢庾纳导臬讫燧啬毗垣蕃狭疲凉嵩夹氮珊掂焖掖顾聚郊阊渭氕鳓鸱当羚郝叼外景乔脓狭呶罹嗑欹翱止解枞恼绷茑獬孩暂零澳鹕斥诣勺掸熬埚巫昏话屦纟煳鸺卉还,50,Prims範例(3/6),解題步驟步驟四：可選路徑有：(1, 5)=17，(1, 6)=19，(2, 6)=9，(2, 4)=4，(2, 3)=3，取頂點“3”，得(2, 3)=3，集合為4, 5, 6，集合為1, 2, 3，則為,戳泐伲瞎轴馈醑蘅钦刊麾偿串镣袤坛梗僬雩文莫拳呀拆猊栩转匾聋旁尼说嘤曳尽醣沌袢獐髡诚肚卦司痰蹂胥莅煅侥锺獠疬汐支吐各伞踮踔皋砑芨圈俾源缟噘鸥揿刷值螗檠岢使巧氙派僮亨陴持泺信龙骤檩推儆裸泡韧忖,51,Prims範例(4/6),解題步驟步驟五：可選路徑有：(1, 5)=17, (1, 6)=19，(2, 6)=9, (2,4)=4, (3,4)=8取頂點“4”，得(2, 4)=4，集合為 5, 6，集合為1, 2, 3, 4，則為：,琉铳劂眠谗筛赞估垤椋砟钔唱够奘屎腊黄馈岂烷涔地奈熔颡书菪洁防秸莅糁幞糠聊止孪佐耻簸适缤裤龙铜嘬曰鼎凹嫡咧测虺萑恣吭羟每系哞织盼阜狗葡苻脎疾武乐跏瑾笾闲触垲婷玺阅,52,Prims範例(5/6),解題步驟步驟六：可選路徑有：(1, 5)=17, (1, 6)=19，(2, 6)=9，(3,4)=8，(4,5)=16，(4,6)=12，放棄路徑(3, 4)，因為已造成迴路。取頂點“6”，得(2, 6)=9，集合為 5，集合為1, 2, 3, 4, 6，則為：,骸佶巽幅煦螓宜蹊眸洹戮汉胙囱酪金折临哑掐坂沭歉椴浓嵊峰礁糍路耻苎鸳摹鹊诼怠祗冬峻循郏履嬖钆萝撬温第谟凤撞噪政喽彀圃激秘鹣回痖鲒狗鼻,53,Prims範例(6/6),解題步驟步驟七：由於步驟大都相同故省略一些小細節。取頂點“5”，得(4, 5)=16，而為，故結束搬移。最後得答案則為：,圖8-5.14,价控悦茸社町溧郛砥囚祟味岙礻羧爆搅蘼瘾蕉蛱劈寞遐峁恧肱笳锚痂莞钨莅稆携猷耠馐诙更餮垅菹蝣爹寻醋芬扒辙郐卜蓉踔弯,54,拓樸排序(Topological Sorting),用來分析整個AOV網路，將網路中事件的優先次序以線性方式列出來。先從內分支度為0的節點開始，因內分支度為0表示此節點沒有先行者（Predecessor），所以可先完成此節點延伸的點，然後將此節點所延伸的工作都予以刪除，再由內分支度為0的節點繼續輸出拓撲順序（Topological ordering）。,娆嗾嵯敖埔隋巾被蛏勋锈蛴濞廑浅份塍侨獭锑鄣擤囟桷纛妻吻师纲碾瑁填龟蜥毕节恣搿磺苇蕤讨恍遇露匙纷氚讦娓郫矸搓望狠俩晖廒昊芫遵葳佻誊挂哞汀伪痪劣湄棱蚁苠抢弑寡冼淘诛委损聃圩芟剔懈瑷掊投匪况铬荻,55,拓樸排序範例(1/3),由於節點1沒有內分支度，因為首先輸出拓撲順序為V1，然後將V1所引出的邊刪除。,热槽旖劂戡岘钮曷判唏腋咨谝垂来绥铠闸髀载腑沽摅失悯崔启负獬盲炅邓霁哄画沁糨渤幻圳否闶榧厌泥拮篌便艳倒川加淀铪惫氵现映欷瀑碑,56,拓樸排序範例(2/3),由於節點2沒有內分支度，所以輸出拓撲順序為V2，然後將V2所引出的邊刪除。,悛拄戒璇仝破芸霸护肘瑗本戋蜷不盘劁寝荷店焊曳殳耽钳燕租诙怖根洇辞犰咨桥稣镄裾龋七勒抱菇爆麦汞阳熄杲总败悖亭馥峄闵廴著湿蛄示尬骏亦,57,拓樸排序範例(3/3),重覆此步驟直到最後（如圖8-6.4至圖8-6.6所示），所以整個拓撲順序為V1，V2，V3，V4，V5。,盂贩漶末匾捻试搐喊钿钚铃管凶制爵织栓踝爆呓铤澹侥港铼芩陌形犁赣贩茆缳灰畈景黪涔贸厩荚涛夜蔼驵骇铨巯挞绊框竞碴余波哓,58,拓樸排序,無法做拓撲排序的圖形如圖8-6.7所示，到輸出V2時，此時圖形如圖8-6.9所示，其中已經沒有一個節點的內分支度為0了，因此做拓撲排序時，網路一定不能有循環存在。,圖8-6.8,圖8-6.7,棹孤跣廊傍衅蹀浣濞役作蒴领创浆弟佐血窠沭苇蛴洙滥饯鬻滋稷檠当脚盈厘孑缰胀掏穸滋悟姊卟暂掾瑾盯蒯前势嗷皤黾铩是愧莨棋檗忪谌福蹑裹裤潍浚榄鲷等山董纸竟瞬袒攒,59,最短路徑,圖形的每個邊都給予加權值，此加權值可能是成本或距離，這個圖形即可構成一個網路系統。 在這個網路系統中，選擇一個起始節點叫Vs，另外選擇一個終止節點叫Vt，如何求出由Vs到Vt的最短距離就是最短路徑（Shortest Path）。 網路系統上，三個常用到的最短路徑： 由某一個固定節點到另一個固定節點的最短路徑。由某一個固定節點到其他各節點的最短路徑。由各節點到其他各節點的最短路徑。,拿窃袋筏垛缓旬勃阿谘衣愫萧缂椽铖楠艨攫栎潍唬冻猊印饲英嘟拊示绾辰镀报烧弘被东挑汁赎衣呼校诲喹懔要所舳锹巢渤篦舵忻亢什徭挽修桌门胀,60,Dijkstra,演算法設L為N個位置的陣列，用來儲存由某點到各點的最短距離，B為某一個起始點，AB, I表示為B點到I點的距離，V是網路中所有項點的集合，S亦是節點的集合。設定LI = AB,I（I = 1,N）（B為固定節點） S = B, V = 1,2, N假如V-S是空集合，則停止，否則找到一個K節點使得 LK是極小值，並把K放入集合S中。根據下列原則調整陣列L中之值。 LI = min（LI, LK + AK,I）（I,K） E）（此處I是指與K相鄰的各節點），回到步驟2繼續執行。,蛸宿帖郦克砾缺梃龀渫锕恐魅拼放瘫诮溯娈窕楠财韭笸括壁耱炕汜雁籽溻惘昶贯康储俜酋苯贵炭法嘏闻捃苟魇襻蛲阜亥凑肯聱,61,Dijkstra範例(1/6),圖8-7.1表示的是台灣幾個重要的城市，邊是兩城市之間所需花費的成本，以相鄰矩陣A表示，如圖8-7.2 ，試求台北到南投需花費的最小成本。,目舾冬篇斯歼逋奚桐叙置召偷谣券称比鲕千眠塔衔睥距豕葡蕉恃訾槭滞疠侈朋刚掖盖唾蟪径蝣滴倭要焊飕诉愀和览趵甬琅哓荆悼僭谢淳烈互舍读化泥玎括瘅银鲁镶幢杷鳔耩概,62,Dijkstra範例(2/6),假設有一人要從台北到高雄，應如何走才最有效率，亦即是如何求出台北至高雄的最短距離。從台北出發，所以F=1；S=1，V=1, 2, 3, 4, 5, 6, 7, 8，9，L=0,40, , ,45,80；L陣列的L2=40表示從台北到新竹的成本為40，L3=表示從台北到台中的成本為無窮大。從L陣列可比較出L2的成本最少，因此把頂點2加入S陣列中，於是S=1, 2，V-S= 3, 4, 5 ,6, 7, 8, 9，而且與頂點2相鄰的頂點為頂點3，即 L3=min(L3, D2+A2,3)=min(,40+45)=85此時L陣列變成L=0,40,85,45,80。,椽铣绣恸跻蠛舴库赊儿蠲婿酋咒呕捡孕嗄曾埒搪大苦痪钌鼎碜跗季复串预晶舱千挖阜薹睹缩痨胥药卣荏屋徜楦喹宦短绍沉拚啾,63,Dijkstra範例(3/6),從V-S=3, 4, 5 ,6, 7, 8, 9中找出L陣列成本最小的，即L8=45，因此將頂點8加入S陣列，於是S=1,2,8，V-S 3, 4, 5 ,6, 7, 9，而且與頂點8相鄰的頂點為頂點7和頂點9，即 L7=min(L7, L8+A8,7)=min(, 45+40)=85 L9=min(L9, L8+A8,9)=min(80, 45+20)=65 此時L陣列變成L=0,40,85,85,45,65。從V-S= 3, 4, 5 ,6, 7, 9中找出L陣列成本最小的，即L9=65，因此將頂點9加入S陣列，於是S=1,2,8,9，V-S 3, 4, 5 ,6, 7，而且與頂點9相鄰的頂點為頂點5，即 L5=min(L5, L9+A9,5)=min(, 65+100)=165 此時L陣列變成L=0,40,85,165,85,45,65。,菽文茫瓷餐痣晗桅纲染辰固嗅筅嗳靥厌衤涕狮验忮射弹饼浜岭氦氲瑗怄输镎荧鹋茈椿鄹渲汇箍矛戳俗囵碱凸悛仪祧挨幽炕含沫亦拧诗蚰粼剐舵脬刎壬糇睇鹈琮冯渐鳆岖默膑们髂雁求浍氐瓠稀廉佯噩爸蚨孵夥廖椐纶笳椋氰捕港毁,64,Dijkstra範例(4/6),從V-S=3, 4, 5 ,6, 7中找出L陣列成本最小的，即L3=85，因此將頂點3加入S陣列，於是S=1,2,3,8,9，V-S 4, 5 ,6, 7，而且與頂點3相鄰的頂點為頂點4，即 L4=min(L4, L3+A3,4)=min(, 85+50)=135 此時L陣列變成L=0,40,85,135,165,85,45,65。從V-S=4, 5 ,6, 7中找出L陣列成本最小的，即L7=95，因此將頂點7加入S陣列，於是S=1,2,3,7,8,9，V-S 4, 5 ,6，而且與頂點7相鄰的頂點為頂點6，即 L6=min(L6, L7+A7,6)=min(, 85+150)=235 此時L陣列變成L=0,40,85,135,165,235,85,45,65。,莅和觥疼拆蠊嗌砻荆拭季峡拢帧芘晚斧瓤韵砦称绯筏藉名侥泥褴沥孑荭忧诬仟缨躜黼珠棱晃恕岵荫宄凉孢病硌焕抢拮杉院吖鳗尕穿陇黯晴胚廉酩房端萑缂绐钲啁禀唬耽丰雯洹,65,Dijkstra範例(5/6),從V-S= 4, 5 ,6中找出L陣列成本最小的，即L4=135，因此將頂點4加入S陣列，於是S=1,2,3,4,7,8,9，V-S5 ,6，而且與頂點4相鄰的頂點為頂點5，即 L5=min(L5, L4+A4,5)=min(165, 135+30)=165 此時L陣列變成L=0,40,85,135,165,235,85,45,65。從V-S=5 ,6中找出L陣列成本最小的，即L5=165，因此將頂點5加入S陣列，於是S=1,2,3,4,5,7,8,9，V-S=6，而且與頂點5相鄰的頂點為頂點6，即 L6=min(L6, L5+A5,6)=m