数据结构第章

第9章图图的基本概念图的存储结构图的实现图的遍历最小生成树最短路径拓扑排序关键路径

主要知识点9.1图1.图的基本概念图是由顶点集合及顶点间的关系集合组成的一种数据结构。图G的定义是：G=（V，E）其中，V={x|x∈某个数据元素集合} E={(x，y)|x，y∈V} 或 E={＜x，y＞|x，y∈V并且Path(x，y)}其中，（x，y）表示从x到y的一条双向通路，即（x，y）是无方向的；Path（x，y）表示从x到y的一条单向通路，即Path（x，y）是有方向的。问题：图的特点图有许多复杂结构，本课程只讨论最基本的图，因此，本章讨论的图中不包括从自身到自身的边存在的图，以及带自身环的图基本术语：（1）顶点和边：图中的结点一般称作顶点，图中的第i个顶点记做vi。两个顶点vi和vj相关联称作顶点vi和vj之间有一条边，图中的第k条边记做ek，ek=（vi,vj）或＜vi,vj＞。（2）有向图和无向图：在有向图中，顶点对＜x,y＞是有序的，顶点对＜x,y＞称为从顶点x到顶点y的一条有向边，有向图中的边也称作弧；在无向图中，顶点对（x,y）是无序的，顶点对（x,y）称为与顶点x和顶点y相关联的一条边。（3）完全图：在有n个顶点的无向图中，若有n(n-1)/2条边，即任意两个顶点之间有且只有一条边，则称此图为无向完全图；在有n个顶点的有向图中，若有n(n-1)条边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为有向完全图。（4）邻接顶点：在无向图G中，若（u,v）是E(G)中的一条边，则称u和v互为邻接顶点，并称边（u,v）依附于顶点u和v；在有向图G中，若＜u,v＞是E(G)中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边＜u,v＞和顶点u和顶点v相关联。。013201234560120123(a)无向完全图(b)无向图(c)有向图(d)有向图（5）顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。顶点的度=入度+出度。（6）路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径（7）权：有些图的边附带有数据信息，这些附带的数据信息称为权。带权的图也称作网络或网。（8）路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。（9）子图：设有图G1={V1,E1}和图G2={V2,E2}，若V1V2，且E1

E2，则称图G2是图G1的子图。2135467879610612715163BACDE60304575804035施工进度图

交通网络图

（10）连通图和强连通图：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。在有向图中，若对于任意一对顶点vi和顶点vj（vi≠vj）都存在路径，则称图G是强连通图。（11）生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。生成树一般是对无向图来讨论。（12）简单路径和回路：若路径上各顶点v1,v2,…,vm,互不重复，则称这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。数据集合：由一组顶点集合{vi}和一组边{ej}集合组成。当为带权图时每条边上权wj还构成权集合{wj}。操作集合：（1）初始化Initiate(G,n)（2）插入顶点InsertVertex(G,vertex)（3）插入边InsertEdge(G,v1,v2,weight)（4）删除边DeleteEdge(G,v1,v2)（5）删除顶点DeleteVertex(G,vertex)（6）第一个邻接顶点GetFirstVex(G,v)（7）下一个邻接顶点GetNextVex(G,intv1,v2)（8）遍历DepthFirstSearch(G)2.图的抽象数据类型9.2图的存储结构图的存储结构主要有邻接矩阵和邻接表两种。1.图的邻接矩阵存储结构假设图G=(V,E)有n个顶点，即V={v0,v1,…,vn-1}，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足：由于矩阵A中的元素aij表示了顶点vi和顶点vj之间边的关系，或者说，A中的元素aij表示了顶点vi和顶点vj（0≤j≤n-1）的邻接关系，所以矩阵A称作邻接矩阵。

无向图的邻接矩阵一定是对称矩阵有向图的邻接矩阵一般是非对称矩阵其中V表示了图的顶点集合，A表示了图的邻接矩阵带权图及其邻接矩阵其中V表示了图的顶点集合，A表示了图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0<aij<∞的元素个数等于第i个顶点的出度，邻接矩阵第j列中所有0<aij<∞的元素个数等于第j个顶点的入度。2.图的邻接表存储结构当图的边数少于顶点个数且顶点个数值较大时，图的邻接n×n矩阵的存储问题就变成了稀疏矩阵的存储问题，此时，邻接表就是一种较邻接矩阵更为有效的存储结构。BADCE(a)01234ABCDE0datasorce1432adjdestnext23411∧

∧

∧

∧

(b)4∧

数组的data域存储图的顶点信息，sorce域存储该顶点在数组中的下标序号，adj域为该顶点的邻接顶点单链表的头指针。第i行单链表中的dest域存储所有起始顶点为vi的邻接顶点vj在数组中的下标序号，next域为单链表中下一个邻接顶点的指针域。如果是带权图，单链表中需再增加cost域，用来存储边<vi,vj>的权值wij。问题：邻接表存储结构和数组一章中的什么存储结构类似？9.3图的实现1.邻接矩阵存储结构下图操作的实现#include"SeqList.h"

typedefstruct{SeqListVertices; intedge[MaxVertices][MaxVertices]; intnumOfEdges; }AdjMGraph;

vo爱idIn忌it热ia罗te桌(A节dj翠MG朵ra侵ph*G盏,in哑tn){in迷ti,估j尽;fo刘r(注i=挺0;傲i歉<毙n证;裙i+气+)fo罚r(族j=众0;廉j狡<梢n浙;浊j+隔+){if辰(i==茧j闹)坦G-率>e签dg功e[沉i]行[j省]割=舰0;el养se食G体->尽ed邮ge失[i等][顺j]堵=Ma互xW押ei她gh际t;}G-用>nu枝mO始fE透dg挑es=于0;渗/*边的作条数誓置为器0*指/Li赶st鸣In笨it恭ia宿te欧(&轧G->碰Ve移rt桶ic秩es并);刮/丹*顺序蝇表初殿始化型*/}vo泡idIn辆se细rt谷Ve纺rt芬ex茶(A糊dj润MG临ra钱ph*G碧,Da尝ta纠Ty番peve弹rt都ex习){Li私st沟In羞se泽rt(&聚G->裁Ve谅rt纤ic顿es谷,挣G-要>V让er姿ti突ce蜻s.秋si徐ze讲,河ve忆rt慌ex);}vo浪idIn该se齐rt赠Ed宵ge齐(A傍dj薯MG硬ra络ph*G访,in销tv1倡,in敏tv2灿,in乔twe答ig械ht染){if便(v杜1便<耍0菊||亩v反1浴>冒G-拦>V溜er算ti隆ce易s.酷si伙ze两|典|两v2救<抹0怒|题|驱v2肠>刚G娃->丙Ve搜rt本ic怕es气.s早iz第e){pr度in辽tf("参数v1或v2越界枯出错揪!\n"稳);ex坏it目(1滔);}G-婶>e钳dg填e[区v1掘][创v2蝇]姑=添we养ig研ht迫;G-倾>nu朴mO畜fE愁dg袍es++拣;}vo血idDe赴le乌te富Ed专ge鞠(A养dj裂MW缝Gr军ap肆h*G姜,in蜓tv1彻,in价tv2渠){藏i革f(区v1羡<冒0疯|允|关v1尿>秧G末->酒Ve郊rt设ic悦es跑.s败iz慢e洽||能v嫌2箭<仪0尺||松v发2框>诱G-怨>V愉er切ti稳ce吴s.失si桌ze杀|赢|苹v1跨=含=多v2耳){pr盾in冠tf("参数v1或v2越界俊出错尊!\n"拦);ex驾it窄(1育);}if驻(G->温ed套ge幼[v森1]柱[v峰2]宽=服=Ma答xW勒ei鼻gh哀t||秒v芳1冻==搭v涂2){pr妥in悲tf("该边聋不存跪在!欲\n"哀);ex友it径(0初);}G-旬>e愤dg隙e[轰v1辨][用v2动]议=Ma吐xW码ei漆gh总t;G-轻>nu罪mO裁fE塘dg选es--生;}in伶tGe终tF浸ir天st星Ve围x(检Ad委jM撞Gr爱ap师hG,in忽tv){in恒tco居l;if网(v<循0阁||顽v陶>桌G劳.V歉er梁ti名ce昼s.酸si枕ze嚼){pr建in摔tf("参数v1越界落出错五!\n"貌);ex脉it趣(1满);}fo芒r(co芽l=饲0;co巧l<=府G掩.V盖er秆ti拨ce妨s.热si卷ze骄;co罢l++涛)if命(G缎.e腥dg寄e[近v]萌[c幼ol]贱>等0通&&G.牌ed项ge理[v央][掌co侨l]肿<Ma啄xW眯ei防gh劲t)勾re放tu脸rnco狐l;re涂tu乘rn扶-治1;}in牺tGe伞tN弊ex饲tV惊ex撒(A埋dj辆MG辅ra秒phG,in构tv1禽,in倍tv2卷){in摸tco狸l;if始(v色1讽<元0孟||域v布1绒>份G.参Ve熟rt蔽ic习es炒.s丹iz管e董||供v救2削<存0侧||登v2流>汉G扰.V肯er委ti下ce检s.承si端ze此){pr幕in尾tf("参数v1或v2越界贤出错互!\n"代);ex醒it纤(1点);}fo统r(co稿l=括v2犁+1竿;co横l<=管G道.V骗er证ti树ce帜s.嚷si回ze详;co些l++畜)if薪(G权.e牌dg叔e[造v1叔][渡co浊l]肺>抱0疮&民&孤G.感ed寄ge方[v信1]邻[c把ol吸]垫<Ma份xW中ei特gh速t)封re银tu洋rnco俭l;re受tu腊rn侦-扫1;}2.邻接泉矩阵衰图操饭作的赠测试例9-兄1以下免图所垂示的续带权什有向板图为顷例编责写测铃试邻仍接矩茅阵图影的程添序。ABCDE1040305020图的顺创建砖函数足设计朴如下击：ty驾pe肝de射fst夹ru痰ct{in垦tro奔w;句//行下陈标in甲tco震l;彩/盐/列下朴标in绩twe躲ig昼ht往;吗/菜/权值}Ro象wC竿ol余We置ig姜ht;vo棚idCr旗ea请tG菜ra体ph凑(A颤dj姓MG盈ra彼ph*G完,Da痕ta目Ty痒peV[另],播i丢ntn,模R茅ow某Co炼lW偿ei报gh篮tE[典],考i兰nte)/*在图G中插泊入n个顶颤点信垮息V和e条边腊信息E*两/{in占ti,状k漆;In啄it脚ia继te窃(G,n);幅/抢*顶点诱顺序扣表初废始化灭*/fo环r(颗i=筑0;i<诸n;i++渣)In歪se骂rt葬Ve准rt讽ex督(G,V[巡寿i])狡;猫/闲*顶点冷插入档*/fo钢r(穴k=睡0;k<车e;k++睬)In躲se剃rt塑Ed险ge害(G,E[即k].从ro谊w,E[姓k].酱co理l,E[志k].竟we垂ig棋ht巷);/*边插柄入*阿/}测试芹程序千设计沈如下色：#i裙nc孤lu注de妥<st感di搭o.转h>#i猛nc套lu效de潜<st暗dl积ib缘瑞.h>ty耀pe阴de哈fch随arDa扮ta位Ty扣pe;#d挥ef方in密eMa民xS揉iz亭e10#d向ef胜in哭eMa聪xV客er伶ti转ce狗s10#de催fi搜neMa冷xW杆ei斑gh找t10茶00丑0#in贞cl加ud踏e依"Ad评jM济Gr扶ap敢h.怜h"#i吃nc命lu北de茎"Ad庸jM病Gr搅ap伤hC裹re勤at胸e.纠h"vo氏idma香in香(v挡oi野d){Ad技jM抽WG颜ra滚phg1静;Da音ta岗Ty盆pea[艺]配=农{'箭A'菊,'栏B'认,'缓C'梅,'赶D'尤,'故E'个};Ro略wC絮ol困We扒ig哈htrc跪w[]败={{说0,澡1渔,乡丰10},残{0,厌4盈,亡20},吹{1,网3售,刘30},承{2,潮1小,矛40},坦{3,横2困,雷50}}帜;in碧tn哨=贼5,嫁e巩=尾5业;in熟ti,舅j镇;Cr动ea妹tG饿ra健ph耗(&玩g1公,汁a,茎n盏,rc畅w,炭e)童;De机le嫁te应Ed蔽ge盘(&它g1姓,更0,民4拐);pr班in嚼tf("顶点障集合辈为：秘")对;fo俭r(婶i=这0;逼i岭<扇g窗1.炊Ve脱rt殊ic书es秀.s签iz品e;建i取++地)pr亲in即tf确("旦%c",漂g幼1.慈Ve经rt佳ic兆es酒.l雀is把t[衫i]企);pr凉in柿tf旦("咸\n")抢;pr富in膝tf("权值扑集合典为：条\n"丢);fo婶r(慨i=骆0;羡i民<雅g倒1.门Ve读rt锐ic甩es绢.s梳iz质e;霜i莲++鱼){fo底r(哭j=万0;震j验<惠g客1.厅Ve劈燕rt穗ic苹es掠.s掏iz给e;燃j艰++倒)pr离in恨tf椒("咸%5肃d械",燥g学1.各ed传ge涌[i进][是j]捏);pr逮in糠tf第("训\n")请;}}2.邻接宏表存棍储结胁构下吐图操驴作的苍实现邻接公表的谨存储书结构ty珠pe湾de档fst遮ru拜ctNo谁de{in读tde著st;做/*邻接毅边的区弧头客顶点路序号称*/st早ru明ctNo隶de辞*赠ne题xt蛛;}葵Ed影ge捡;耀/鼻*邻接雨边单趟链表寨的结胜点结推构体允*/ty差pe够de北fst甲ru吐ct{Da歉ta陪Ty书peda欧ta每;艘/*顶点瞒数据涉元素港*/in好tso桨rc扁e;甩/世*邻接挺边的米弧尾留顶点瓜序号叠*/Ed红ge侧*ad脂j;调/低*邻接内边的版头指申针*镜/}Ad轧jL肠He冻ig阁ht;皂/*数组雕的数累据元番素类抓型结丑构体海*/ty毕pe封de假fst挥ru以ct{Ad败jL味He脾ig掀hta[挣Ma牧xV文er碗ti姿ce烘s];础/*邻接止表数跌组*恳/in匠tnu屿mO窃fV厅er卸ts;愤/*顶点祥个数遭*/in族tnu景mO不fE长dg塘es;朴/*边个思数*揭/}Ad斩jL公Gr抹ap协h;菊/越*邻接甲表结科构体情*/讨论到：图左操作劈燕的实清现方罢法9.颜4图的嫂遍历1.图的短深度障和广而度优减先遍爬历算驻法图的团遍历首是访落问图维中的汤每一眉个顶正点且享每个太顶点柜只被则访问绞一次甜。算捎法设渴计需劣要考树虑三珍个问衬题：（1剂）算种法的院参数他要指昆定访争问的域第一回个顶锡点；（2咱）要盒考虑婶遍历肯路径览可能霜出现签的死蹈循环达问题终；（3毛）要维使一哨个顶出点的疼所有她邻接孤顶点老按照泻某种介次序芦被访欠问。一、图的醒深度例优先炸遍历家算法图的级深度税优先碌遍历扩算法傅是遍龟历时居深度虹优先究的算亿法，俩是一暮个递域归算级法。连通夺图的深训度优并先遍愿历递棕归算比法为宏：（1伪）访司问顶之点v并标刮记顶色点v为已怜访问抢；（2耗）查激找顶辛点v的第扮一个锈邻接纵顶点w；（3众）若顶钓点v的邻件接顶乌点w存在睁，则牛继续片执行掉，否著则算振法结转束；（4仍）若何顶点w尚未愿被访努问则企深度舍优先堵搜索罚递归集访问敲顶点w；（5）查找纠顶点v的w邻接搅顶点渔的下工一个截邻接海顶点w，转到裙步骤疮（3）。对于职例9-士1所示孤的有甚向图翅，深度采优先灾遍历肤访问厨顶点映次序戴为：A地B掘D板C涛E二、图的弃广度萌优先脊遍历板算法连通词图的广搅度优流先遍径历算乔法为忽：（1清）访集问初仙始顶救点v并标旬记顶张点v为已速访问倾；（2涨）顶宝点v入队惯列；（3照）当厅队列伙非空差时则蹈继续钥执行巧，否勒则算列法结挖束；（4坛）出液队列什取得峡队头粒顶点u；（5械）查找贤顶点u的第怜一个啊邻接捧顶点w；（6）若顶栽点u的邻添接顶因点w不存菊在，犯则转薄到步朵骤（款3）虹，否吨则循达环执座行：（6冒.1慨）若棚顶点w尚未顽被访炼问则眯访问侵顶点w并标搜记顶识点w为已值访问告；（6释.2闲）顶无点w入队凯列；（6叉.3质）查杆找顶虏点u的w邻接坑顶点钱后的绳下一悼个邻忽接顶始点w，转到叮步骤困（6悦）。图的唐广度块优先泛遍历际算法奋是一阀个分那层搜吨索的雄过程会，需维要一校个队勇列以堆保持弊访问迷过的将顶点仔的顺旺序，足以便甲按访铺问过姻的顶寄点的歼顺序估来访筒问这挎些顶泉点的纷邻接柿顶点逮。对于那例9-惨1所示佣的有罪向图芦，广锅度优更先遍窑历访疑问顶消点次棵序为粥：A多B勇E苍D始C问题：连预通图傲的（肚深度馒、广基度）合遍历肤和生草成树哲的关胞系？三、非连嗓通图泥的遍优历对于扫非连觉通图细，从皆图的晓任意萌一个痰顶点漂开始究深度籍或广识度优蝴先遍迹历并矛不能贸访问选图中旱的所指有顶并点。只能狮访问钞和初艳始顶瓶点连面通的精所有蛮顶点马。但是塞，每糠一个塞顶点添都作左为一按次初陕始顶伏点进暖行深长度优烂先遍坏历或塌广度么优先剂遍历猛，并聋根据压顶点挺的访讽问标俱记来痛判断洪是否杂需要赌访问卵该顶帝点，孤就一仔定可评以访拥问非也连通晌图中心的所绑有顶趟点。vo押idDe失pt哈hF钩Se宅ar松ch毯(A广dj征MW另Gr箩ap两hG,in阁tv,in厕tvi颠si猎te皆d[睬],vo章idVi亲si扛t(罗Da浓ta济Ty行peit蛾em乖)){in挠tw;Vi刻si效t(捡G.筐Ve俱rt姥ic悔es置.l判is陶t[等v])邻;vi对si谁te衣d[拨v]丈=鸭1;w臣=Ge绝tF郑ir锻st脚Ve皮x(亿G,度v)倦;wh笼il欢e(具w!=刷-马1){if住(!老v江is供it格ed论[w防])De轰pt峡hF忽Se稻ar倚ch坑(G,分w,兆v取is芳it梅ed艰,摇Vi凶si纪t)授;w=Ge钩tN热ex权tV青ex闻(G,裳v,叹w哲);}}2.渴图的屯深度绩和广复度优仆先遍雷历函芽数实顶现一、深度雷优先药遍历二、厨非连蝴通图释的深度器优先肉遍历vo纯idDe辆pt偿hF秤ir鹿st友Se盒ar勾ch粱(A蚂dj趴MW益Gr般ap昏hG,骗v讽oi皂dVi冠si眉t(仅Da挥ta情Ty纵peit运em裤)){in如ti;in贩t*v搂is孕it获ed纱=且(in叛t*)ma拣ll功oc霞(s肃iz瓣eo盲f(宁in幅t)*虚G.钳Ve喊rt最ic俗es萌.s船iz健e)躺;fo晚r(金i=嫁0;竞i画<著G陕.V弊er谷ti骂ce赢s.孙si雹ze址;屈i+讨+)vi夸si削te覆d[窑i]宫=态0;fo允r(革i=陶0;钓i见<胜G祝.V蓝er研ti堪ce放s.宴si趴ze民;掉i+占+)if顿(!按v归is竞it放ed雕[i终])De发pt赠hF样Se伯ar笑ch样(G,诞i,舱v贸is江it傍ed时,妇Vi缠si输t)碗;fr齿ee渠(v做is巴it锋ed);}三、倦广渡度优符先遍枕历#in阴cl眯ud山e货"Se代qQ步ue杠ue糠.h"vo么idBr崇oa俗dF摧Se雀ar之ch慢(A灰dj伙MW溪Gr防ap团hG,in坐tv,in月tvi即si完te惊d[鸣],vo惕idVi旺si溜t(秃Da术ta拌Ty棋peit村em买)){Da哗ta允Ty圈peu,会w包;Se琴qC隐Qu形eu国equ色eu魂e;Vi蓝si定t(蝴G.庸Ve奴rt澡ic烫es盐.l肌is勒t[睡v])耀;vi些si采te贩d[灰v]笑=够1;Qu阳eu良eI色ni腿ti奸at想e(芝&q胀ue挡ue);Qu批eu网eA温pp松en婚d(谋&q井ue愚ue,圆v)置;wh较il冰e(款Qu笑eu途eN况ot床Em饭pt汉y(喘qu赠eu足e)){Qu巡寿eu争eD箭el逃et丝式e(尽&q均ue骂ue,爱&u调);w=Ge宾tF辈ir错st挨Ve逃x(锣G,刷u)积;wh启il蚁e(悬w!=朱-免1){if记(!寸vi步si鼠te奋d[抓w]){Vi殿si横t(倒G.腔Ve爬rt恢ic储es尾.l体is妈t[彻w])居;vi辆si钞te赏d[带w]社=键1;Qu芒eu舍eA出pp短en牲d(&碎qu势eu桑e,滑w)蛮;}w=Ge来tN予ex勺tV糟ex遣(G,朽u,改w坝);}}}vo现idBr劫oa貌dF艘ir渴st梦Se上ar停ch脂(A姓dj版MW家Gr踩ap捉hG,锄v敞oi弄dVi孩si恶t(鸣Da墓ta吃Ty询peit痰em渡)){in雕ti;in约t*v状is矛it泡ed靠=搬(in蚀t*)ma辈ll兰oc篮(s菊iz话eo泄f(典in音t)*饲G.岭Ve身rt堪ic驱es刮.s依iz阳e)骡;fo手r(澡i=枕0;不i倚<碌G隶.V提er积ti悄ce坡s.通si劣ze被;群i+陆+)vi盖si怖te升d[椅i]浴=联0;fo煮r(看i=蹄0;踪蝶i泛<狗G晕.V构er披ti娱ce堆s.康si忽ze摆;侍i+摸+)if愧(!密vi性si润te执d[单i])Br冰oa沃dF餐Se惭ar俘ch昼(G,思i,娘v阿is晓it齐ed疑,岸Vi立si说t)袄;fr烦ee樱(v万is志it进ed);}四、古非连衔通图蕉的广号度优西先遍烤历五、详程序默举例例9-匆2以图9-灾8所示拦的带轧权有抱向图木为例病，编腔写测皱试上怕述图民的深啄度优写先和野广度什优先针遍历乐函数恒的程城序。#in收cl驴ud揪e券<st狼di振o.叉h>#i被nc帽lu浊de拐<st顽dl咱ib各.h>#i殿nc烈lu就de牛<ma望ll凭oc桨.h>ty聚pe彩de恒fch锐arDa借ta腾Ty宏pe;#d符ef狸in至eMa投xS辜iz叫e10木0#d霸ef柜in藏eMa愉xV闭er她ti府ce用s10#d惜ef炉in狸eMa擦xE样dg垫es10爬0#d兆ef即in莲eMa崇xW暑ei孤gh代t10嘉00捕0#d耍ef兵in置eMa勇xQ读ue湿ue称Si电ze10项0#i涌nc敲lu蚊de左"Ad滤jM秤Gr息ap舟h.穷h"#i场nc啦lu学de棒"Ad络jM膏Gr拌ap夹hC测re称at守e.片h"#i温nc遗lu帝de吊"Ad似jM旬Gr包ap句hT症ra酱ve晶rs素e.宇h"vo锹idVi休si指t(详Da劈燕ta稿Ty夫peit杜em弓){pr高in晚tf颈("蒸%c",夫i展te晚m)梅;}vo胡id宿m汤ai散n(污vo包id配){Ad坛jM踏WG叹ra浙phg1净;Da疮ta测Ty旬pea[饭]长=牛{'橡A'举,'冒B'笨,'颜C'感,'软D'五,'崖E'浩};Ro每wC段ol维We拌ig绪htrc触w[]堤=壶{角{0手,1迷,1顺0}跟,{丽0,包4,骡20弓},剂{1沾,3奇,3还0}慕,{窗2,缸1,德40财},幸{3住,2贡,5溪0}很};in樱tn调=固5,贱e泡=卖5熊;Cr跳ea槽tG晨ra关ph痛(&厌g1察,然a,身n伯,rc演w,炉e)加;pr碗in钉tf("深度腰优先宋搜索唐序列尊为：既")猜;De虏pt疏hF离ir笔st吊Se徐ar列ch娃(g早1,闷V喊is悬it观);pr丛in池tf仰("绞\n广度良优先傅搜索颜序列译为：宴")额;Br唯oa例dF钞ir迈st慈Se蒸ar网ch番(g盈1,鸽V宅is浑it源);}9.假5最小渔生成填树1.基本超概念一个签有n个顶平点的蔽连通盗图的生成表树是原图漠的极源小连傅通子惹图，它领包含搭原图债中的劫所有n个顶逢点，浪并且维有保游持图铅连通换的最稻少的写边。（1）若洲在生茄成树微中删优除一化条边近就会帐使该邀生成冠树因紫变成化非连尚通图礼而不未再满羡足生萌成树佩的定馅义；（2）若挎在生育成树蜘中增宾加一昏条边螺就会兽使该宋生成免树中芹因存郊在回免路而墨不再起满足差生成榴树的暗定义细；（3）一典个连律通图裂的生舞成树怒可能苹有许霸多；（4雪）有n个顶炕点的巴无向璃连通畅图，苹无论亿它的倘生成田树的磁形状咬如何冒，一父定有活且只途有n-傍1条边况。1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)(b)(c)无向键图和愿它的沙不同通的生缴成树如果躬无向母连通易图是养一个纪带权款图，秃那么督它的障所有兼生成烧树中舰必有线一棵葬边的冬权值者总和微最小婶的生吐成树克，我币们称煎这棵胀生成煌树为最小灯代价耍生成欲树，简移称最小种生成继树。构造永有n个顶您点的释无向地连通勉带权自图的冷最小绕生成枪树必堆须满姿足以网下三冒条：（1犹）构旅造的诸最小玻生成倡树必堡须包巴括n个顶胆点；（2希）构锯造的惊最小缠生成厌树中单有且催只有n-茶1条边帆；（3脑）构另造的案最小律生成老树中权值寺总和衣最小。典型愚的构何造方虹法有拖两种撑，一澡种称迎作普里适姆（Pr位im）算法，另赚一种席称作克鲁常斯卡袋尔（Kr菊us幻玉ka晕l）算法。2.普里艳姆算情法一、算法姨思想假设G=耳(V迟,E羡)为一警个带宜权图阁，其庙中V为带免权图币中顶饺点的成集合桥，E为带街权图补中边托的权严值集话合。始设置悔两个养新的家集合U和T，其中U用于盼存放吴带权哥图G的最什小生潜成树望的顶轨点的娘集合肥，T用于炼存放恢带权砌图G的最必小生叼成树起的权疗值的决集合微。普里聚姆算促法思看想是：令跨集合U的初兴值为U=霉{u0}（即假幻玉设构秃造最述小生鬼成树师时从忌顶点u0开始质），府集合T的初到值为T=疑{}。从所浑有顶穗点u∈U和顶晒点v∈V-引U的带访权边书中选淹出具铸有最淋小权南值的柏边(u,抢v)，将顶加点v加入僵集合U中，练将边(u,甲v)加入边集合T中。麻如此罢不断丘重复汁，当U=傅V时则谨最小席生成星树构椅造完澡毕。姿此时皂集合U中存忠放着注最小份生成云树顶毫点的逝集合喜，集义合T中存呈放着竟最小慎生成林树边介的权问值集颠合。ACBGEFD50604552423065504070ACBGEFDACBGEFD50ACBGEFD5040ACBGEFD505040ACBGEFD50305040ACBGEFD5042305040ACBGEFD504542305040(a)(b)(c)(d)(e)(f)(g)(h)图9-终10普里僻姆算耳法构杀造最遣小生诵成树寨的过禾程二、洪普里务姆函皇数设熄计普里刑姆函疑数应抬有两暴个参蒸数，贝一个斩参数圾是图G，另一锡个参伤数是番通过妇函数袍得到添的最瘦小生拦成树久的顶猎点数其据和菜相应冤顶点未的边丢的权筒值数适据cl毛os浑eV唐er设te浮x。其数授据类银型定昆义为勉如下何结构勿体：ty弓pe青de掏rst问ru厌ct{Ve蛋rTve征rt笑ex扎;in砌twe刘ig掏ht畅;}Mi浓nS脚pa祝nT旁re遥e;其中劝，ve投rt馆ex域用拘来保桨存最稼小生风成树煎每条醋边的隆弧头任顶点礼数据未，we锯ig这ht域用仪来保触存最吓小生倒成树现的相议应边欣的权参值。普里义姆函陵数设肺计：vo迫idPr宝im汗(A丸dj肆MW肥Gr鼠ap沙hG,Mi蔬nS棕pa浪nT滨re受ecl仓os潜eV膏er第te仁x[]滔){Ve疮rTx;in禁tn杯=星G.危Ve蹈rt锯ic洞es笔.s槐iz届e,mi加nC膛os山t;in缴t*lo跨wC合os蒙t=睬(in杏t*)ma宇ll纹oc策(s阔iz到eo羊f(罩in效t)*锣n)摔;in选ti,扩j四,伐k;fo额r(流i=颂1;隶i深<摄n欲;门i扫++帮)lo翁wC扫os买t[勾i]爸=言G.剩ed衔ge哀[0][束i]疼;/*从顶仙点0拴出发炕构造恭最小商生成清树*拍/Li爷st虾Ge泽t(货G.该Ve天rt亮ic均es,0,权&x妖);cl忘os零eV铃er指te菠x[0].间ve窃rt朗ex魔=红x长;lo谈wC垃os状t[0]氧=时-1浴;fo编r(寒i=1;喜i<n;疤i++岔){/*寻找码当前觉最小肺权值牺的边场所对荷应的傅弧头促顶点k*扶/mi盛nC溪os威t=Ma勺xW敞ei冰gh页t;fo然r(雁j=全1;靠j溉<洞n乏;挖j+盘+){if你(l户ow夺Co味st村[j]汁<mi值nC痰os骗t&&lo菜wC迫os庭t[瓶j]历>捷0){mi沉nC否os杏t=lo疤wC棋os党t[碰j];k件=扶j;}}Li昏st位Ge取t(睬G.醋Ve煎rt淘ic狸es,悉k,助&奶x)流;cl等os钟eV废er膛te悦x[说i]贩.v掠er米te授x=免x;cl尼os况eV建er蛇te赏x[吊i]芹.w跃ei沉gh乒t=mi播nC庄os注t;lo帝wC通os偿t[龟k]络=投-1抓;fo门r(染j=歉1;挡j知<衬n弹;青j+记+){if馅(G富.e嚼dg慕e[脆k]脊[j]鞭<lo景wC膨os诞t[炼j])lo萝wC晕os靠t[招j]逼=萄G.想ed糠ge忽[k沸][植j]般;}}}设计腔说明而：（1革）函槐数中冒定义雾一个倾临时腾数组lo必wC菜os蜜t，数组泡元素lo溉wC芬os碧t[衬v]中保挣存了祥集合U中顶秃点ui与集公合V-巩U中顶渐点vj的所泥有边慌中当石前具忙有最辽小权宪值的伙边(u,v)。（2献）集合U的初系值为U=赶{序号礼为0鉴的顶状点}酿。lo颗wC劣os稳t的初蓝始值锐为邻记接矩党阵数聋组中葬第0份行的室值，脱这样骨初始乘时lo脱wC扣os灵t中就观存放注了从牧集合U中顶炼点0抹到集壤合V-盏U中各杂个顶貌点的忽权值些。（3淹）每问次从lo节wC淹os全t中寻刘找具待有最胃小权艳值的薄边，望根据lo滨wC鲜os盆t的定誉义，液这样锹的边艺其弧送头顶甜点必百然为盯集合U中的定顶点僻，其覆弧尾五顶点讽必然滴为集栏合V-练U中的卖顶点眠。当父选到丘一条魂这样勺的边裳(u,隆v)揉，就保余存其迹顶点忙数据印和权趴值数拣据到紧参数cl执os肥eV甩er智te启x中，薄并将lo羊wC宝os眯t[爸v]置为掏-1抢，表汗示顶稍点v加入它了集嘉合U中。0-115023456lowCost60∞

∞

∞

∞

0-11-123654405660∞

∞

0-11-123504-1570660∞

0-11-123-14-1530642520-11-123-14-15-1642520-11-123-14-15-16-1450-11-123-14-15-16-1-1(a)(b)(c)(d)(e)(f)(g)lowCostlowCostlowCostlowCostlowCostlowCost（4钢）当捕顶点v从集贯合V-克U加入依到集容合U后，经若存舅在一纱条边尝(u,体v)班，u是集呀合U的顶最点，v是集范合V-漠U的顶枣点，枝且边岔(u,少v)较原宝先lo哑wC缺os昏t[间v]的代超价更查小，倘则用址这样龄的权食值修材改原矮先lo坡wC数os夏t[扬v]中的锦相应勾权值贩。（5得）以挺图9-毫10（a）所示愿的无智向连抚通带践权图言为例碍，调帽用普准里姆奔函数恒时数屠组lo姨wC撒os量t的动柳态变睬化过猾程如规图示彻。函数朋主要润是一张个两辣重循吹环，勒其中说每一拣重循钩环的金次数冈均为叹顶点脚个数n，所以乓该算熔法的时间疗复杂夸度为O(n2)。三、限测试考程序例9-往3以图9-弯10（a）所示致的无汁向连咏通带组权图岗为例中设计菊测试也上述Pr测im函数葬的程兆序。3.克鲁吃斯卡翻尔算发法克鲁想斯卡连尔算屠法是召一种按照核带权搜图中即边的架权值程的递经增顺绘序构滤造最移小生后成树的方晴法。部设无盖向连藏通带糟权图G=(V,E)，其中V为顶季点的盼集合日，E为边拉的集刷合。克鲁阴斯卡兼尔算押法思棕想是度：设带昌权图G的最跪小生埋成树T由顶烟点集床合和攻边的烤集合教构成坟，其能初值防为T=(V,{俘})营，即初始碰时最爷小生谋成树T只由绑带权币图G中的奶顶点粗集合坐组成茎，各部顶点不之间疑没有拦一条功边。这烤样，变最小核生成搬树T中的更各个器顶点模各自纯构成碌一个图连通桐分量菊。然吉后，袄按照阔边的盗权值纺递增面的顺淋序考即察带倒权图G中的早边集瓣合E中的谅各条赵边，①若被宝考察渡的边慈的两鸽个顶蠢点属帝于T的两乳个不制同的间连通世分量周，则押将此垄边加漏入到网最小踏生成拥树T，同时膊把两存个连屋通分君量连宾接为茶一个波连通际分量轻；②若被爷考察玩的边井的两里个顶致点属墙于T的同僵一个禾连通妙分量晨，则狮将此久边舍宇去。桥如此宫下去估，当T中的想连通吐分量尖个数晓为1非时，T中的顶该连柏通分赶量即异为带星权图G的一顾棵最挑小生排成树ACBGEFD30ACBGEFD3040ACBGEFD423040ACBGEFD45423040ACBGEFD5045423040ACBGEFD504542305040(a)(b)(c)(d)(e)(f)克鲁河斯卡都尔算趣法构共造最忌小生撇成树魔的过催程9.抽6最短摆路径1.基辅本概漠念路径浪长度:一恰条路监径上续所经器过的护边的无数目带权易路径役长度始:路径桨上所滨经过田边的头权值轨之和最短殖路径鸦:(带司权)暮路径代长度甲(值军)最克小的伪那条驻路径图9-喜13（a）有向鞭带权将图；枣（b）邻接拼矩阵2.从一展个顶异点到战其余物各顶丧点的崭最短沿路径一、狄克翠斯特个拉算候法思掀想按路千径长浆度递梳增的抚顺序丑逐步双产生精最短恶路径滨。狄克贝斯特初拉算醒法的兔思想拌是：设置抵两个拖顶点喂的集授合S和T，集合S中存讯放已跑找到们最短摄路径境的顶超点，集合T中存次放当旁前还愈未找践到最松短路路径的仗顶点盼。初钉始状蹲态时解，集烈合S中只疏包含著源点丑，设搞为v0，然后毫从集快合T中选李择到愿源点v0路径把长度济最短麦的顶熟点u加入乞到集泄合S中，卷集合S中每洋加入炊一个葬新的楼顶点u都要烫修改铲源点v0到集折合T中剩拳余顶嘱点的膏当前肝最短瞒路径怪长度嘴值，私集合T中各名顶点晕的新晴的当喊前最笨短路述径长助度值艳，为萍原来断的当她前最神短路佳径长先度值倒与从车源点叨过顶素点u到达派该顶定点的碍路径箭长度扬中的素较小砌者。乏此过史程不居断重从复，咐直到赖集合T中的柴顶点停全部纺加入低到集习合S中为盾止。狄克假斯特双拉算执法求闯从顶伐点A到其得余各穗顶点狂最短郊路径镜的过披程二、狄克僚斯特童拉函对数设划计参数寸设计晶：函数放共有烂4个拒参数疏，其侮中2距个为判输入庄参数误，分套别为稼带权勒图G和源绍点序引号v0约；2个为遍输出啊参数会，分披别为di认st歪an搞ce飘[]和pa更th南[]浴，d兼is逆ta熔nc沸e[债]用来畏存放屡得到效的从朽源点v0到其歌余各穿顶点互的最纲短距变离数聋值，pa铁th弓[]用来猪存放罗得到跨的从成源点v0到其摊余各腐顶点桥的最逆短路闲径上若到达庸目标糊顶点绞的前舅一顶满点下辫标。狄克榴斯特愧拉函无数设忍计：vo慰idDi纲jk血st室ra航(A早dj税MG钩ra查phG,in纪tv0向,in悬tdi密st买an循ce疏[]汉,in括tpa象th订[]妙)/*带权方图G从下担标v0顶点依到其本它顶优点的响最短吹距离di尝st史an扣ce怠*//*和最寒短路题径下闷标pa济th牙*/{in肆tn饭=G.山Ve啄rt厕ic钟es搞.s床iz乌e;in葱t*s遥=循(in配t*)ma工ll汁oc怀(s激iz我eo州f(坐in庭t)*呆n)咐;in桃tmi昏nD把is,齿i,猎j蜡,终u;/*拖初始首化*艳/fo冲r(宝i=杏0;绢i恐<岔n带;蕉i赶++村){di社st观an剧ce摔[i]划=当G.分ed晒ge哥[v若0]汤[i跃];s[幕i]挽=罗0;if叉(i!=争v负0炒&&di芝st垦an竞ce笨[i]段<Ma扇xW降ei搁gh扬t)pa多th床[i]纵=叉v0奖;el蛾sepa估th漏[i]扁=钳-1摸;}s[方v0续]逝=巧1;/*偷在还哨未找樱到最眉短路茄径的医顶点拜集中握选有港最短戏距离悼的顶隔点u*雹/fo块r(肝i=带1;近i顽<暂n精;代i泼++太){mi素nD羽is=Ma哥xW金ei恼gh谈t;fo罗r(筑j=逼0;针j<n;绩j++幸)if阅(s喇[j]虾==隔0构&埋&di凑st如an璃ce坑[j]友<mi锄nD宿is){践u常=延j盈;mi诸nD称is=di烫st赤an矮ce躺[j];叛}/*当已峰不再糕存在提路径签时算秀法结星束*锦/if篮(m马in跳Di抹s==Ma询xW喝ei斧gh平t)织re成tu惧rn福;s[水u]冠=伸1;江/旺*标记嗓顶点u已从申集合T加入粗到集跟合S中*巩//*壮修改腰从v0到其要它顶抓点的苍最短辩距离浴和最冤短路猴径*借/fo狭r(坟j=理0;缴j腥<垒n恢;这j+浴+)if池(s仆[j]况==墨0聪&袄&G.宵ed垒ge条[u荐][在j]笔<Ma捐xW元ei屡gh郑t&&di叠st迫an拥ce崖[u]围+G.怎ed罪ge洒[u警][己j]述<di测st渣an添ce多[j]){di芹st草an巷ce鲜[j]翅=di拿st香an第ce赢[u]壳+G.丘ed堵ge屿[u归][搏j];pa滤th浅[j]效=夺u;}}}三、凶测试吊程序例9-详4：以图9-惊13的有敌向带匆权图隔为例事设计始测试粪上述Di络jk遵st用ra函数滥的程使序。3.每对爆顶点涌之间粥的最贱短路萌径带权蛋有向宰图，得每对膜顶点隔之间武的最狼短路纤径可马通过晴调用都狄克堤斯特耍拉算眯法实定现。具体循方法糊是：暖每次练以不吉同的捉顶点镰作为芹源点娇，调煤用狄触克斯园特拉扣算法浊求出勒从该顷源点犹到其佛余顶触点的陶最短勤路径识。重复n次就可群求出晚每对唐顶点待之间熔的最篮短路桑径。销由于旗狄克撒斯特冠拉算汗法的咬时间黎复杂简度为O(n2)，所以父这种算法针的时牛间复盐杂度活为O(n3)。弗洛尖伊德呢算法项的思赠想是而：设矩绪阵co盛st用来熟存放苗带权恋有向殊图G的权盼值，摩即矩就阵元琴素co关st博[i][你j]中存误放着慌下标眼为i的顶板点到遵下标兽为j的顶誓点之钢间的准权值疑，可危以通台过递况推构危造一棵个矩倚阵序贺列A0,A1,A2,…抱…,AN来求桂每对邪顶点树之间伍的最盖短路盟径。午其中让，Ak[i][j]（略0≤k≤n）表示容从顶馆点vi到顶胀点vj的路鸟径上夸所经敬过的红顶点罢下标你不大扯于k的最恳短路展径长委度。逗初始薪时有穿，A0[i][j]=co歌st耽[i][j]。一种夺情况雹是该叛路径活不经粥过下固标为k+1的顶竹点，印此时铃该路哑径长收度与踢从顶恢点vi到顶签点vj的路丢径上卖所经许过的伍顶点掩下标习不大凡于k的最惨短路吐径长过度相光同；另一河种情含况是欧该路趟径经企过下罗标为k+1的顶斧点，剃此时冷该路桶径可瘦分为地两段宴，一婶段是绍从顶恭点vi到顶有点vk+桥1的最揭短路工径，法另一壶段是烂从顶邻点vk+岸1到顶姻点vj的最阵短路肢径，偷此时长的最道短路唇径长千度等步于这摘两段段最短资路径扛长度初之和并。当已码经求得出Ak,要递吃推求物解Ak+改1时，律有：这两退种情透况中殃的路访径长粱度较馋小者们，就纽奉是要窜求的吴从顶养点vi到顶讯点vj的路疤径上该所经堆过的舒顶点阴下标浮不大愉于k+1的最胸短路托径长塑度。用公家式描录述为陶：A0[i][j]=碧co世st天[i][j]Ak+1[i][j]=mi市n{Ak[i][j],Ak[i][k+1拜]+Ak[k+1枕][j]}登（丘0≤k≤n-1掠）9.免7拓扑雨排序1．偏蔽序关隆系和系全序疼关系拓扑漫排序寸就是驼要由忍某个隆集合世上的杨偏序枯关系脑得到赞该集溪合上黑的全机序关涂系。若集该合X上的沫关系R是自洞反的瞒、反渠对称骄的和棋传递碑的，汤则称夺关系R是集苏合X上的稳偏序大关系婶（或茂称半窜序关贷系）蜘。设关育系R为定球义在们集合X上的只二元蛋关系敞，若季对于鸦每一国个x∈纷X，都作有(x,星x)袄∈R，则逗称R是自文反的民。设关宅系R为定仍义在常集合X上的沃二元臂关系贞，如膏果对尝于任详意的x,垮y,谎z∈称X，若副当(x,渴y)责∈R且(y,懂z)湿∈R时，奇有(x,均z)库∈R，则然称关记系R是传栏递的赌。设关固系R为定表义在瓦集合X上的宅二元鞭关系器，若溜对于波所有朴的x,呢y∈丘X，若辟当(x,赛y)这∈R且(y,扣x)侄∈R时，坟有x=锈y，则第称关哲系R是反办对称捎的。例如策，设X是实姐数集歉合，R为小钞于等哀于关拿系，腊即R=捎{(x,叉y)龄|x茧∈X跳∧y斩∈X扒∧x当≤y}，由向于当x≤挽y且y≤敲x时有x＝y，因路此，洲关系R是反较对称渠关系蹲。另驱