【文章內(nèi)容簡(jiǎn)介】 邊 表 data： 數(shù)據(jù)域 ， 存放頂點(diǎn)信息 。 adj： 指針域 ， 指向邊表中第一個(gè)結(jié)點(diǎn) 。 dest： 鄰接點(diǎn)域 ， 邊的終點(diǎn)在頂點(diǎn)表中的下標(biāo) 。 link： 指針域 ， 指向邊表中的下一個(gè)結(jié)點(diǎn) 。 圖的存儲(chǔ)結(jié)構(gòu) template class T, class E struct Edge { int dest。 E cost。 EdgeT,E *link。 …… }。 template class T, class E struct Vertex { T data。 EdgeT,E *adj。 }。 定義鄰接表的結(jié)點(diǎn) data adj dest link 圖的存儲(chǔ)結(jié)構(gòu) 1 0 3 ∧ 2 3 ∧ 1 ∧ 0 1 ∧ V1 V2 V3 V4 0 1 2 3 data adj V1 V3 V4 V2 無(wú)向圖的鄰接表 邊表中的結(jié)點(diǎn)表示什么？ 每個(gè)結(jié)點(diǎn)對(duì)應(yīng)圖中的一條邊， 鄰接表的空間復(fù)雜度為 O(n+e)。 圖的存儲(chǔ)結(jié)構(gòu) 1 0 3 ∧ 2 3 ∧ 1 ∧ 0 1 ∧ V1 V2 V3 V4 0 1 2 3 data adj V1 V3 V4 V2 無(wú)向圖的鄰接表 如何求頂點(diǎn) i 的度？ 頂點(diǎn) i的邊表中結(jié)點(diǎn)的個(gè)數(shù)。 圖的存儲(chǔ)結(jié)構(gòu) 如何判斷頂點(diǎn) i 和頂點(diǎn) j 之間是否存在邊 ? 測(cè)試頂點(diǎn) i 的邊表中是否存在終點(diǎn)為 j 的結(jié)點(diǎn)。 1 0 3 ∧ 2 3 ∧ 1 ∧ 0 1 ∧ V1 V2 V3 V4 0 1 2 3 data adj V1 V3 V4 V2 無(wú)向圖的鄰接表 圖的存儲(chǔ)結(jié)構(gòu) 有向圖的鄰接表 V1 V2 V3 V4 1 2 ∧ 2 ∧ 0 ∧ V1 V2 V3 V4 0 1 2 3 data adj ∧ 如何求頂點(diǎn) i 的出度？ 頂點(diǎn) i 的出邊表中結(jié)點(diǎn)的個(gè)數(shù)。 圖的存儲(chǔ)結(jié)構(gòu) 有向圖的鄰接表 V1 V2 V3 V4 1 2 ∧ 2 ∧ 0 ∧ V1 V2 V3 V4 0 1 2 3 data adj ∧ 如何求頂點(diǎn) i 的入度？ 各頂點(diǎn)的出邊表中以頂點(diǎn) i 為 終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。 圖的存儲(chǔ)結(jié)構(gòu) 有向圖的鄰接表 V1 V2 V3 V4 1 2 ∧ 3 ∧ 0 ∧ V1 V2 V3 V4 0 1 2 3 data adj ∧ 如何求頂點(diǎn) i 的所有鄰接點(diǎn)？ 遍歷頂點(diǎn) i 的邊表，該邊表中的所有終點(diǎn)都是頂點(diǎn) i 的鄰接點(diǎn)。 圖的存儲(chǔ)結(jié)構(gòu) 網(wǎng)圖的鄰接表 V1 V2 V3 V4 2 7 8 5 2 1 V1 V2 V3 V4 0 1 2 3 data adj ∧ 5 2 ∧ 8 3 ∧ 7 0 ∧ 圖的存儲(chǔ)結(jié)構(gòu) 鄰接表表示的圖的類(lèi)定義 圖的存儲(chǔ)結(jié)構(gòu) template class T, class E class Graphlnk:public GraphT,E{ friend istreamamp。 operator(istreamamp。 in, GraphlnkT,Eamp。 G)。 friend ostreamamp。 operator(ostreamamp。 out, GraphlnkT,Eamp。 G)。 public: Graphlnk(int sz=DefaultVertices)。 ~Graphlnk( ) T getValue(int i){ return i=0amp。amp。i=numVertices?NodeTable[i].data:0。} E getWeight(int v1, int v2){ int getFirstNeighbor(int v)。 …… private: VertexT,E* NodeTable。 int getVertexPos(const T vertex){ for(int i=0。inumVertices。i++) if(NodeTable[i].data==Vertex) return i。 return –1。} }。 圖的存儲(chǔ)結(jié)構(gòu)的比較 ——鄰接矩陣和鄰接表 O（ n2） O（ n+e） O（ n2） O（ n+e） 空間性能 時(shí)間性能 適用范圍 唯一性 鄰 接 矩 陣 鄰 接 表 稠密圖 稀疏圖 唯一 不唯一 圖的存儲(chǔ)結(jié)構(gòu) 圖的遍歷 圖的遍歷操作 圖的遍歷 是在從圖中 某 一頂點(diǎn)出發(fā)，對(duì)圖中所 有頂點(diǎn)訪問(wèn)一次且僅 訪問(wèn) 一次。 抽象操作， 可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里 簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。 圖的遍歷操作要解決的關(guān)鍵問(wèn)題 ① 在圖中 ， 如何選取遍歷的起始頂點(diǎn) ？ ?在 線性表 中，數(shù)據(jù)元素在表中的編號(hào)就是元素在序列中的位置，因而其編號(hào)是唯一的； ?在 樹(shù) 中，將結(jié)點(diǎn)按層序編號(hào)，由于樹(shù)具有層次性，因而其層序編號(hào)也是唯一的； ?在 圖 中，任何兩個(gè)頂點(diǎn)之間都可能存在邊，頂點(diǎn)是沒(méi)有確定的先后次序的，所以，頂點(diǎn)的編號(hào)不唯一。 為了定義操作的方便，將圖中的頂點(diǎn)按任意順序排列起來(lái)，比如，按頂點(diǎn)的存儲(chǔ)順序。 解決方案：從編號(hào)小的頂點(diǎn)開(kāi)始 。 圖的遍歷 ② 從某個(gè)起點(diǎn)始可能到達(dá)不了所有其它頂點(diǎn) ， 怎么辦 ？ 圖的遍歷操作要解決的關(guān)鍵問(wèn)題 解決方案：多次調(diào)用從某頂點(diǎn)出發(fā)遍歷圖的算法。 ?下面僅討論從某頂點(diǎn)出發(fā)遍歷圖的算法。 圖的遍歷 ③ 因圖中可能存在回路 ， 某些頂點(diǎn)可能會(huì)被重復(fù)訪問(wèn) ，那么如何避免遍歷不會(huì)因回路而陷入死循環(huán) 。 ④ 在圖中 ， 一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連 ， 當(dāng)這樣的頂點(diǎn) 訪問(wèn)過(guò)后 ， 如何選取下一個(gè)要訪問(wèn)的頂點(diǎn) ？ 圖的遍歷操作要解決的關(guān)鍵問(wèn)題 解決方案：附設(shè)訪問(wèn)標(biāo)志數(shù)組 visited[n] 。 解決方案： 深度 優(yōu)先遍歷和 廣度 優(yōu)先遍歷。 圖的遍歷 約翰 霍普克洛夫特 1939年生于西雅圖 。 1961年進(jìn)入斯坦福大學(xué)研究生院深造 ， 1962年獲碩士學(xué)位 ，1964年獲博士學(xué)位 。 畢業(yè)后先后在普林斯頓大學(xué) 、 斯坦福大學(xué)等著名學(xué)府工作 ， 也曾任職于一些科學(xué)研究機(jī)構(gòu)如 NSF（ 美國(guó)科學(xué)基金會(huì) ）和 NRC（ 美國(guó)國(guó)家研究院 ） 。 羅伯特 陶爾揚(yáng) 1948年 4月 30日生于加利福尼亞州 。 1969年本科畢業(yè)，進(jìn)入斯坦福大學(xué)研究生院，1972年獲得博士學(xué)位。 1986年圖靈獎(jiǎng)獲得者 圖的遍歷 1. 深度優(yōu)先遍歷 基本思想 ： ⑴ 訪問(wèn)頂點(diǎn) v； ⑵ 從 v的未被訪問(wèn)的鄰接點(diǎn)中選取一個(gè)頂點(diǎn) w，從 w出發(fā)進(jìn)行深度優(yōu)先遍歷； ⑶ 重復(fù)上述兩步，直至圖中所有和 v有路徑相通的頂點(diǎn)都被訪問(wèn)到。 圖的遍歷 深一層遞歸 遞歸返回 深度優(yōu)先遍歷序列 ?入棧序列 ?出棧序列 ? V1 V3 V2 V4 V5 V6 V7 V8 V1 遍歷序列： V1 V2 V2 V4 V4 V5 V5 圖的遍歷 深一層遞歸 遞歸返回 深度優(yōu)先遍歷序列 ?入棧序列 ?出棧序列 ? V1 V3 V2 V4 V5 V6 V7 V8 V1 遍歷序列： V1 V2 V2 V4 V4 V5 V8 V8 圖的遍歷 深一層遞歸 遞歸返回 深度優(yōu)先遍歷序列 ?入棧序列 ?出棧序列 ? V1 V3 V2 V4 V5 V6 V7 V8 V1 遍歷序列： V1 V2 V2 V4 V4 V5 V8 圖的遍歷 深一層遞歸 遞歸返回 深度優(yōu)先遍歷序列 ?入棧序列 ?出棧序列 ? V1 V3 V2 V4 V5 V6 V7 V8 V1 遍歷序列： V1 V7 V2 V4 V5 V8 V3 V3 V6 V6 V7 圖的遍歷 深一層遞歸 遞歸返回 深度優(yōu)先遍歷序列 ?入棧序列 ?出棧序列 ? V1 V3 V2 V4 V5 V6 V7 V8 遍歷序列： V1 V2 V4 V5 V8 V3 V6 V7 圖的遍歷 2. 廣度優(yōu)先遍歷 基本思想 ： ⑴ 訪問(wèn)頂點(diǎn) v； ⑵ 依次 訪問(wèn) v的各個(gè)未被訪問(wèn)的鄰接點(diǎn) v1, v2, … , vk； ⑶ 分別從 v1， v2， … ， vk出發(fā)依次訪問(wèn)它們未被訪問(wèn)的鄰接點(diǎn) ， 并使 “ 先 被訪問(wèn)頂點(diǎn)的鄰接點(diǎn) ” 先 于 “后被訪問(wèn)頂點(diǎn)的鄰接點(diǎn) ” 被訪問(wèn) 。 直至圖中所有與頂點(diǎn) v有路徑相通的頂點(diǎn)都被訪問(wèn)到 。 圖的遍歷 廣度優(yōu)先遍歷序列 ?入隊(duì)序列 ?出隊(duì)序列 ? V1 V3 V2 V4 V5 V6 V7 V8 遍歷序列： V1 V1 圖的遍歷 廣度優(yōu)先遍歷序列 ?入隊(duì)序列 ?出隊(duì)序列 ? V1 V3 V2 V4 V5 V6 V7 V8 遍歷序列： V1 V2 V2 V3 V3 圖的遍歷 廣度優(yōu)先遍歷序列 ?入隊(duì)序列 ?出隊(duì)序列 ? V1 V3 V2 V4 V5 V6 V7 V8 遍歷序列： V1 V2 V3 V3 V4 V4 V5 V5 圖的遍歷 廣度優(yōu)先遍歷序列 ?入隊(duì)序列 ?出隊(duì)序列 ? V1 V3 V2 V4 V5 V6 V7 V8 遍歷序列： V1 V2 V3 V4 V4 V5 V5 V6 V6 V7 V7 圖的遍歷 廣度優(yōu)先遍歷序列 ?入隊(duì)序列 ?出隊(duì)序列 ? V1 V3 V2 V4 V5 V6 V7 V8 遍歷序列： V1 V2 V3 V4 V5 V5 V6 V6 V7 V7 V8 V8 圖的遍歷 兩種遍歷算法時(shí)間性能的比較 O（ n2） O（ n+e） O（ n2） O（ n+e） 深度優(yōu)先搜索 廣度優(yōu)先搜索 鄰 接 矩 陣 鄰 接 表 圖的遍歷 要想判定一個(gè)無(wú)向圖是否為連通圖，或有幾個(gè)連通分量，通過(guò) 對(duì)無(wú)向圖遍歷即可得到結(jié)果。 ?非連通圖：需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索 ， 而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行 搜索過(guò)程中得到的頂點(diǎn)訪問(wèn)序列恰為其各個(gè)連通分量中的頂點(diǎn)集 。 ?連通圖：僅需從圖中任一頂點(diǎn)出發(fā) ， 進(jìn) 行深度優(yōu)先搜索 （ 或廣度優(yōu)先搜索 ） ， 便可訪問(wèn)到圖中所有頂點(diǎn) 。 無(wú)向圖的連通性 圖的遍歷 連通分量 1. count=0。 2. for (圖中每個(gè)頂點(diǎn) v) if (v尚未被訪問(wèn)過(guò) ) count++。 從 v出發(fā)遍歷該圖； 3. if (count==1) cout圖是連通的 。 else cout圖中有 count個(gè)連通分量 。 求無(wú)向圖的連通分量 圖的遍歷 【 例 】 以深度優(yōu)先搜索方法從頂點(diǎn) 出發(fā)遍歷圖 , 建立深度優(yōu)先生成森林。 A B C D E F G A A B D E C F G 有向圖 深度優(yōu)先生成森林 templateclass Type void Graph Type :: DFS_Forest ( Tree Type amp。T ) { TreeNode Type * rt, * subT。 int *visited = new int[n]。 //創(chuàng)建訪問(wèn)數(shù)組 for ( int i = 0。 i n。 i++ ) visited [i] = 0。 //初始化