11.1 BFS算法的實驗范例

§6.1 概述?

? ? ? ? ?圖

? ? ? ? 圖結(jié)構(gòu)是描述和解決實際應用問題的一種基本而有力的工具。所謂的圖（graph），可定義為G = (V, E)。其中，集合V中的元素稱作頂點（vertex）；集合E中的元素分別對應于V中的某一對頂點(u, v)，表示它們之間存在某種關系，故亦稱作邊（edge） ①。一種直觀顯示圖結(jié)構(gòu)的方法是，用小圓圈或小方塊代表頂點，用聯(lián)接于其間的直線段或曲線弧表示對應的邊。 從計算的需求出發(fā)，我們約定V和E均為有限集，通常將其規(guī)模分別記n = |V|和e = |E|。

? ? ? ?無向圖、有向圖及混合圖

? ? ? ?若邊(u, v)所對應頂點u和v的次序無所謂，則稱作無向邊（undirected edge），例如表示同學關系的邊。反之若u和v不對等，則稱(u, v)為有向邊（directed edge），例如描述企業(yè)與銀行之間的借貸關系，或者程序之間的相互調(diào)用關系的邊。

在某些文獻中，頂點也稱作節(jié)點（node），邊亦稱作弧（arc），本章則統(tǒng)一稱作頂點和邊。

? ? ? ?如此，無向邊(u, v)也可記作(v, u)，而有向的(u, v)和(v, u)則不可混淆。這里約定，有向邊(u, v)從u指向v，其中u稱作該邊的起點（origin）或尾頂點（tail），而v稱作該邊的終點（destination）或頭頂點（head）。

? ? ? ?若E中各邊均無方向，則G稱作無向圖（undirected graph，簡稱undigraph）。例如在描述影視演員相互合作關系的圖G中，若演員u和v若曾經(jīng)共同出演過至少一部影片，則在他（她） 們之間引入一條邊(u, v)。反之，若E中只含有向邊，則G稱作有向圖（directed graph，簡稱 digraph）。例如在C++類的派生關系圖中，從頂點u指向頂點v的有向邊，意味著類u派生自類v。特別地，若E同時包含無向邊和有向邊，則G稱作混合圖（mixed graph）。例如在北京市內(nèi)交通圖中，有些道路是雙行的，另一些是單行的，對應地可分別描述為無向邊和有向邊。

? ? ? ? 相對而言，有向圖的通用性更強，因為無向圖和混合圖都可轉(zhuǎn)化為有向圖————如圖6.1所示， 每條無向邊(u, v)都可等效地替換為對稱的一對有向邊(u, v)和(v, u)。因此，本章將主要針對有向圖，介紹圖結(jié)構(gòu)及其算法的具體實現(xiàn)。

? ? ? ?度

? ? ? ? 對于任何邊e = (u, v)，稱頂點u和v彼此鄰接（adjacent），互為鄰居；而它們都與邊e彼此關聯(lián)（incident）。在無向圖中，與頂點v關聯(lián)的邊數(shù)，稱作v的度數(shù)（degree），記作deg(v)。以圖6.1(a)為例，頂點{ A, B, C, D }的度數(shù)為{ 2, 3, 2, 1 }。

? ? ? ? 對于有向邊e = (u, v)，e稱作u的出邊（outgoing edge）、v的入邊（incoming edge）。v的出邊總數(shù)稱作其出度（out-degree），記作outdeg(v)；入邊總數(shù)稱作其入度（in-degree），記作indeg(v)。在圖6.1(c)中，各頂點的出度為{ 1, 3, 1, 1 }，入度為{ 2, 1, 2, 1 }。

簡單圖

? ? ? ? 聯(lián)接于同一頂點之間的邊，稱作自環(huán)（self-loop）。在某些特定的應用中，這類邊可能的確具有意義————比如在城市交通圖中，沿著某條街道，有可能不需經(jīng)過任何交叉路口即可直接返回原處。不含任何自環(huán)的圖稱作簡單圖（simple graph），也是本書主要討論的對象。

通路與環(huán)路

? ? ? ? ?所謂路徑或通路（path），就是由m + 1個頂點與m條邊交替而成的一個序列：π = { v0, e1, v1, e2, v2, ..., em, vm }

? ? ? ? ?且對任何0 < i <= m都有ei = (vi-1, vi)。也就是說，這些邊依次地首尾相聯(lián)。其中沿途邊的總數(shù)m，亦稱作通路的長度，記作|π| = m。

? ? ? ? ?為簡化描述，也可依次給出通路沿途的各個頂點，而省略聯(lián)接于其間的邊，即表示為：?π = { v0, v1, v2, ..., vm }

? ? ? ? 圖6.2(a)中的{ C, A, B, A, D }，即是從頂點C到D的一條通路，其長度為4。可見，盡管通路上的邊必須互異，但頂點卻可能重復。沿途頂點互異的通路，稱作簡單通路（simple path）。在圖6.2(b)中，{ C, A, D, B }即 是從頂點C到B的一條簡單通路，其長度為3。

? ? ? ? 特別地，對于長度m >= 1的通路π，若起止頂點相同（即v0 = vm），則稱作環(huán)路（cycle），其長度也取作沿途邊的總數(shù)。圖6.3(a)中，{ C, A, B, A, D, B, C }即是一條環(huán)路，其長度為 6。反之，不含任何環(huán)路的有向圖，稱作有向無環(huán)圖（directed acyclic graph, DAG）。

? ? ? ? ? 同樣，盡管環(huán)路上的各邊必須互異，但頂點卻也可能重復。反之若沿途除v0 = vm外所有頂點均互異，則稱作簡單環(huán)路（simple cycle）。例如，圖6.3(b)中的{ C, A, B, C }即是一條簡單環(huán)路，其長度為3。特別地，經(jīng)過圖中各邊一次且恰好一次的環(huán)路，稱作歐拉環(huán)路 （Eulerian tour）————當然，其長度也恰好等于圖中邊的總數(shù)e。

? ? ? ? 圖6.4(a)中的{ C, A, B, A, D, C, D, B, C }即是一條歐拉環(huán)路，其長度為8。對偶地，經(jīng)過圖中各頂點一次且恰好一次的環(huán)路，稱作哈密爾頓環(huán)路（Hamiltonian tour），其長度亦等于構(gòu)成環(huán)路的邊數(shù)。圖6.4(b)中，{ C, A, D, B, C }即是一條長度為4的哈密爾頓環(huán)路。

帶權(quán)網(wǎng)絡

? ? ? ? 圖不僅需要表示頂點之間是否存在某種關系，有時還需要表示這一關系的具體細節(jié)。以鐵路運輸為例，可以用頂點表示城市，用頂點之間的聯(lián)邊，表示對應的城市之間是否有客運鐵路聯(lián)接；同時，往往還需要記錄各段鐵路的長度、承運能力，以及運輸成本等信息。

? ? ? ?為適應這類應用要求，需通過一個權(quán)值函數(shù)，為每一邊e指定一個權(quán)重（weight），比如wt(e) 即為邊e的權(quán)重。各邊均帶有權(quán)重的圖，稱作帶權(quán)圖（weighted graph）或帶權(quán)網(wǎng)絡（weighted network），有時也簡稱網(wǎng)絡（network），記作G(V, E, wt())。

復雜度

? ? ? ? 與其它算法一樣，圖算法也需要就時間性能和空間性能，進行分析和比較。相應地，問題的輸入規(guī)模，也應該以頂點數(shù)與邊數(shù)的總和（n + e）來度量。不難看出，無論頂點多少，邊數(shù)都有可能為0。那么反過來，在包含n個頂點的圖中，至多可能包含多少條邊呢？

? ? ? ? 對于無向圖，每一對頂點至多貢獻一條邊，故總共不超過n(n - 1)/2條邊，且這個上界由完全圖達到。對于有向圖，每一對頂點都可能貢獻（互逆的）兩條邊，因此至多可有n(n - 1) 條邊。總而言之，必有e = O(n^2 )。

§6.2 抽象數(shù)據(jù)類型

6.2.1 操作接口

? ? ? ?作為抽象數(shù)據(jù)類型，圖支持的操作接口分為邊和頂點兩類，分列于表6.1和表6.2。

6.2.2 Graph模板類

? ? ? ? ?代碼6.1以抽象模板類的形式，給出了圖ADT的具體定義。

? ? ? ? 仍為簡化起見，這里直接開放了變量n和e。除以上所列的操作接口，這里還明確定義了頂點和邊可能處于的若干狀態(tài)，并通過內(nèi)部接口reset()復位頂點和邊的狀態(tài)。

? ? ? ? 圖的部分基本算法在此也以操作接口的形式供外部用戶直接使用，比如廣度優(yōu)先搜索、深度優(yōu)先搜索、雙連通分量分解、最小支撐樹、最短路徑等。為求解更多的具體應用問題，讀者可照此模式，獨立地補充相應的算法。

? ? ? ? 就功能而言，這些算法均超脫于圖結(jié)構(gòu)的具體實現(xiàn)方式，借助統(tǒng)一的頂點和邊ADT操作接口直接編寫。盡管如此，正如以下即將看到的，圖算法的時間、空間性能，卻與圖結(jié)構(gòu)的具體實現(xiàn)方式緊密相關，在這方面的理解深度，也將反映和決定我們對圖結(jié)構(gòu)的駕馭與運用能力。

§6.3 鄰接矩陣

6.3.1 原理

? ? ? ? 鄰接矩陣（adjacency matrix）是圖ADT最基本的實現(xiàn)方式，使用方陣A[n][n]表示由n個頂點構(gòu)成的圖，其中每個單元，各自負責描述一對頂點之間可能存在的鄰接關系，故此得名。

? ? ? ? 對于無權(quán)圖，存在 （不存在）從頂點u到v的邊，當且僅當A[u][v] = 1（0）。圖6.5(a)和(b)即為無向圖和有向圖的鄰接矩陣實例。這一表示方式，不難推廣至帶權(quán)網(wǎng)絡。此時如圖(c)所示，矩陣各單元可從布爾型改為整型或浮點型，記錄所對應邊的權(quán)重。對于不存在的邊，通常統(tǒng)一取值為∞或0。

轉(zhuǎn)載于:https://www.cnblogs.com/ZHONGZHENHUA/p/10500871.html

總結(jié)

以上是生活随笔為你收集整理的第四篇 群聚类非线性表的编程实验 第11章 应用图的遍历算法编程的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。