第六章 圖與網(wǎng)絡(luò)模型

1、第六章 圖與網(wǎng)絡(luò)模型§6.1圖與網(wǎng)絡(luò)的基本概念1.概論 圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736 年發(fā)表的“哥尼斯堡的七座橋”。1847年，克希霍夫?yàn)榱私o出電網(wǎng)絡(luò)方程而引進(jìn)了“樹”的概念。1857年，凱萊在計(jì)數(shù)烷的同分異構(gòu)物時(shí)，也發(fā)現(xiàn)了“樹”。哈密爾頓于1859年提出“周游世界”游戲，用圖論的術(shù)語，就是如何找出一個(gè)連通圖中的生成圈，近幾十年來，由于計(jì)算機(jī)技術(shù)和科學(xué)的飛速發(fā)展，大大地促進(jìn)了圖論研究和應(yīng)用，圖論的理論和方法已經(jīng)滲透到物理、化學(xué)、通訊科學(xué)、建筑學(xué)、生物遺傳學(xué)、心理學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)等學(xué)科中。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們

2、用點(diǎn)表示這些具體事物，用連接兩點(diǎn)的線段（直的或曲的）表示兩個(gè)事物的特定的聯(lián)系，就得到了描述這個(gè)“圖”的幾何形象。圖論為任何一個(gè)包含了一種二元關(guān)系的離散系統(tǒng)提供了一個(gè)數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對(duì)該模型求解。哥尼斯堡七橋問題就是一個(gè)典型的例子。在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩個(gè)島及島與河岸聯(lián)結(jié)起來問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點(diǎn)。當(dāng)然可以通過試驗(yàn)去嘗試解決這個(gè)問題，但該城居民的任何嘗試均未成功。歐拉為了解決這個(gè)問題，采用了建立數(shù)學(xué)模型的方法。他將每一塊陸地用一個(gè)點(diǎn)來代替，將每一座橋用連接相應(yīng)兩點(diǎn)的一條線來代替，從而得到一個(gè)有四個(gè)“點(diǎn)”，七條

3、“線”的“圖”。問題成為從任一點(diǎn)出發(fā)一筆畫出七條線再回到起點(diǎn)。歐拉考察了一般一筆畫的結(jié)構(gòu)特點(diǎn)，給出了一筆畫的一個(gè)判定法則：這個(gè)圖是連通的，且每個(gè)點(diǎn)都與偶數(shù)線相關(guān)聯(lián)，將這個(gè)判定法則應(yīng)用于七橋問題，得到了“不可能走通”的結(jié)果，不但徹底解決了這個(gè)問題，而且開創(chuàng)了圖論研究的先河。圖與網(wǎng)絡(luò)所研究的問題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。下面將要討論的最短路問題、最小費(fèi)用問題和匹配問題等都是圖與網(wǎng)絡(luò)的基本問題。我們首先通過一些例子來了解網(wǎng)絡(luò)優(yōu)化問題。例1 最短路問題（SPPshortest path problem）一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從

4、甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。例2 公路連接問題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最?。坷? 指派問題（assignment problem）一家公司經(jīng)理準(zhǔn)備安排名員工去完成項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的。

5、如何分配工作方案可以使總回報(bào)最大？例4 中國(guó)郵遞員問題（CPPchinese postman problem）一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國(guó)管梅谷教授1960年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問題。例5 旅行商問題（TSPtraveling salesman problem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。例6 運(yùn)輸問題（trans

6、portation problem）某種原材料有個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往個(gè)使用這些原材料的工廠。假定個(gè)產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？上述問題有兩個(gè)共同的特點(diǎn)：一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題；二是它們都易于用圖形的形式直觀地描述和表達(dá)，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)（network）。與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問題就是網(wǎng)絡(luò)最優(yōu)化或稱網(wǎng)絡(luò)優(yōu)化 （netwok optimization）問題。所以上面

7、例子中介紹的問題都是網(wǎng)絡(luò)優(yōu)化問題。由于多數(shù)網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)上的流（flow）為研究的對(duì)象，因此網(wǎng)絡(luò)優(yōu)化又常常被稱為網(wǎng)絡(luò)流（network flows）或網(wǎng)絡(luò)流規(guī)劃等。2.圖與網(wǎng)絡(luò)的一些基本概念。2.1 無向圖一個(gè)無向圖(undirected graph)是由一個(gè)非空有限集合和中某些元素的無序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點(diǎn)集（vertex set）或節(jié)點(diǎn)集（node set）， 中的每一個(gè)元素稱為該圖的一個(gè)頂點(diǎn)（vertex）或節(jié)點(diǎn)（node）；稱為圖的邊集（edge set），中的每一個(gè)元素(即中某兩個(gè)元素的無序?qū)? 記為或 ，被稱為該圖的一條從到的邊（edge）。當(dāng)

8、邊時(shí)，稱為邊的端點(diǎn)，并稱與相鄰（adjacent）；邊稱為與頂點(diǎn)關(guān)聯(lián)（incident）。如果某兩條邊至少有一個(gè)公共端點(diǎn)，則稱這兩條邊在圖中相鄰。邊上賦權(quán)的無向圖稱為賦權(quán)無向圖或無向網(wǎng)絡(luò)（undirected network）。我們對(duì)圖和網(wǎng)絡(luò)不作嚴(yán)格區(qū)分，因?yàn)槿魏螆D總是可以賦權(quán)的。一個(gè)圖稱為有限圖，如果它的頂點(diǎn)集和邊集都有限。圖的頂點(diǎn)數(shù)用符號(hào)或表示，邊數(shù)用或表示。當(dāng)討論的圖只有一個(gè)時(shí)，總是用來表示這個(gè)圖。從而在圖論符號(hào)中我們常略去字母，例如，分別用和代替和。端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)(loop)。一個(gè)圖稱為簡(jiǎn)單圖(simple graph)，如果它既沒有環(huán)也沒有兩條邊連接同一對(duì)頂點(diǎn)。2.2 有向

9、圖定義 一個(gè)有向圖（directed graph或 digraph）是由一個(gè)非空有限集合和中某些元素的有序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點(diǎn)集或節(jié)點(diǎn)集， 中的每一個(gè)元素稱為該圖的一個(gè)頂點(diǎn)或節(jié)點(diǎn)；稱為圖的弧集（arc set），中的每一個(gè)元素(即中某兩個(gè)元素的有序?qū)? 記為或，被稱為該圖的一條從到的?。╝rc）。當(dāng)弧時(shí)，稱為的尾（tail），為的頭（head），并稱弧為的出?。╫utgoing arc），為的入?。╥ncoming arc）。對(duì)應(yīng)于每個(gè)有向圖，可以在相同頂點(diǎn)集上作一個(gè)圖，使得對(duì)于的每條弧，有一條有相同端點(diǎn)的邊與之相對(duì)應(yīng)。這個(gè)圖稱為的基礎(chǔ)圖。反之，給定任意圖，對(duì)于

10、它的每個(gè)邊，給其端點(diǎn)指定一個(gè)順序，從而確定一條弧，由此得到一個(gè)有向圖，這樣的有向圖稱為的一個(gè)定向圖。以下若未指明“有向圖”三字，“圖”字皆指無向圖。2.3 完全圖、二分圖每一對(duì)不同的頂點(diǎn)都有一條邊相連的簡(jiǎn)單圖稱為完全圖(complete graph)。個(gè)頂點(diǎn)的完全圖記為。若，（這里表示集合中的元素個(gè)數(shù)），中無相鄰頂點(diǎn)對(duì)，中亦然，則稱為二分圖(bipartite graph)；特別地，若，則，則稱為完全二分圖，記成。 2.4 子圖圖叫做圖的子圖（subgraph），記作，如果，。若是的子圖，則稱為的母圖。的支撐子圖（spanning subgraph，又成生成子圖）是指滿足的子圖。2.5 頂點(diǎn)的

11、度設(shè)，中與關(guān)聯(lián)的邊數(shù)（每個(gè)環(huán)算作兩條邊）稱為的度(degree)，記作。若是奇數(shù)，稱是奇頂點(diǎn)(odd point)；是偶數(shù)，稱是偶頂點(diǎn)(even point)。關(guān)于頂點(diǎn)的度，我們有如下結(jié)果：(i) (ii) 任意一個(gè)圖的奇頂點(diǎn)的個(gè)數(shù)是偶數(shù)。2.6 圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模型與算法為了在計(jì)算機(jī)上實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計(jì)算機(jī)上來描述圖與網(wǎng)絡(luò)。一般來說，算法的好壞與網(wǎng)絡(luò)的具體表示方法，以及中間結(jié)果的操作方案是有關(guān)系的。這里我們介紹計(jì)算機(jī)上用來描述圖與網(wǎng)絡(luò)的5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表

12、示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)是一個(gè)簡(jiǎn)單有向圖，并假設(shè)中的頂點(diǎn)用自然數(shù)表示或編號(hào)，中的弧用自然數(shù)表示或編號(hào)。對(duì)于有多重邊或無向網(wǎng)絡(luò)的情況，我們只是在討論完簡(jiǎn)單有向圖的表示方法之后，給出一些說明。（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacency matrix）的形式存儲(chǔ)在計(jì)算機(jī)中。圖的鄰接矩陣是如下定義的：是一個(gè)的矩陣，即 ， 也就是說，如果兩節(jié)點(diǎn)之間有一條弧，則鄰接矩陣中對(duì)應(yīng)的元素為1；否則為0?？梢钥闯觯@種表示法非常簡(jiǎn)單、直接。但是，在鄰接矩陣的所有個(gè)元素中，只有個(gè)為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法浪費(fèi)大量的存儲(chǔ)空間，從而增加了在網(wǎng)絡(luò)中查找弧的時(shí)間。例

13、7 對(duì)于右圖所示的圖，可以用鄰接矩陣表示為同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是此時(shí)一條弧所對(duì)應(yīng)的元素不再是1，而是相應(yīng)的權(quán)而已。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個(gè)矩陣表示這些權(quán)。（ii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidence matrix）的形式存儲(chǔ)在計(jì)算機(jī)中圖的關(guān)聯(lián)矩陣是如下定義的：是一個(gè)的矩陣，即 ， 也就是說，在關(guān)聯(lián)矩陣中，每行對(duì)應(yīng)于圖的一個(gè)節(jié)點(diǎn)，每列對(duì)應(yīng)于圖的一條弧。如果一個(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)的元素為；如果一個(gè)節(jié)點(diǎn)與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為0。對(duì)

14、于簡(jiǎn)單圖，關(guān)聯(lián)矩陣每列只含有兩個(gè)非零元（一個(gè)，一個(gè)）?？梢钥闯觯@種表示法也非常簡(jiǎn)單、直接。但是，在關(guān)聯(lián)矩陣的所有個(gè)元素中，只有個(gè)為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法也會(huì)浪費(fèi)大量的存儲(chǔ)空間。但由于關(guān)聯(lián)矩陣有許多特別重要的理論性質(zhì)，因此它在網(wǎng)絡(luò)優(yōu)化中是非常重要的概念。例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)矩陣表示為同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以通過對(duì)關(guān)聯(lián)矩陣的擴(kuò)展來表示。例如，如果網(wǎng)絡(luò)中每條弧有一個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加一行，把每一條弧所對(duì)應(yīng)的權(quán)存儲(chǔ)在增加的行中。如果網(wǎng)絡(luò)中

15、每條弧賦有多個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加相應(yīng)的行數(shù)，把每一條弧所對(duì)應(yīng)的權(quán)存儲(chǔ)在增加的行中。（iii）弧表示法弧表表示法將圖以弧表（arc list）的形式存儲(chǔ)在計(jì)算機(jī)中。所謂圖的弧表，也就是圖的弧集合中的所有有序?qū)??；”肀硎痉ㄖ苯恿谐鏊谢〉钠瘘c(diǎn)和終點(diǎn)，共需個(gè)存儲(chǔ)單元，因此當(dāng)網(wǎng)絡(luò)比較稀疏時(shí)比較方便。此外，對(duì)于網(wǎng)絡(luò)圖中每條弧上的權(quán)，也要對(duì)應(yīng)地用額外的存儲(chǔ)單元表示。例如，例7所示的圖，假設(shè)弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的權(quán)分別為8，9，6，4，0，3，6和7，則弧表表示如下：起點(diǎn)11234455終點(diǎn)23423534權(quán)8964036

16、7為了便于檢索，一般按照起點(diǎn)、終點(diǎn)的字典序順序存儲(chǔ)弧表，如上面的弧表就是按照這樣的順序存儲(chǔ)的。（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacency lists）的形式存儲(chǔ)在計(jì)算機(jī)中。所謂圖的鄰接表，也就是圖的所有節(jié)點(diǎn)的鄰接表的集合；而對(duì)每個(gè)節(jié)點(diǎn)，它的鄰接表就是它的所有出弧。鄰接表表示法就是對(duì)圖的每個(gè)節(jié)點(diǎn)，用一個(gè)單向鏈表列出從該節(jié)點(diǎn)出發(fā)的所有弧，鏈表中每個(gè)單元對(duì)應(yīng)于一條出弧。為了記錄弧上的權(quán)，鏈表中每個(gè)單元除列出弧的另一個(gè)端點(diǎn)外，還可以包含弧上的權(quán)等作為數(shù)據(jù)域。圖的整個(gè)鄰接表可以用一個(gè)指針數(shù)組表示。例如，例7所示的圖，鄰接表表示為這是一個(gè)5維指針數(shù)組，每一維（上面表示法中的每一行）對(duì)

17、應(yīng)于一個(gè)節(jié)點(diǎn)的鄰接表，如第1行對(duì)應(yīng)于第1個(gè)節(jié)點(diǎn)的鄰接表（即第1個(gè)節(jié)點(diǎn)的所有出弧）。每個(gè)指針單元的第1個(gè)數(shù)據(jù)域表示弧的另一個(gè)端點(diǎn)（弧的頭），后面的數(shù)據(jù)域表示對(duì)應(yīng)弧上的權(quán)。如第1行中的“2”表示弧的另一個(gè)端點(diǎn)為2（即弧為（1,2），“8”表示對(duì)應(yīng)弧(1,2)上的權(quán)為8；“3”表示弧的另一個(gè)端點(diǎn)為3（即弧為(1,3)），“9”表示對(duì)應(yīng)?。?，3）上的權(quán)為9。又如，第5行說明節(jié)點(diǎn)5出發(fā)的弧有(5,3)、(5,4)，他們對(duì)應(yīng)的權(quán)分別為6和7。對(duì)于有向圖，一般用表示節(jié)點(diǎn)的鄰接表，即節(jié)點(diǎn)的所有出弧構(gòu)成的集合或鏈表（實(shí)際上只需要列出弧的另一個(gè)端點(diǎn)，即弧的頭）。例如上面例子，等。這種記法我們?cè)诒緯竺鎸?huì)經(jīng)常用

18、到。（v）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對(duì)每個(gè)節(jié)點(diǎn)，它也是記錄從該節(jié)點(diǎn)出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個(gè)單一的數(shù)組表示。也就是說，在該數(shù)組中首先存放從節(jié)點(diǎn)1出發(fā)的所有弧，然后接著存放從節(jié)點(diǎn)2出發(fā)的所有孤，依此類推，最后存放從節(jié)點(diǎn)出發(fā)的所有孤。對(duì)每條弧，要依次存放其起點(diǎn)、終點(diǎn)、權(quán)的數(shù)值等有關(guān)信息。這實(shí)際上相當(dāng)于對(duì)所有弧給出了一個(gè)順序和編號(hào)，只是從同一節(jié)點(diǎn)出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個(gè)節(jié)點(diǎn)出發(fā)的所有弧，我們一般還用一個(gè)數(shù)組記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始地址（即弧的編號(hào)）。在這種表示法中，可以快速檢索從每個(gè)節(jié)點(diǎn)出發(fā)的所有

19、弧，這種星形表示法稱為前向星形（forward star）表示法。例如，在例7所示的圖中，仍然假設(shè)?。?,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的權(quán)分別為8，9，6，4，0，3，6和7。此時(shí)該網(wǎng)絡(luò)圖可以用前向星形表示法表示如下： 節(jié)點(diǎn)對(duì)應(yīng)的出弧的起始地址編號(hào)數(shù)組（記為）節(jié)點(diǎn)號(hào)123456起始地址134679記錄弧信息的數(shù)組弧編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367在數(shù)組中，其元素個(gè)數(shù)比圖的節(jié)點(diǎn)數(shù)多1（即），且一定有，。對(duì)于節(jié)點(diǎn)，其對(duì)應(yīng)的出弧存放在弧信息數(shù)組的位置區(qū)間為，如果，則節(jié)點(diǎn)沒有出弧。這種表示法與弧

20、表表示法也非常相似，“記錄弧信息的數(shù)組”實(shí)際上相當(dāng)于有序存放的“弧表”。只是在前向星形表示法中，弧被編號(hào)后有序存放，并增加一個(gè)數(shù)組（）記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始編號(hào)。前向星形表示法有利于快速檢索每個(gè)節(jié)點(diǎn)的所有出弧，但不能快速檢索每個(gè)節(jié)點(diǎn)的所有入弧。為了能夠快速檢索每個(gè)節(jié)點(diǎn)的所有入孤，可以采用反向星形（reverse star）表示法：首先存放進(jìn)入節(jié)點(diǎn)1的所有孤，然后接著存放進(jìn)入節(jié)點(diǎn)2的所有弧，依此類推，最后存放進(jìn)入節(jié)點(diǎn)的所有孤。對(duì)每條弧，仍然依次存放其起點(diǎn)、終點(diǎn)、權(quán)的數(shù)值等有關(guān)信息。同樣，為了能夠快速檢索從每個(gè)節(jié)點(diǎn)的所有入弧，我們一般還用一個(gè)數(shù)組記錄每個(gè)節(jié)點(diǎn)的入孤的起始地址（即弧的編號(hào)）。例如

21、，例7所示的圖，可以用反向星形表示法表示為如下形式：節(jié)點(diǎn)對(duì)應(yīng)的入弧的起始地址編號(hào)數(shù)組（記為）節(jié)點(diǎn)號(hào)123456起始地址113689記錄弧信息的數(shù)組弧編號(hào)12345678終點(diǎn)22333445起點(diǎn)31145524權(quán)48906763如果既希望快速檢索每個(gè)節(jié)點(diǎn)的所有出弧，也希望快速檢索每個(gè)節(jié)點(diǎn)的所有入弧，則可以綜合采用前向和反向星形表示法。當(dāng)然，將孤信息存放兩次是沒有必要的，可以只用一個(gè)數(shù)組（trace）記錄一條弧在兩種表示法中的對(duì)應(yīng)關(guān)系即可。例如，可以在采用前向星形表示法的基礎(chǔ)上，加上上面介紹的數(shù)組和如下的數(shù)組即可。這相當(dāng)于一種緊湊的雙向星形表示法如下所示：兩種表示法中的弧的對(duì)應(yīng)關(guān)系（記為）反向法中弧編號(hào)12345678正向法中弧編號(hào)41257836對(duì)于網(wǎng)絡(luò)圖的表示法，我們作如下說明： 星形表示法和鄰接表表示法在實(shí)際算法實(shí)現(xiàn)中都