第五章 樹和二叉樹

樹和二叉樹的定義

1射富、樹的定義

一種非線性結(jié)構(gòu)。樹是遞歸結(jié)構(gòu)盆色，在樹的定義中又用到了樹的概念灰蛙。

基本術(shù)語：

樹結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹的分支；

孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子隔躲；

雙親結(jié)點(diǎn)：B結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子摩梧，則A結(jié)點(diǎn)是B結(jié)點(diǎn)的雙親；

兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)宣旱；

堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)仅父；

結(jié)點(diǎn)層次：根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)浑吟，依此類推笙纤；

樹的高（深）度：樹中最大的結(jié)點(diǎn)層

結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個(gè)數(shù)

樹的度： 樹中最大的結(jié)點(diǎn)度。

葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)组力，是度為0的結(jié)點(diǎn)省容；

分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)（非終端結(jié)點(diǎn)）；

森林：互不相交的樹集合燎字；

有序樹：子樹有序的樹蓉冈，如：家族樹；

無序樹：不考慮子樹的順序轩触；

2寞酿、樹的基本定義

3、二叉樹的定義

二叉樹

二叉樹可以為空脱柱。二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹伐弹，即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹榨为，還是右子樹惨好。這是二叉樹與樹的最主要的差別。注意區(qū)分：二叉樹随闺、二叉查找樹/二叉排序樹/二叉搜索樹日川、二叉平衡(查找)樹二叉平衡樹肯定是一顆二叉排序樹。堆不是一顆二叉平衡樹矩乐。二叉樹與樹是不同的龄句，二叉樹不等價(jià)于分支樹最多為二的有序樹回论。當(dāng)一個(gè)結(jié)點(diǎn)只包含一個(gè)子節(jié)點(diǎn)時(shí)，對于有序樹并無左右孩子之分分歇，而對于二叉樹來說依然有左右孩子之分傀蓉，所以二叉樹與樹是兩種不同的結(jié)構(gòu)。

1职抡、二叉樹的性質(zhì)

性質(zhì)：

在二叉樹的第 i 層上至多有2i-1個(gè)結(jié)點(diǎn)葬燎。

深度為 k 的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)（k≥1）

對任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)缚甩、n2個(gè)度為 2 的結(jié)點(diǎn)谱净，則必存在關(guān)系式：n0= n2+1。

具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為?log2 n?+1 擅威。

n個(gè)結(jié)點(diǎn)的二叉樹中壕探，完全二叉樹具有最小的路徑長度。

如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號,則對任一結(jié)點(diǎn)i（1<=i<=n),有：

如果i＝1裕寨，則結(jié)點(diǎn)i無雙親浩蓉，是二叉樹的根；如果i>1宾袜，則其雙親的編號是 i/2(整除）捻艳。

如果2i>n，無左孩子庆猫；否則认轨，其左孩子是結(jié)點(diǎn)2i。

如果2i＋1>n月培，則結(jié)點(diǎn)i無右孩子嘁字；否則，其右孩子是結(jié)點(diǎn)2i＋1杉畜。

2纪蜒、二叉樹的存儲結(jié)構(gòu)

二叉樹的存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)：僅僅適用于滿或完全二叉樹，結(jié)點(diǎn)之間的層次關(guān)系由性質(zhì)5確定此叠。

二叉鏈表法：每個(gè)節(jié)點(diǎn)存儲左子樹和右子樹纯续。三叉鏈表：左子樹、右子樹灭袁、父節(jié)點(diǎn)猬错，總的指針是n+2

在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為n-1茸歧。在有N個(gè)結(jié)點(diǎn)的二叉鏈表中必定有2N個(gè)鏈域倦炒。除根結(jié)點(diǎn)外，其余N-1個(gè)結(jié)點(diǎn)都有一個(gè)父結(jié)點(diǎn)软瞎。所以逢唤，一共有N-1個(gè)非空鏈域拉讯，其余2N-(N-1)=N+1個(gè)為空鏈域。

二叉鏈存儲法也叫孩子兄弟法智玻，左指針指向左孩子遂唧，右指針指向右兄弟芙代。而中序遍歷的順序是左孩子吊奢，根，右孩子纹烹。這種遍歷順序與存儲結(jié)構(gòu)不同页滚，因此需要堆棧保存中間結(jié)果。而中序遍歷檢索二叉樹時(shí)铺呵，由于其存儲結(jié)構(gòu)跟遍歷順序相符裹驰，因此不需要用堆棧。

遍歷二叉樹和線索二叉樹

1片挂、遍歷二叉樹

遍歷二叉樹：使得每一個(gè)結(jié)點(diǎn)均被訪問一次幻林，而且僅被訪問一次。非遞歸的遍歷實(shí)現(xiàn)要利用棧音念。

先序遍歷DLR：根節(jié)點(diǎn)->左子樹->右子樹

中序遍歷LDR：左子樹->根節(jié)點(diǎn)->右子樹沪饺。必須要有中序遍歷才能得到一棵二叉樹的正確順序

后續(xù)遍歷LRD：左子樹->右子樹->根節(jié)點(diǎn)。需要棧的支持闷愤。

層次遍歷：用一維數(shù)組存儲二叉樹時(shí),總是以層次遍歷的順序存儲結(jié)點(diǎn)整葡。層次遍歷應(yīng)該借助隊(duì)列。

2讥脐、線索二叉樹

線索二叉樹：對二叉樹所有結(jié)點(diǎn)做某種處理可在遍歷過程中實(shí)現(xiàn)遭居；檢索（查找）二叉樹某個(gè)結(jié)點(diǎn)，可通過遍歷實(shí)現(xiàn)旬渠；如果能將二叉樹線索化俱萍，就可以簡化遍歷算法，提高遍歷速度告丢，目的是加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度枪蘑。

如何線索化？以中序遍歷為例芋齿，若能將中序序列中每個(gè)結(jié)點(diǎn)前趨腥寇、后繼信息保存起來，以后再遍歷二叉樹時(shí)就可以根據(jù)所保存的結(jié)點(diǎn)前趨觅捆、后繼信息對二叉樹進(jìn)行遍歷赦役。對于二叉樹的線索化，實(shí)質(zhì)上就是遍歷一次二叉樹栅炒，只是在遍歷的過程中掂摔，檢查當(dāng)前結(jié)點(diǎn)左术羔，右指針域是否為空，若為空乙漓，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索级历。前驅(qū)就是在這一點(diǎn)之前走過的點(diǎn)，不是下一將要去往的點(diǎn)叭披。

加上結(jié)點(diǎn)前趨后繼信息（結(jié)索）的二叉樹稱為線索二叉樹寥殖。n個(gè)結(jié)點(diǎn)的線索二叉樹上每個(gè)結(jié)點(diǎn)有2個(gè)指針域（指向左孩子和右孩子），總共有2n個(gè)指針域涩蜘；一個(gè)n個(gè)結(jié)點(diǎn)的樹有n-1條邊嚼贡，那么空指針域= 2n - (n-1) = n + 1，即線索數(shù)為n+1同诫。指針域tag為0粤策，存放孩子指針，為1误窖，存放前驅(qū)/后繼節(jié)點(diǎn)指針叮盘。

線索樹下結(jié)點(diǎn)x的前驅(qū)與后繼查找：設(shè)結(jié)點(diǎn)x相應(yīng)的左（右）標(biāo)志是線索標(biāo)志，則lchild(rchild)就是前驅(qū)(后繼）霹俺，否則：

LDR–前驅(qū)：左子樹中最靠右邊的結(jié)點(diǎn)柔吼；后繼：右子樹中最靠左邊的結(jié)點(diǎn)

LRD–前驅(qū)：右子樹的根，若無右子樹吭服，為左子樹跟嚷堡。后繼：x是根，后繼是空艇棕；x是雙親的右孩子蝌戒、x是雙親的左孩子，但雙親無右孩子沼琉，雙親是后繼北苟；x是雙親的左孩子，雙親有右孩子打瘪，雙親右子樹中最左的葉子是后繼

DLR–對稱于LRD線索樹—將LRD中所有左右互換友鼻，前驅(qū)與后繼互換，得到DLR的方法闺骚。

為簡化線索鏈表的遍歷算法彩扔，仿照線性鏈表，為線索鏈表加上一頭結(jié)點(diǎn)僻爽，約定：

頭結(jié)點(diǎn)的lchild域：存放線索鏈表的根結(jié)點(diǎn)指針虫碉；

頭結(jié)點(diǎn)的rchild域: 中序序列最后一個(gè)結(jié)點(diǎn)的指針；

中序序列第一結(jié)點(diǎn)lchild域指向頭結(jié)點(diǎn);

中序序列最后一個(gè)結(jié)點(diǎn)的rchild域指向頭結(jié)點(diǎn);

中序遍歷的線索二叉樹以及線索二叉樹鏈表示意圖

一棵左右子樹均不空的二叉樹在前序線索化后,其中空的鏈域的個(gè)數(shù)是1胸梆。前序和后續(xù)線索化后空鏈域個(gè)數(shù)都是1敦捧，中序是2须板。二叉樹在線索化后，仍不能有效求解的問題是前序求前序先驅(qū)兢卵，后序求后序后繼习瑰。

中序遍歷的順序?yàn)椋鹤蟆⒏嗷纭⒂姨鹧伲詫τ诿恳环强盏木€索，左子樹結(jié)點(diǎn)的后繼為根結(jié)點(diǎn)王滤，右子樹結(jié)點(diǎn)的前驅(qū)為根結(jié)點(diǎn)贺嫂，再遞歸的執(zhí)行上面的過程滓鸠，可得非空線索均指向其祖先結(jié)點(diǎn)雁乡。在中序線索二叉樹中,每一非空的線索均指向其祖先結(jié)點(diǎn)。

在二叉樹上加上結(jié)點(diǎn)前趨糜俗、后繼線索后踱稍，可利用線索對二叉樹進(jìn)行遍歷,此時(shí)，不需棧悠抹，也不需遞歸珠月。基本步驟：

p=T->lchild; p指向線索鏈表的根結(jié)點(diǎn)楔敌；

若線索鏈表非空啤挎，循環(huán)：

循環(huán)，順著p左孩子指針找到最左下結(jié)點(diǎn)卵凑；訪問之庆聘；

若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索，p的右孩子結(jié)點(diǎn)即為后繼結(jié)點(diǎn)循環(huán)： p=p->rchild勺卢； 并訪問p所指結(jié)點(diǎn)伙判；（在此循環(huán)中，順著后繼線索訪問二叉樹中的結(jié)點(diǎn)）

一旦線索“中斷”黑忱，p所指結(jié)點(diǎn)的右孩子域?yàn)橛液⒆又羔樠绺В琾=p->rchild，使 p指向右孩子結(jié)點(diǎn)甫煞；

樹和二叉樹抽象數(shù)據(jù)類型定義

樹和森林

1菇曲、樹的存儲結(jié)構(gòu)

樹的存儲結(jié)構(gòu)：

雙親表示法

孩子表示法

利用圖表示樹

孩子兄弟表示法（二叉樹表示法）：鏈表中每個(gè)結(jié)點(diǎn)的兩指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)

將樹轉(zhuǎn)化成二叉樹：右子樹一定為空

加線：在兄弟之間加一連線

抹線：對每個(gè)結(jié)點(diǎn)，除了其左孩子外抚吠，去除其與其余孩子之間的關(guān)系

旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心常潮，將整樹順時(shí)針轉(zhuǎn)45°

2、森林與二叉樹的轉(zhuǎn)換

將各棵樹分別轉(zhuǎn)換成二叉樹

將每棵樹的根結(jié)點(diǎn)用線相連

以第一棵樹根結(jié)點(diǎn)為二叉樹的根

3埃跷、樹與森林的遍歷

樹與轉(zhuǎn)換后的二叉樹的關(guān)系：轉(zhuǎn)換后的二叉樹的先序?qū)?yīng)樹的先序遍歷蕊玷；轉(zhuǎn)換后的二叉樹的中序?qū)?yīng)樹的后序遍歷

哈夫曼樹/霍夫曼樹及其應(yīng)用

1邮利、哈夫曼樹的基本概念

2、哈夫曼樹的構(gòu)造算法

3垃帅、哈夫曼編碼

哈弗曼樹概念：

路徑：從一個(gè)祖先結(jié)點(diǎn)到子孫結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的路徑延届；

路徑長度：路徑上的分支數(shù)目稱為路徑長度；

樹的路徑長度：從根到每個(gè)結(jié)點(diǎn)的路徑長度之和贸诚。

結(jié)點(diǎn)的權(quán)：根據(jù)應(yīng)用的需要可以給樹的結(jié)點(diǎn)賦權(quán)值方庭；

結(jié)點(diǎn)的帶權(quán)路徑長度：從根到該結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)權(quán)的乘積；

樹的帶權(quán)路徑長度=樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑之和酱固；通常記作 WPL=∑wi×li

哈夫曼樹：假設(shè)有n個(gè)權(quán)值(w1, w2, … , wn)械念，構(gòu)造有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)有一個(gè) wi作為它的權(quán)值运悲。則帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹龄减。最優(yōu)二叉樹。

前綴碼的定義：在一個(gè)字符集中班眯，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴希停。霍夫曼編碼就是前綴碼署隘，可用于快速判斷霍夫曼編碼是否正確宠能。霍夫曼樹是滿二叉樹磁餐，若有n個(gè)節(jié)點(diǎn)违崇，則共有(n+1)/2個(gè)碼子

給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹诊霹，若帶權(quán)路徑長度達(dá)到最小羞延，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為霍夫曼樹(Huffman Tree)畅哑‰瓤霍夫曼樹是帶權(quán)路徑長度最短的樹顷扩，權(quán)值較大的結(jié)點(diǎn)離根較近曲楚。

假設(shè)哈夫曼樹是二叉的話麻捻，則度為0的結(jié)點(diǎn)個(gè)數(shù)為N摄闸，度為2的結(jié)點(diǎn)個(gè)數(shù)為N-1挟阻，則結(jié)點(diǎn)總數(shù)為2N-1详恼。哈夫曼樹的結(jié)點(diǎn)個(gè)數(shù)必為奇數(shù)房午。

哈夫曼樹不一定是完全二叉樹墓赴，但一定是最優(yōu)二叉樹媚创。

若度為m的哈夫曼樹中,其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為[(n-1)/(m-1)]渗钉。邊的數(shù)目等于度。

第六章 圖

圖的定義和基本術(shù)語

1、圖的定義——一種非線性結(jié)構(gòu)鳄橘。樹是遞歸結(jié)構(gòu)声离，在樹的定義中又用到了樹的概念。

2瘫怜、圖的基本術(shù)語

3术徊、圖的類型定義

無向圖

回路或環(huán)：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。

簡單回路或簡單環(huán)：除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外鲸湃，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路

連通：頂點(diǎn)v至v’ 之間有路徑存在

連通圖：無向圖圖 G 的任意兩點(diǎn)之間都是連通的赠涮，則稱G是連通圖。

連通分量：極大連通子圖暗挑，子圖中包含的頂點(diǎn)個(gè)數(shù)極大

所有頂點(diǎn)度的和必須為偶數(shù)

有向圖：

回路或環(huán)：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑笋除。

簡單回路或簡單環(huán)：除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路炸裆。

連通：頂點(diǎn)v至v’之間有路徑存在

強(qiáng)連通圖：有向圖G的任意兩點(diǎn)之間都是連通的垃它，則稱G是強(qiáng)連通圖。各個(gè)頂點(diǎn)間均可達(dá)晒衩。

強(qiáng)連通分量：極大連通子圖

有向圖頂點(diǎn)的度是頂點(diǎn)的入度與出度之和嗤瞎。鄰接矩陣中第V行中的1的個(gè)數(shù)是V的出度

生成樹：極小連通子圖。包含圖的所有n個(gè)結(jié)點(diǎn)听系，但只含圖的n-1條邊。在生成樹中添加一條邊之后虹菲，必定會形成回路或環(huán)靠胜。

完全圖：有 n(n-1)/2 條邊的無向圖。其中n是結(jié)點(diǎn)個(gè)數(shù)毕源。必定是連通圖浪漠。

有向完全圖：有n(n-1)條邊的有向圖。其中n是結(jié)點(diǎn)個(gè)數(shù)霎褐。每兩個(gè)頂點(diǎn)之間都有兩條方向相反的邊連接的圖址愿。

一個(gè)無向圖 G=(V,E) 是連通的，那么邊的數(shù)目大于等于頂點(diǎn)的數(shù)目減一：|E|>=|V|-1冻璃，而反之不成立响谓。如果 G=(V,E) 是有向圖，那么它是強(qiáng)連通圖的必要條件是邊的數(shù)目大于等于頂點(diǎn)的數(shù)目：|E|>=|V|省艳，而反之不成立娘纷。沒有回路的無向圖是連通的當(dāng)且僅當(dāng)它是樹，即等價(jià)于：|E|=|V|-1跋炕。

圖的存儲結(jié)構(gòu)

圖的存儲形式

鄰接矩陣和加權(quán)鄰接矩陣

無權(quán)有向圖：出度: i行之和赖晶；入度: j列之和。

無權(quán)無向圖：i結(jié)點(diǎn)的度: i行或i列之和辐烂。

加權(quán)鄰接矩陣：相連為w遏插，不相連為∞

鄰接表

用頂點(diǎn)數(shù)組表捂贿、邊（弧）表表示該有向圖或無向圖

頂點(diǎn)數(shù)組表：用數(shù)組存放所有的頂點(diǎn)胳嘲。數(shù)組大小為圖頂點(diǎn)數(shù)n

邊表（邊結(jié)點(diǎn)表）：每條邊用一個(gè)結(jié)點(diǎn)進(jìn)行表示眷蜓。同一個(gè)結(jié)點(diǎn)的所有的邊形成它的邊結(jié)點(diǎn)單鏈表。

n個(gè)頂點(diǎn)的無向圖的鄰接表最多有n(n-1)個(gè)邊表結(jié)點(diǎn)胎围。有n個(gè)頂點(diǎn)的無向圖最多有n*(n-1)/2條邊吁系，此時(shí)為完全無向圖，而在鄰接表中每條邊存儲兩次白魂，所以有n*(n-1)個(gè)結(jié)點(diǎn)

1汽纤、鄰接矩陣

2、鄰接表

3福荸、十字鏈表

4蕴坪、鄰接多重表

圖的遍歷

深度優(yōu)先搜索利用棧，廣度優(yōu)先搜索利用隊(duì)列

求一條從頂點(diǎn)i到頂點(diǎn)s的簡單路徑–深搜敬锐。求兩個(gè)頂點(diǎn)之間的一條長度最短的路徑–廣搜背传。當(dāng)各邊上的權(quán)值均相等時(shí),BFS算法可用來解決單源最短路徑問題。

圖遍歷與回溯

圖搜索->形成搜索樹

窮舉法台夺。

貪心法径玖。多步?jīng)Q策，每步選擇使得構(gòu)成一個(gè)問題的可能解颤介，同時(shí)滿足目標(biāo)函數(shù)梳星。

回溯法。根據(jù)題意滚朵，選取度量標(biāo)準(zhǔn)冤灾，然后將可能的選擇方法按度量標(biāo)準(zhǔn)所要求順序排好，每次處理一個(gè)量辕近，得到該意義下的最優(yōu)解的分解處理韵吨。

圖

1、深度優(yōu)先搜索

2移宅、廣度優(yōu)先搜索

圖的應(yīng)用

1归粉、生成樹和最小生成樹

每次遍歷一個(gè)連通圖將圖的邊分成遍歷所經(jīng)過的邊和沒有經(jīng)過的邊兩部分，將遍歷經(jīng)過的邊同圖的頂點(diǎn)構(gòu)成一個(gè)子圖吞杭，該子圖稱為生成樹盏浇。因此有DFS生成樹和BFS生成樹。

生成樹是連通圖的極小子圖芽狗，有n個(gè)頂點(diǎn)的連通圖的生成樹必定有n-1條邊,在生成樹中任意增加一條邊绢掰，必定產(chǎn)生回路。若砍去它的一條邊，就會把生成樹變成非連通子圖

最小生成樹：生成樹中邊的權(quán)值(代價(jià))之和最小的樹滴劲。最小生成樹問題是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹攻晒。

Kruskal算法：令最小生成樹集合T初始狀態(tài)為空，在有n個(gè)頂點(diǎn)的圖中選取代價(jià)最小的邊并從圖中刪去班挖。若該邊加到T中有回路則丟棄鲁捏，否則留在T中；依此類推萧芙，直至T中有n-1條邊為止给梅。

Prim算法、Kruskal算法和Dijkstra算法均屬于貪心算法双揪。

Dijkstra算法解決的是帶權(quán)重的有向圖上單源最短路徑問題动羽，該算法要求所有邊的權(quán)重都為非負(fù)值。

Dijkstra算法解決了從某個(gè)原點(diǎn)到其余各頂點(diǎn)的最短路徑問題渔期，由循環(huán)嵌套可知該算法的時(shí)間復(fù)雜度為O(N*N)运吓。若要求任一頂點(diǎn)到其余所有頂點(diǎn)的最短路徑，一個(gè)比較簡單的方法是對每個(gè)頂點(diǎn)當(dāng)做源點(diǎn)運(yùn)行一次該算法疯趟，等于在原有算法的基礎(chǔ)上拘哨，再來一次循環(huán)，此時(shí)整個(gè)算法的復(fù)雜度就變成了O(N*N*N)信峻。

Bellman-Ford算法解決的是一般情況下的單源最短路徑問題倦青，在這里，邊的權(quán)重可以為負(fù)值站欺。該算法返回一個(gè)布爾值姨夹，以表明是否存在一個(gè)從源節(jié)點(diǎn)可以到達(dá)的權(quán)重為負(fù)值的環(huán)路。如果存在這樣一個(gè)環(huán)路矾策，算法將告訴我們不存在解決方案。如果沒有這種環(huán)路存在峭沦，算法將給出最短路徑和它們的權(quán)重贾虽。

2、最短的路徑

3吼鱼、拓?fù)渑判?/p>

雙連通圖和關(guān)節(jié)點(diǎn)

若從一個(gè)連通圖中刪去任何一個(gè)頂點(diǎn)及其相關(guān)聯(lián)的邊蓬豁，它仍為一個(gè)連通圖的話，則該連通圖被稱為重（雙）連通圖菇肃。

若連通圖中的某個(gè)頂點(diǎn)和其相關(guān)聯(lián)的邊被刪去之后地粪，該連通圖被分割成兩個(gè)或兩個(gè)以上的連通分量，則稱此頂點(diǎn)為關(guān)節(jié)點(diǎn)琐谤。

沒有關(guān)節(jié)點(diǎn)的連通圖為雙連通圖若生成樹的根結(jié)點(diǎn)蟆技，有兩個(gè)或兩個(gè)以上的分支，則此頂點(diǎn)(生成樹的根)必為關(guān)節(jié)點(diǎn)；

對生成樹上的任意一個(gè)非葉“頂點(diǎn)”质礼，若其某棵子樹中的所有“頂點(diǎn)”沒有和其祖先相通的回邊旺聚，則該“頂點(diǎn)”必為關(guān)節(jié)點(diǎn)。

一些定義：

事件的最早發(fā)生時(shí)間（ve(j)）：從源點(diǎn)到j(luò)結(jié)點(diǎn)的最長的路徑眶蕉。意味著事件最早能夠發(fā)生的時(shí)間砰粹。

事件的最遲發(fā)生時(shí)間（vl(j)）：不影響工程的如期完工，事件j必須發(fā)生的時(shí)間造挽。

活動ai由弧

有向無環(huán)圖及其應(yīng)用

拓?fù)渑判蚣盍АＴ谟绵徑颖肀硎緢D時(shí),對有n個(gè)頂點(diǎn)和e條弧的有向圖而言時(shí)間復(fù)雜度為O(n+e)。一個(gè)有向圖能被拓?fù)渑判虻某湟獥l件就是它是一個(gè)有向無環(huán)圖饭入。拓?fù)湫蛄形ㄒ徊荒芪ㄒ淮_定有向圖嵌器。

AOV網(wǎng)(Activity On Vertex)：用頂點(diǎn)表示活動，邊表示活動的優(yōu)先關(guān)系的有向圖稱為AOV網(wǎng)圣拄。AOV網(wǎng)中不允許有回路嘴秸，這意味著某項(xiàng)活動以自己為先決條件。

拓?fù)溆行蛐蛄校喊袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列一個(gè)線性序列的過程庇谆。若vi是vj前驅(qū)岳掐，則vi一定在vj之前；對于沒有優(yōu)先關(guān)系的點(diǎn)饭耳，順序任意串述。

拓?fù)渑判颍簩OV網(wǎng)絡(luò)中頂點(diǎn)構(gòu)造拓?fù)溆行蛐蛄械倪^程。方法：

在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之

從圖中刪除該頂點(diǎn)和所有以它為尾的弧

重復(fù)上述兩步寞肖，直至全部頂點(diǎn)均已輸出纲酗；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止(此時(shí)說明圖中有環(huán)）

采用深度優(yōu)先搜索或拓?fù)渑判蛩惴梢耘袛喑鲆粋€(gè)有向圖中是否有環(huán)(回路).深度優(yōu)先搜索只要在其中記錄下搜索的節(jié)點(diǎn)數(shù)n，當(dāng)n大于圖中節(jié)點(diǎn)數(shù)時(shí)退出新蟆，并可以得出有回路觅赊。若有回路，則拓?fù)渑判蛟L問不到圖中所有的節(jié)點(diǎn)琼稻，所以也可以得出回路吮螺。廣度優(yōu)先搜索過程中如果訪問到一個(gè)已經(jīng)訪問過的節(jié)點(diǎn)，可能是多個(gè)節(jié)點(diǎn)指向這個(gè)節(jié)點(diǎn)帕翻，不一定是存在環(huán)鸠补。

算法描述：

把鄰接表中入度為0的頂點(diǎn)依此進(jìn)棧

若棧不空，則

棧頂元素vj退棧并輸出嘀掸；

在鄰接表中查找vj的直接后繼vk紫岩，把vk的入度減1；若vk的入度為0則進(jìn)棧

若棽撬空時(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n泉蝌，則有向圖有環(huán)歇万；否則，拓?fù)渑判蛲戤叀?/p>

AOE網(wǎng)：帶權(quán)的有向無環(huán)圖梨与，其中頂點(diǎn)表示事件堕花，弧表示活動，權(quán)表示活動持續(xù)時(shí)間粥鞋。在工程上常用來表示工程進(jìn)度計(jì)劃缘挽。

4、關(guān)鍵路徑

Java呻粹。大家都知道壕曼，我們是學(xué)Java全棧的，大家就肯定以為我有全套的Java系統(tǒng)教程等浊。沒錯(cuò)腮郊，我是有Java全套系統(tǒng)教程，進(jìn)扣裙【47】974【9726】所示筹燕，今天小編就免費(fèi)送!~

“我們相信人人都可以成為一個(gè)程序員轧飞，現(xiàn)在開始，找個(gè)師兄撒踪，帶你入門过咬，學(xué)習(xí)的路上不再迷茫。這里是ja+va修真院制妄，初學(xué)者轉(zhuǎn)行到互聯(lián)網(wǎng)行業(yè)的聚集地