版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第五章 圖,圖(Graph)是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中,對(duì)結(jié)點(diǎn)(圖中常稱為頂點(diǎn))的前趨和后繼個(gè)數(shù)不加限制,即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)雜的數(shù)據(jù)對(duì)象。 圖的應(yīng)用極為廣泛,特別是近年來的迅速發(fā)展,已經(jīng)滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。,圖狀結(jié)構(gòu)的實(shí)際背景 在城市之間建立通訊網(wǎng)絡(luò),使得其中的任意兩個(gè)城市之間有直接或間接的通訊線路,假設(shè)已知每對(duì)城市之間通訊線路的造價(jià),要求找出一個(gè)造價(jià)最低的通訊網(wǎng)絡(luò)。,城市航線網(wǎng),計(jì)算機(jī)網(wǎng)絡(luò),第五章 圖 5.1 基本概念 5.2 圖的存儲(chǔ)結(jié)構(gòu) 5.3
2、 圖的遍歷 5.4 拓?fù)渑判?5.5 關(guān)鍵路徑 5.6 最短路徑 5.7 最小支撐樹,定義5.1:圖G由兩個(gè)集合V和E組成,記為G=(V, E);其中 V 是頂點(diǎn)的有限集合,E 是連接 V 中兩個(gè)不同頂點(diǎn)的邊的有限集合。通常,也將圖G的頂點(diǎn)集和邊集分別記為V(G)和E(G)。 如果E中的頂點(diǎn)對(duì)是有序的,即E中的每條邊都是有方向的,則稱G為有向圖。如果頂點(diǎn)對(duì)是無序?qū)?,則稱G是無向圖。,5.1 圖的基本概念,定義5.2 若G = (V, E)是有向圖,則它的一條有向邊是由V中兩個(gè)頂點(diǎn)構(gòu)成的有序?qū)?,亦稱為弧,記為,其中w是邊的始點(diǎn),又稱弧尾;v是邊的終點(diǎn),又稱弧頭。,有向圖 G=(V,E) V= v
3、1,v2,v3,v4 E=,無向圖,G=(V,E) V=V1, V2, V3, V4 ,V5 E=(V1, V4 ), (V1, V2), (V2, V3 ), (V2, V5 ), (V3, V4 ), (V3, V5 ) ,定義5.3 在無向圖中,若兩個(gè)頂點(diǎn)w和v之間存在一條邊(w, v),則稱w, v是相鄰的,二者互為鄰接頂點(diǎn)。 在有向圖中,若存在一條邊,則稱頂點(diǎn)w鄰接到頂點(diǎn)v,頂點(diǎn)v鄰接自頂點(diǎn)w.,定義5.4 由于E是邊的集合,故一個(gè)圖中不會(huì)多次出現(xiàn)一條邊。若去掉此限制,則由此產(chǎn)生的結(jié)構(gòu)稱為多重圖。圖 (c)就是一個(gè)多重圖。,(a) (b) (c),定義5.5 設(shè)G是無向圖,vV(G)
4、,E(G)中以v為端點(diǎn)的邊的個(gè)數(shù),稱為頂點(diǎn)的度。若G是有向圖,則v的出度是以v為始點(diǎn)的邊的個(gè)數(shù),v的入度是以v為終點(diǎn)的邊的個(gè)數(shù)。 有向圖中,以某頂點(diǎn)為弧頭的弧的數(shù)目稱為該頂點(diǎn)的入度。以某頂點(diǎn)為弧尾的弧的數(shù)目稱為該頂點(diǎn)的出度。 頂點(diǎn)的度=入度+出度。,設(shè)圖G(可以為有向或無向圖)共有n個(gè)頂點(diǎn), e條邊,若頂點(diǎn)vi的度數(shù)為D(vi),則,因?yàn)橐粭l邊關(guān)聯(lián)兩個(gè)頂點(diǎn),而且使得這兩個(gè)頂點(diǎn)的度數(shù)分別增加1。因此頂點(diǎn)的度數(shù)之和就是邊的兩倍。,定義5.6 設(shè)G是圖,若存在一個(gè)頂點(diǎn)序列 使得 或 屬于E(G),則稱vp到vq存在一條路徑,其中vp 稱為起點(diǎn),vq稱為終點(diǎn)。 路徑的長度是該路徑上邊的個(gè)數(shù)。如果一條路
5、徑上除了起點(diǎn)和終點(diǎn)可以相同外,再不能有相同的頂點(diǎn),則稱此路徑為簡單路徑。如果一條簡單路徑的起點(diǎn)和終點(diǎn)相同,且路徑長度大于等于2,則稱之為簡單回路。,圖(a)中,v1到v3之間存在一條路徑v1, v2, v5, v4, v3,同時(shí)這也是一條簡單路徑;v1, v2, v5, v4, v3, v1是一條簡單回路。,(a) (b) (c),路徑:v1 v3 v4 v3 v5 簡單路徑:v1 v3 v5 簡單回路:v1 v2 v3 v1,路徑:v1 v3 v2 v4 v3 v2 簡單路徑:v1 v3 v2 簡單回路:v1 v3 v2 v1,定義5.7 設(shè)G,H是圖,如果V(H) V(G),E(H) E(
6、G),則稱H是G的子圖,G是H的母圖。如果H是G的子圖,并且V(H) = V(G),則稱H為G的支撐子圖。,完全圖 :有向完全圖(邊數(shù)n*(n-1) 無向完全圖(邊數(shù)1/2*n*(n-1),定義5.8 設(shè)G是圖,若存在一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑,則稱vi與vj可及(連通)。若G為無向圖,且V(G)中任意兩頂點(diǎn)都可及,則稱G為連通圖。若G為有向圖,且對(duì)于V(G)中任意兩個(gè)不同的頂點(diǎn)vi和vj , vi與vj可及, vj與vi也可及,則稱G為強(qiáng)連通圖。 也可以定義“弱連通圖”的概念,即在任何頂點(diǎn)u和v之間,至少存在一條從u到v的路徑或者存在一條從v到u的路徑。,定義5.10 對(duì)于G的一個(gè)連通子
7、圖GK,如果不存在G的另一個(gè)連通子圖G,使得V(GK)V(G),則稱GK為G的連通分量。 無向圖G的極大連通子圖稱為G的連通分量。,(a) (b) (c),(d) (e),一個(gè)圖的連通子圖,e是a的連通分量,連通分量,連通分量,有時(shí)候,圖不僅要表示出元素之間是否存在某種關(guān)系,同時(shí)還需要表示與這一關(guān)系相關(guān)的某些信息。 例如在計(jì)算機(jī)網(wǎng)絡(luò)對(duì)應(yīng)的圖中,頂點(diǎn)表示計(jì)算機(jī),頂點(diǎn)之間的邊表示計(jì)算機(jī)之間的通訊鏈路。實(shí)際中,為了管理計(jì)算機(jī)網(wǎng)絡(luò),我們需要這個(gè)圖包含更多的信息,例如每條通訊鏈路的物理長度、成本和帶寬等信息。為此,我們?yōu)閭鹘y(tǒng)圖中的每條邊添加相應(yīng)的數(shù)據(jù)域以記錄所需要的信息。,定義5.11 設(shè)G = (V,
8、 E)是圖,若對(duì)圖中的任意一條邊l,都有實(shí)數(shù)w(l)與其對(duì)應(yīng),則稱G為權(quán)圖,記為G = (V, E, w)。記w(u,v)表示w(u,v)或w(),規(guī)定: uV, 有w(u,u)=0或w()=0 u,vV, 若(u,v)E(G)或E(G) 則w(u,v)=或w()=,定義5.12 若 是權(quán)圖G中的一條路徑,則 稱為加權(quán)路徑 的長度或權(quán)重。 權(quán)通常用來表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或費(fèi)用。,無向圖 有向圖 邊 端點(diǎn) 弧 弧頭 弧尾 相鄰的 鄰接到 鄰接自 度 出度 入度 連通圖 強(qiáng)連通圖,第五章 圖 5.1 基本概念 5.2 圖的存儲(chǔ)結(jié)構(gòu) 5.3 圖的遍歷 5.4 拓?fù)渑判?5.5 關(guān)鍵路徑
9、5.6 最短路徑 5.7 最小支撐樹,鄰接矩陣 鄰接表(逆鄰接表),1、 圖的存儲(chǔ)結(jié)構(gòu),用順序方式或鏈接方式存儲(chǔ)圖的頂點(diǎn)表v0,v1,vn-1 ,圖的邊用nn階矩陣A =(aij)表示,A的定義如下: (a)若圖為權(quán)圖,aij對(duì)應(yīng)邊的權(quán)值; (b)若圖為非權(quán)圖,則 (1) aii=0; (2) aij=1,當(dāng)ij且或(vi,vj)存在時(shí); (3)aij=0,當(dāng)ij且或(vi,vj)不存在時(shí)。 稱矩陣A為圖的鄰接矩陣。,1、鄰接矩陣,例1無向圖的鄰接矩陣 無向圖的鄰接矩陣是對(duì)稱陣。,例2有向圖的鄰接矩陣,例3權(quán)圖的鄰接矩陣,借助鄰接矩陣,可以很容易地求出圖中頂點(diǎn)的度。 無向圖 鄰接矩陣的第i行(
10、或第i列)的非零元素的個(gè)數(shù)是頂點(diǎn)Vi的度。 有向圖 鄰接矩陣第i行的非零元素的個(gè)數(shù)為頂點(diǎn)Vi的出度;第i列的非零元素的個(gè)數(shù)為頂點(diǎn)Vi的入度。,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0,2、鄰接表 鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表(n個(gè)頂點(diǎn)建立n個(gè)單鏈表),第i個(gè)單鏈表中的結(jié)點(diǎn)包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。由順序存儲(chǔ)的頂點(diǎn)表和鏈接存儲(chǔ)的邊鏈表構(gòu)成的圖的存儲(chǔ)結(jié)構(gòu)被稱為鄰接表。,例1無向圖的鄰接表 頂點(diǎn)的結(jié)構(gòu) 非權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu) 對(duì)于用鄰接表存儲(chǔ)的無向圖,
11、每條邊對(duì)應(yīng)兩個(gè)邊結(jié)點(diǎn); 根據(jù)鄰接表,可以統(tǒng)計(jì)出無向圖中每個(gè)頂點(diǎn)的度。,例2有向圖的鄰接表 對(duì)于用鄰接表存儲(chǔ)的有向圖,每條邊只對(duì)應(yīng)一個(gè)邊結(jié)點(diǎn); 根據(jù)鄰接表,可以統(tǒng)計(jì)出有向圖中每個(gè)頂點(diǎn)的出度。但是,如果要統(tǒng)計(jì)頂點(diǎn)的入度,每統(tǒng)計(jì)一個(gè)頂點(diǎn),就要遍歷所有的邊結(jié)點(diǎn),其時(shí)間復(fù)雜度為O(e)(e為圖中邊的個(gè)數(shù)),從而統(tǒng)計(jì)所有頂點(diǎn)入度的時(shí)間復(fù)雜度為O(ne)(n為圖的頂點(diǎn)個(gè)數(shù))。,例3有向圖的逆鄰接表 建立逆鄰接表(頂點(diǎn)的指向關(guān)系與鄰接表恰好相反),根據(jù)逆鄰接表,很容易統(tǒng)計(jì)出圖中每個(gè)頂點(diǎn)的入度。,例4 權(quán)圖的鄰接表,權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu),采用鄰接矩陣還是用鄰接表來存儲(chǔ)圖,要視對(duì)給定圖實(shí)施的具體操作而定。 對(duì)于邊很多
12、的圖(也稱稠密圖),適于用鄰接矩陣存儲(chǔ),因?yàn)檎加玫目臻g少。 而對(duì)于頂點(diǎn)多而邊少的圖(也稱稀疏圖),若用鄰接矩陣存儲(chǔ),對(duì)應(yīng)的鄰接矩陣將是一個(gè)稀疏矩陣,存儲(chǔ)利用率很低。因此,頂點(diǎn)多而邊少的圖適于用鄰接表存儲(chǔ)。,鄰接矩陣存儲(chǔ)的圖類Graph_Matrix 鄰接表存儲(chǔ)的圖類Graph_List,2、 圖的實(shí)現(xiàn),1. 用鄰接矩陣存儲(chǔ)的圖類 Graph_Matrix類聲明 const int MaxGraphSize = 256 ; / 圖的最大頂點(diǎn)個(gè)數(shù) const int MaxWeight = 1000 ; /邊的最大權(quán)值 template class Graph_Matrix private: SL
13、List VertexList ; /頂點(diǎn)表 int edge MaxGraphSize MaxGraphSize ; /鄰接矩陣 int graphsize ; /當(dāng)前頂點(diǎn)數(shù),public: /I. 構(gòu)造函數(shù)與析構(gòu)函數(shù) Graph_Matrix( ) ; Graph_Matrix( ) ; /II. 圖的維護(hù)函數(shù) int GraphEmpty(void) const /檢測圖是否為空 int GraphFull(void) const ; /檢測圖是否已滿,即頂點(diǎn)個(gè)數(shù)是否越界 int NumberOfVertices( void ) const ;/返回圖的頂點(diǎn)個(gè)數(shù) int NumberOf
14、Edges( void ) const ; /返回圖的邊個(gè)數(shù) int GetWeight( const int v1, const int v2 ) ; / 返回指定邊的權(quán)值 int* /返回序號(hào)為v1的頂點(diǎn)相對(duì)于序號(hào)為v2的頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)的序號(hào),void InsertVertex( const int ,/ 構(gòu)造函數(shù), 創(chuàng)建一個(gè)圖 Graph_Matrix : Graph_Matrix () cin graphsize; for( int i = 0 ; i edgeij; ,/ 取得序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號(hào) int Graph_Matrix :GetFirstNeighb
15、or( const int v ) if (v = = -1) return -1; for( int i = 0 ; i 0 / 若v沒有鄰接頂點(diǎn),則返回-1 ,/取得頂點(diǎn)v1相對(duì)于v2的下一個(gè)鄰接頂點(diǎn)的序號(hào) int Graph_Matrix :GetNextNeighbor( const int v1 , const int v2 ) if (v1 = = -1 | v2= = -1) return -1; for( int i = v2 + 1 ; i 0 /若在v2之后沒有與v1鄰接的頂點(diǎn),則返回-1 ,刪除頂點(diǎn)Vertex 算法思想:不僅要從頂點(diǎn)表中刪除該頂點(diǎn),還需要?jiǎng)h除該頂點(diǎn)所發(fā)出
16、的邊以及所有的入邊,即在鄰接矩陣中刪除相應(yīng)的行和列。,2. 用鄰接表存儲(chǔ)的圖類Graph_List,2. 用鄰接表存儲(chǔ)的圖類Graph_List / 邊結(jié)點(diǎn)的結(jié)構(gòu)體 struct Edge friend class Graph_List ; int VerAdj ; / 鄰接頂點(diǎn)序號(hào),從0開始編號(hào) int cost ; / 邊的權(quán)值 Edge *link ; / 指向下一個(gè)邊結(jié)點(diǎn)的指針 ;,權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu),/ 頂點(diǎn)表中結(jié)點(diǎn)的結(jié)構(gòu)體 struct Vertex friend class Graph_List; int VerName;/ 頂點(diǎn)的名稱 Edge *adjacent;/ 邊鏈表的頭
17、指針 ,頂點(diǎn)的結(jié)構(gòu),/采用鄰接表存儲(chǔ)的Graph_List類定義 class Graph_List private: Vertex *Head; / 頂點(diǎn)表頭指針 int graphsize; / 圖中當(dāng)前頂點(diǎn)的個(gè)數(shù) public: / I. 圖的構(gòu)造函數(shù)和析構(gòu)函數(shù) Graph_List ( ); Graph_List ( ); / II. 圖的維護(hù)函數(shù) 與Graph_Matrix類中的維護(hù)函數(shù)相同。 / III. 圖的基本算法 與Graph_Matrix類中的基本算法相同。 ;,/ 求序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號(hào) int Graph_List: GetFirstNeighbor( c
18、onst int v ) if ( v = = -1 ) return -1; Edge *p = Headv.adjacent ; if (p != NULL) return pVerAdj ; else return -1; ,Head,/ 求序號(hào)為v1的頂點(diǎn)相對(duì)于序號(hào)為v2的頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)的序號(hào) int Graph_List : GetNextNeighbor( const int v1 , const int v2 ) if ( v1 != -1 ,第五章 圖 5.1 基本概念 5.2 圖的存儲(chǔ)結(jié)構(gòu) 5.3 圖的遍歷 5.4 拓?fù)渑判?5.5 關(guān)鍵路徑 5.6 最短路徑 5.7
19、最小支撐樹,從已給的連通圖中某一頂點(diǎn)出發(fā),沿著一些邊訪遍圖中所有頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪問一次,就叫做圖的遍歷 ( Graph Traversal )。 圖中可能存在回路,且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通,在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。 為了避免重復(fù)訪問,可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組 visited ,它的初始狀態(tài)為 0,在圖的遍歷過程中,一旦某一個(gè)頂點(diǎn) i 被訪問,就立即讓 visitedi 為 1,防止它被多次訪問。,5.3.1 深度優(yōu)先遍歷 深度優(yōu)先遍歷又被稱為深度優(yōu)先搜索 DFS ( Depth First Search ) 基本思想: D
20、FS 在訪問圖中某一起始頂點(diǎn) v 后,由 v 出發(fā),訪問它的任一鄰接頂點(diǎn) w1;再從 w1 出發(fā),訪問與 w1鄰接但還沒有訪問過的頂點(diǎn) w2;然后再從 w2 出發(fā),進(jìn)行類似的訪問, 如此進(jìn)行下去,直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。接著,退回一步,退到前一次剛訪問過的頂點(diǎn),看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有,則訪問此頂點(diǎn),之后再從此頂點(diǎn)出發(fā),進(jìn)行與前述類似的訪問;如果沒有,就再退回一步進(jìn)行搜索。重復(fù)上述過程,直到連通圖中所有頂點(diǎn)都被訪問過為止。,深度優(yōu)先搜索DFS ( Depth First Search ),深度優(yōu)先搜索的示例,1. 遞歸算法/P140 算法DepthF
21、irstSearch (v, visited) /* 圖的深度優(yōu)先遍歷的遞歸算法*/ DFSearch1初始化 PRINT(v). visitedv 1. p adjacent(Headv) . DFSearch2深度優(yōu)先遍歷圖 WHILE pDO ( IF visitedVerAdj(p)1 THEN DepthFirstSearch (VerAdj(p), visited) . p link(p) . ),算法 DFS_Main( ) visited = new intgraphsize ;/ 為輔助數(shù)組申請(qǐng)空間 for( int k = 0 ; k graphsize ; k + + )
22、visitedk = 0 ; / 數(shù)組初始化 / 從序號(hào)為0的頂點(diǎn)出發(fā),深度優(yōu)先遍歷圖 DepthFirstSearch( 0 , visited ) ; delete visited ; / 釋放輔助數(shù)組空間 ,DFSearch1初始化 PRINT(v). visitedv 1. p adjacent(Headv) . DFSearch2深度優(yōu)先遍歷圖 WHILE p DO ( IF visitedVerAdj(p)1 THEN DepthFirstSearch (VerAdj(p), visited) . p link(p) . ),可以利用堆棧實(shí)現(xiàn)深度優(yōu)先遍歷的非遞歸算法。 堆棧中存放已
23、訪問結(jié)點(diǎn)的未被訪問的鄰接頂點(diǎn),每次彈出棧頂元素時(shí),如其未被訪問,則訪問該頂點(diǎn),并檢查當(dāng)前頂點(diǎn)的邊鏈表,將其未被訪問的鄰接頂點(diǎn)入棧,循環(huán)進(jìn)行。,2. 迭代算法,首先將所有頂點(diǎn)的visited值置為0, 初始頂點(diǎn)壓入堆棧; 檢測堆棧是否為空。若堆棧為空,則迭代結(jié) 束;否則,從棧頂彈出一個(gè)頂點(diǎn)v; 如果v未被訪問過,則訪問v,將visitedv值更新為1,然后根據(jù)v的鄰接頂點(diǎn)表,將v的未被訪問的鄰接頂點(diǎn)壓入棧,執(zhí)行步驟 。,算法DFS (Head, v , visited. visited) /* 圖的深度優(yōu)先遍歷的非遞歸算法*/ DFS1初始化 CREATS(S) . /*創(chuàng)建堆棧 S */ FO
24、R i = 1 TO n DO visitedi 0. S v. /* 將v壓入棧中 */ DFS2利用堆棧S深度優(yōu)先遍歷圖 WHILE NOT(ISEMTS(S) DO /* 當(dāng)S不空時(shí) */ ( v S. /*彈出堆棧頂元素 */ IF visitedv = 0 THEN ( PRINT(v) . visitedv 1. p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN S VerAdj(p) . p link(p). ) ) ),DFS2利用堆棧S深度優(yōu)先遍歷圖 WHILE NOT(ISEMTS(S) DO /*
25、當(dāng)S不空時(shí) */ ( v S. IF visitedv = 0 THEN ( PRINT(v) . visitedv 1. p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN S VerAdj(p) . p link(p). ) ) ),算法分析,圖中有 n 個(gè)頂點(diǎn),e 條邊。 如果用鄰接表表示圖,沿頂點(diǎn)的adjacent可以找到某個(gè)頂點(diǎn)v 的所有鄰接頂點(diǎn)w。由于總共有2e 個(gè)邊結(jié)點(diǎn),所以掃描邊的時(shí)間為O(e)。而且對(duì)所有頂點(diǎn)遞歸訪問1次,所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。 如果用鄰接矩陣表示圖,則查找每一個(gè)頂點(diǎn)的所有
26、的邊,所需時(shí)間為O(n),則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n2)。,非連通圖需要多次調(diào)用深度優(yōu)先遍歷算法 For i=0 to n-1 DO visitedi 0. For j=0 to n-1 DO IF visitedj=0 THEN DepthFirstSearch (vj, visited),5.3.2 廣度優(yōu)先遍歷 基本思想: 首先訪問初始點(diǎn)頂點(diǎn)v0,之后依次訪問與v0鄰接的全部頂點(diǎn)w1,w2,.,wk。然后,再順次訪問與w1,w2,.,wk鄰接的尚未訪問的全部頂點(diǎn),再從這些被訪問過的頂點(diǎn)出發(fā),逐個(gè)訪問與它們鄰接的尚未訪問過的全部頂點(diǎn)。依此類推,直到連通圖中的所有頂點(diǎn)全部訪問完為
27、止。,廣度優(yōu)先搜索BFS ( Breadth First Search ),廣度優(yōu)先搜索的示例,廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹,廣度優(yōu)先搜索類似于樹的層次遍歷,是一種分層的搜索過程,每向前走一步可能訪問一批頂點(diǎn),不像深度優(yōu)先搜索那樣有回退的情況。因此,廣度優(yōu)先搜索不是一個(gè)遞歸的過程,其算法也不是遞歸的。 為了實(shí)現(xiàn)逐層訪問,算法中使用一個(gè)隊(duì)列,以便于向下一層訪問。 與深度優(yōu)先搜索過程一樣,為避免重復(fù)訪問,需要一個(gè)輔助數(shù)組visited 。,算法BFS (Head, v, visited. visited) /*廣度優(yōu)先遍歷算法 */ BFS1初始化 (P142改錯(cuò)) CREATQ(Q). /*
28、創(chuàng)建隊(duì)列 Q */ FOR i = 1 TO n DO visitedi 0. PRINT(v) . visitedv 1. Qv. /* 入隊(duì) */ BFS2廣度優(yōu)先遍歷 WHILE NOT(ISEMTQ(Q) DO /* 當(dāng)隊(duì)列不空時(shí) */ ( v Q. /* 出隊(duì) */ p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN ( Q VerAdj(p) . PRINT(VerAdj(p) ) . visitedVerAdj(p) 1. ) . p link(p). ) ) ,WHILE NOT(ISEMTQ(Q) DO
29、/* 當(dāng)隊(duì)列不空時(shí) */ ( v Q. /* 出隊(duì) */ p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN ( Q VerAdj(p) . PRINT(VerAdj(p) ) . visitedVerAdj(p) 1. ) p link(p). ) ),算法分析,如果使用鄰接表表示圖,則循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + + dn-1 = O(e),其中的 di 是頂點(diǎn) i 的度??偟臅r(shí)間復(fù)雜度為O(n+e)。 如果使用鄰接矩陣,則對(duì)于每一個(gè)被訪問的頂點(diǎn),循環(huán)要檢測矩陣中的 n 個(gè)元素,總的時(shí)間代價(jià)為O(n2)。,第
30、五章 圖 5.1 基本概念 5.2 圖的存儲(chǔ)結(jié)構(gòu) 5.3 圖的遍歷 5.4 拓?fù)渑判?5.5 關(guān)鍵路徑 5.6 最短路徑 5.7 最小支撐樹,5.4 拓?fù)渑判?計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外,一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng),這個(gè)工程就可以完成了。 AOV網(wǎng):在有向圖中,用頂點(diǎn)表示活動(dòng),用有向邊表示活動(dòng)之間的先后關(guān)系,稱這樣的有向圖為AOV網(wǎng)(Activity On Vertex Network)。,例如,計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程,每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程,有些則不要求。這樣在有的課程
31、之間有領(lǐng)先關(guān)系,有的課程可以并行地學(xué)習(xí)。,例按拓?fù)浯涡虬才庞?jì)算機(jī)專業(yè)必修課程,在AOV網(wǎng)絡(luò)中,如果活動(dòng)Vi 必須在活動(dòng)Vj 之前進(jìn)行,則存在有向邊, AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路,即有向環(huán)。在AOV網(wǎng)絡(luò)中如果出現(xiàn)了有向環(huán),則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。 因此,對(duì)給定的AOV網(wǎng)絡(luò),必須先判斷它是否存在有向環(huán)。,拓?fù)湫蛄校喊袮OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列,使每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前邊。 拓?fù)渑判颍簶?gòu)造AOV網(wǎng)的拓?fù)湫蛄械倪^程被稱為拓?fù)渑判颉?拓?fù)湫蛄校篊0 , C1 , C2 , C4 , C3 , C5 , C7 , C8 , C6, 拓?fù)渑判蚧静襟E: 從網(wǎng)中選擇一
32、個(gè)入度為0的頂點(diǎn)且輸出之。 從網(wǎng)中刪除該頂點(diǎn)及其所有出邊。 執(zhí)行 ,直至所有頂點(diǎn)已輸出,或網(wǎng)中剩余頂點(diǎn)入度均不為0 (說明網(wǎng)中存在回路,無法繼續(xù)拓?fù)渑判?,回路與拓?fù)渑判?任何無回路的AOV網(wǎng),其頂點(diǎn)均可排成拓?fù)湫蛄?其拓?fù)湫蛄胁灰欢ㄎㄒ?; 如果能將AOV網(wǎng)的所有頂點(diǎn)都排入一個(gè)拓?fù)湫蛄?,則該AOV網(wǎng)中必定無有向環(huán);若在有回路的AOV網(wǎng)中,找不到所有頂點(diǎn)的拓?fù)湫蛄?AOV網(wǎng)所代表的工程是不可行的)。 。 因此,可以用拓?fù)渑判蚺袛嘤邢驁D中是否有回路,假定AOV網(wǎng)用鄰接表的形式存儲(chǔ)。為實(shí)現(xiàn)拓?fù)渑判蛩惴?,事先需好兩?xiàng)準(zhǔn)備工作: 建立一個(gè)數(shù)組count ,counti的元素值取對(duì)應(yīng)頂點(diǎn)i的入度; 建立
33、一個(gè)堆棧,棧中存放入度為0的頂點(diǎn),每當(dāng)一個(gè)頂點(diǎn)的入度為0,就將其壓入棧。,拓?fù)渑判蛩惴?用一個(gè)堆棧存放入度為 0 的頂點(diǎn)。 虛擬的堆棧利用變量top和count數(shù)組元素的值來模擬堆棧的壓入和彈出。 top:“棧頂”位置,初始為-1 counttop:次棧頂元素 入棧:counti = top; top = i; 出棧:j = top; top = counttop;,算法TopoOrder(n) /* 圖的拓?fù)渑判蛩惴?*/ TOrder1初始化 /* 計(jì)算count數(shù)組 */ FOR i = 0 TO n-1 DO counti 0. FOR i = 0 TO n-1 DO ( p adja
34、cent( Headi ) . WHILE p DO (countVerAdj(p) countVerAdj(p)+1. p link (p). ) )/統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度,拓?fù)渑判蛩惴ǎ?算法TOrder1初始化第二部分 top -1./棧頂指針top FOR i = 0 TO n-1 DO/將入度為0的頂點(diǎn)入棧 IF counti = 0 THEN ( counti top. top i. ),拓?fù)渑判蛩惴ǎ?/算法TOrder1初始化第二部分 top -1./棧頂指針top FOR i = 0 TO n-1 DO/將入度為0的頂點(diǎn)入棧 IF counti = 0 THEN ( count
35、i top. top i. ),TOrder2拓?fù)渑判?FOR i = 1 TO n DO IF top = - 1 THEN / 若循環(huán)體尚未被執(zhí)行n次,棧頂指針已為-1 (PRINT “有回路! ”. RETURN. ) /說明有回路,終止程序 ELSE ( j top. top counttop . /* 彈出棧頂j */ PRINT ( j ) . p adjacent( Headj ) . / 掃描j的邊鏈表 WHILE p DO ( k VerAdj(p) . countk countk-1. / 頂點(diǎn)k的入度減1 IF countk = 0 THEN /若入度為0,則k入棧 (c
36、ountk top. top k.) p link (p). ) ) ,FOR i = 1 TO n DO (j top. top counttop . /* 彈出堆棧頂點(diǎn)j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1,若入度為0,則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n DO (j top. top count
37、top . /* 彈出堆棧頂點(diǎn)j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO /* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1,若入度為0, 則k 入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n DO (j top. top counttop . /* 彈出堆棧頂點(diǎn)j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/*
38、 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1,若入度為0,則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n DO (j top. top counttop . /* 彈出堆棧頂點(diǎn)j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1,若入度為0,則k入棧 */ countk countk-1. IF
39、countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n DO (j top. top counttop . /* 彈出堆棧頂點(diǎn)j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1,若入度為0,則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n D
40、O (j top. top counttop . /* 彈出堆棧頂點(diǎn)j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1,若入度為0,則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),引理5.1 設(shè)圖G = (V, E)是非循環(huán)圖, V(G), 則G中一定存在入度為零的頂點(diǎn) 定理5.2 設(shè)G=(V, E)是非循環(huán)圖,V(G)=1, 2 , n, e=|E(
41、G)|. 則算法TopoOrder是正確的且算法的時(shí)間復(fù)雜性為 O(n+e).,第五章 圖 5.1 基本概念 5.2 圖的存儲(chǔ)結(jié)構(gòu) 5.3 圖的遍歷 5.4 拓?fù)渑判?5.5 關(guān)鍵路徑 5.6 最短路徑 5.7 最小支撐樹,5.5 關(guān)鍵路徑 5.5.1 基本概念 邊表示活動(dòng)(Activity) 邊的權(quán)值表示活動(dòng)的持續(xù)時(shí)間(Duration) 頂點(diǎn)表示入邊的活動(dòng)已完成,出邊的活動(dòng)可以開始的狀態(tài),也稱為事件(Event) 這樣的有向無環(huán)的帶權(quán)圖叫做AOE (Activity On Edges Network)網(wǎng)。,例 某工程 源點(diǎn):表示整個(gè)工程的開始(入度為零)。 匯點(diǎn):表示整個(gè)工程的結(jié)束(出度為
42、零)。 完成整個(gè)工程至少需要多少時(shí)間? 為縮短工程的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?,從源點(diǎn)到各頂點(diǎn)的路徑可能不止一條,路徑長度也可能不同。只有各條路徑上所有活動(dòng)都完成了,整個(gè)工程才算完成。 關(guān)鍵路徑:從源點(diǎn)到匯點(diǎn)具有最大長度的路徑稱為關(guān)鍵路徑。 路徑長度:指路徑上的各邊權(quán)值之和。 關(guān)鍵活動(dòng):關(guān)鍵路徑上的活動(dòng)。, 關(guān)鍵活動(dòng)有關(guān)的量: 事件vi的最早發(fā)生時(shí)間ve(i): 從源點(diǎn)v0到vi的最長路徑長度。 事件vi的最遲發(fā)生時(shí)間vl(i): 保證匯點(diǎn)的最早發(fā)生時(shí)間不推遲的前提下,事件vi允許的最遲開始時(shí)間,等于ve(n-1)減去從vi到vn-1最長路徑長度。, 關(guān)鍵活動(dòng)有關(guān)的量: 活動(dòng)ak的最早開始時(shí)間e
43、(k): 設(shè)活動(dòng)ak在有向邊上, e(k)是從源 點(diǎn)v0到vi的最長路徑長度。因此e(k)=ve(i)。, 關(guān)鍵活動(dòng)有關(guān)的量: 活動(dòng)ak的最遲開始時(shí)間l(k): l(k)是在不會(huì)引起時(shí)間延誤的前提下,該活動(dòng)允許的最遲開始時(shí)間。 設(shè)活動(dòng)ak在有向邊上,則 l(k)= vl(j)-dur()。, 關(guān)鍵活動(dòng): l(k) e(k),5.5.2 關(guān)鍵活動(dòng)算法 求關(guān)鍵活動(dòng)的基本步驟: 對(duì)AOE網(wǎng)進(jìn)行拓?fù)渑判?,按拓?fù)浯涡蚯蟪龈黜旤c(diǎn)事件的最早發(fā)生時(shí)間ve,若網(wǎng)中有回路,則終止算法; 按拓?fù)湫蛄械哪嫘蚯蟪龈黜旤c(diǎn)事件的最遲發(fā)生時(shí)間vl 根據(jù)ve和vl的值,求出各活動(dòng)的最早開始時(shí)間e(k)與最遲開始時(shí)間l(k),若
44、e(k)= l(k),則是關(guān)鍵活動(dòng)。,例 求關(guān)鍵活動(dòng)第1步,按拓?fù)湔蜻f推: 注:此時(shí)j為前驅(qū)結(jié)點(diǎn),i為后繼結(jié)點(diǎn),ve(0)=0 ve(1)= ve(0)+weight()=0+6=6 ve(2)= ve(0)+weight()=0+4=4 ve(3)= ve(0)+weight()=0+5=5 ve(4)= maxve(1)+ weight(), ve(2)+ weight() =max6+1,4+1=7,ve(5)= ve(3)+weight()=5+2=7 ve(6)= ve(4)+weight()=7+9=16 ve(7)= maxve(4)+ weight(), ve(5)+ weight()=max7+7,7+4=14 ve(8)= maxve(6)+ weight(), ve(7)+ weight()=max16+2,14+4=18,例 求關(guān)鍵活動(dòng)第2步,按拓?fù)淠嫘蜻f推:,vl(8)= ve(8)=18 vl(7)= vl(8)-weight()=18
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 室內(nèi)設(shè)計(jì)服務(wù)員工作總結(jié)
- 能源化工行業(yè)市場總結(jié)
- 酒店員工培訓(xùn)計(jì)劃設(shè)計(jì)
- 音樂學(xué)校前臺(tái)服務(wù)心得
- 互聯(lián)網(wǎng)產(chǎn)品設(shè)計(jì)師工作總結(jié)
- 《易坦靜的臨床應(yīng)用》課件
- 2023-2024學(xué)年上海市徐匯區(qū)南洋模范中學(xué)高二(下)期中地理試卷
- 《燃?xì)饣A(chǔ)知識(shí)》課件
- 2022年廣東省河源市公開招聘警務(wù)輔助人員輔警筆試自考題2卷含答案
- 2024年湖北省隨州市公開招聘警務(wù)輔助人員輔警筆試自考題2卷含答案
- 2024消防安全基礎(chǔ)知識(shí)培訓(xùn)課件
- 《小兒留置導(dǎo)尿管》課件
- 粵教版科學(xué)四年級(jí)上冊(cè)全冊(cè)試卷(含答案)
- 宮腔鏡診治規(guī)范
- 安全管理計(jì)劃指標(biāo)和指標(biāo)體系
- 倉庫物料盤點(diǎn)作業(yè)規(guī)范培訓(xùn)課件
- 六年級(jí)《牽手兩代-第二講-乖孩子為什么會(huì)厭學(xué)》家長課程培訓(xùn)
- 水稻全生育期營養(yǎng)管理
- 節(jié)流閥流量計(jì)算公式
- 美甲店衛(wèi)生制度規(guī)章范本
- 湘少版三年級(jí)下冊(cè)英語單詞默寫1(附單元標(biāo)題句)
評(píng)論
0/150
提交評(píng)論