【正文】 T G )()( TVGV ? )()( GETE ?T G GG )(G?G)()()( eGeGG ???? ???其中 表示從 上刪除邊 ， 表示把 的長(zhǎng)度收縮為零得到的圖。若圖 滿足 ， ，則稱 是 的生成樹(shù)。 end index2(temp)=index。 index=index1(find(d(index1)==d(temp)a(temp,index1)))。 pb(temp)=1。 tmpb=find(d(tb)==min(d(tb)))。 while sum(pb)length(a) tb=find(pb==0)。d(1)=0。index2=ones(1,length(a))。pb(1)=1。 a=a+a39。 a(5,:)=[zeros(1,5),55]。 a(3,:)=[zeros(1,3),10,20,M]。 a(1,:)=[0,50,M,40,25,10]。 clc。其中分量 ； 存放始點(diǎn)到第 點(diǎn)最短通路中第 頂點(diǎn)前一頂點(diǎn)的序號(hào)； 存放由始點(diǎn)到第 點(diǎn)最短通路的值。（ 表示無(wú)直接航路），請(qǐng)幫助該公司設(shè)計(jì)一張 城市 到其它城市間的票價(jià)最便宜的路線圖。若在算法運(yùn)行過(guò)程中，將每一頂點(diǎn)獲得 P標(biāo)號(hào) 所由來(lái)的邊在圖上標(biāo)明，則算法結(jié)束時(shí)， 至各項(xiàng)點(diǎn)的最短路也在圖上標(biāo)示出來(lái)了。在 進(jìn)入 之前的標(biāo)號(hào)叫 T標(biāo)號(hào)， 進(jìn)入 時(shí)的標(biāo)號(hào)叫 P標(biāo)號(hào)。 iSv? ii SVS \?)}()(),({m i n uvwulvliSu ??)(vl )}({min vliSv?1?iu}{ 11 ?? ? iii uSS ?(iii). 若 ，停止；若 ，用 代替 ，轉(zhuǎn) (ii)。 0)( 0 ?ul 0uv? ??)(vl }{00 uS ? 0?i(ii) 對(duì)每個(gè) （ ），用 代替 。為避免重復(fù)并保留每一步的計(jì)算信息，采用了標(biāo)號(hào)算法 .下面是該算法。這條軌叫做 間的最短路，它的權(quán)叫做 間的距離， 亦記作 。 G的子圖的權(quán)是指子圖的各邊的權(quán)和。 應(yīng)用 ?兩個(gè)指定頂點(diǎn)之間的最短距離 00,vu問(wèn)題如下：給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間， 找一條最短鐵路線 以各城鎮(zhèn)為圖 G的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖 G相應(yīng)兩頂點(diǎn)間的邊，得圖 G。記作 d(u,v)。起點(diǎn)和終點(diǎn)重合的軌叫做圈 . 若圖 G的兩個(gè)頂點(diǎn) u,v間存在道路，則稱 u和 v連通 (connected)。若道路 W的頂點(diǎn)互不相同，則 W稱為軌 (path)。頂點(diǎn) 稱為 W的起點(diǎn) 和終點(diǎn)。其中 與 關(guān)聯(lián)。又如，在鄰接表和星形表示法中，每條 邊會(huì)被存儲(chǔ)兩次，而且反向星形表示顯然是沒(méi)有必要的，等等。例如，可以在計(jì)算機(jī)中只存儲(chǔ)鄰接矩陣的一半信息 （如上三角部分），因?yàn)榇藭r(shí)鄰接矩陣是對(duì)稱矩陣。其他方法則可以很方便地推廣到可以處理平行弧的情形。有關(guān)“計(jì)算時(shí)間”的觀念是網(wǎng)絡(luò)優(yōu)化中需要考慮的一個(gè)關(guān)鍵因素。星形表示法的優(yōu)點(diǎn)是占用 的存儲(chǔ)空間較少，并且對(duì)那些不提供指針類型的語(yǔ)言（如 FORTRAN語(yǔ)言等）也容易實(shí)現(xiàn)。例如，可以在 采用前向星形表示法的基礎(chǔ)上，加上上面介紹的數(shù)組和如下的數(shù)組即可。例如，例 7所示的圖，可以用反向星 形表示法表示為如下形式： 節(jié)點(diǎn)對(duì)應(yīng)的入弧的起始地址編號(hào)數(shù)組（記為） 節(jié)點(diǎn)號(hào) 1 2 3 4 5 6 起始地址 1 1 3 6 8 9 )(irpointi記錄弧信息的數(shù)組 弧編號(hào) 1 2 3 4 5 6 7 8 終點(diǎn) 2 2 3 3 3 4 4 5 起點(diǎn) 3 1 1 4 5 5 2 4 權(quán) 4 8 9 0 6 7 6 3 如果既希望快速檢索每個(gè)節(jié)點(diǎn)的所有出弧，也希望快速檢索每個(gè)節(jié)點(diǎn)的所有入弧，則 可以綜合采用前向和反向星形表示法。對(duì)每條弧，仍然依次存放其起點(diǎn)、終點(diǎn)、權(quán)的數(shù)值等有 關(guān)信息。 )1()( ?? ip o in tip o in tpoint前向星形表示法有利于快速檢索每個(gè)節(jié)點(diǎn)的所有出弧，但不能快速檢索每個(gè)節(jié)點(diǎn)的所 有入弧。這種表示法與弧表表示法也非常相 似，“記錄弧信息的數(shù)組”實(shí)際上相當(dāng)于有序存放的“弧表”。此時(shí)該網(wǎng)絡(luò)圖可 以用前向星形表示法表示如下： 節(jié)點(diǎn)對(duì)應(yīng)的出弧的起始地址編號(hào)數(shù)組（記為） 節(jié)點(diǎn)號(hào) i起始地址 )(ipoint1 2 3 4 5 6 1 3 4 6 7 9 記錄弧信息的數(shù)組 弧編號(hào) 1 2 3 4 5 6 7 8 起點(diǎn) 1 1 2 3 4 4 5 5 終點(diǎn) 2 3 4 2 3 5 3 4 權(quán) 8 9 6 4 0 3 6 7 在數(shù)組中，其元素個(gè)數(shù)比圖的節(jié)點(diǎn)數(shù)多 1（即 n+1），且一定有 ， 。在這種表示法中，可以 快速檢索從每個(gè)節(jié)點(diǎn)出發(fā)的所有弧，這種星形表示法稱為前向星形（ forward star）表示法。這實(shí)際上相當(dāng)于對(duì)所有弧給出了一個(gè)順序和編號(hào)，只是從同一節(jié)點(diǎn)出發(fā) 的弧的順序可以任意排列。也 就是說(shuō)，在該數(shù)組中首先存放從節(jié)點(diǎn) 1出發(fā)的所有弧，然后接著存放從節(jié)點(diǎn) 2出發(fā)的所有孤 ，依此類推，最后存放從節(jié)點(diǎn)出發(fā)的所有孤。 )(iA i i}3,2{)1( ?A， }4,3{)5( ?A （ v）星形表示法 星形（ star）表示法的思想與鄰接表表示法的思想有一定的相似之處。例如上面例子 ， ，等。又 如，第 5行說(shuō)明節(jié)點(diǎn) 5出發(fā)的弧有 (5,3)、 (5,4)，他們對(duì)應(yīng)的權(quán)分別為 6和 7。每個(gè)指針單元的第 1 個(gè)數(shù)據(jù)域表示弧的另一個(gè)端點(diǎn)（弧的頭），后面的數(shù)據(jù)域表示對(duì)應(yīng)弧上的權(quán)。圖的整個(gè)鄰接表可以用一個(gè)指針數(shù)組 表示。鄰接表表示法就是對(duì)圖的每個(gè)節(jié)點(diǎn)，用一個(gè)單向鏈表列出從該節(jié)點(diǎn)出發(fā)的所有 弧，鏈表中每個(gè)單元對(duì)應(yīng)于一條出弧。 （ iv）鄰接表表示法 鄰接表表示法將圖以鄰接表（ adjacency lists）的形式存儲(chǔ)在計(jì)算機(jī)中。此外，對(duì)于網(wǎng)絡(luò)圖中每條弧上的權(quán)，也要對(duì)應(yīng)地用額 外的存儲(chǔ)單元表示。所謂圖的弧表，也就是圖的 弧集合中的所有有序?qū)?。如果網(wǎng)絡(luò)中每條弧賦有多個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加相應(yīng)的行數(shù)，把 每一條弧所對(duì)應(yīng)的權(quán)存儲(chǔ)在增加的行中。 例 8 對(duì)于例 7所示的圖，如果關(guān)聯(lián)矩陣中每列對(duì)應(yīng)弧的順序?yàn)?(1,2)， (1,3)， (2,4)， (3,2)， (4,3)， (4,5)， (5,3)和 (5,4)，則關(guān)聯(lián)矩陣表示為 : ????????????????????????1110000010110100010110100000110100000011同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以通過(guò)對(duì)關(guān)聯(lián)矩陣的擴(kuò)展來(lái)表示。 如果網(wǎng)絡(luò)比較稀疏，這種表示法也會(huì)浪費(fèi)大量的存儲(chǔ)空間?？梢钥闯觯@ 種表示法也非常簡(jiǎn)單、直接。如果一個(gè) 節(jié)點(diǎn)是一條弧的起點(diǎn)，則關(guān)上聯(lián)矩陣中對(duì)應(yīng)的元素為 1；如果一個(gè)節(jié)點(diǎn)是一條弧的終點(diǎn)， 則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為 1；如果一個(gè)節(jié)點(diǎn)與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素 為 0。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個(gè)矩陣表示 這些權(quán)。 2n m例 7 對(duì)于上圖所示的圖，可以用鄰接矩陣表示為 ????????????????0110010100000100100000110， 同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。但是，在鄰接矩陣的所有 個(gè)元素中，只有 個(gè)為非零元。 圖 的鄰接矩陣是如下定義的： 是一個(gè) 的 矩陣，即 ),( AVG ? C nn? 10?nnnnijcC ?? ?? }1,0{)(??????.),(,0,),(,1AjiAjicij也就是說(shuō)，如果兩節(jié)點(diǎn)之間有一條弧，則鄰接矩陣中對(duì)應(yīng)的元素為 1；否則為 0。對(duì)于有多重邊或 無(wú)向網(wǎng)絡(luò)的情況，我們只是在討論完簡(jiǎn)單有向圖的表示方法之后，給出一些說(shuō)明。這里我們 介紹計(jì)算機(jī)上用來(lái)描述圖與網(wǎng)絡(luò)的 5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表 示法、弧表表示法、鄰接表表示法和星形表示法。 圖與網(wǎng)絡(luò)的數(shù)