圖的定義
圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成座咆,通過表示為G(V,E),其中案淋,G標(biāo)示一個(gè)圖座韵,V是圖G中頂點(diǎn)的集合,E是圖G中邊的集合。
無邊圖:若頂點(diǎn)Vi到Vj之間的邊沒有方向誉碴,則稱這條邊為無項(xiàng)邊(Edge)宦棺,用序偶對(duì)(Vi,Vj)標(biāo)示。
有向圖:若從頂點(diǎn)Vi到Vj的邊是有方向的黔帕,則成這條邊為有向邊代咸,也稱為弧(Arc)成黄。用有序?qū)Γ╒i呐芥,Vj)標(biāo)示,Vi稱為弧尾奋岁,Vj稱為弧頭思瘟。如果任意兩條邊之間都是有向的,則稱該圖為有向圖闻伶。
有向圖G2中潮太,G2=(V2,{E2}),頂點(diǎn)集合(A,B,C,D),弧集合E2={<A,D>,{B,A},<C,A>,<B,C>}.
- 權(quán)(Weight):有些圖的邊和弧有相關(guān)的數(shù)虾攻,這個(gè)數(shù)叫做權(quán)(Weight)铡买。這些帶權(quán)的圖通常稱為網(wǎng)(Network)。
圖的表示
鄰接矩陣
- 說明
擁有n個(gè)頂點(diǎn)的圖霎箍,它所包含的連接數(shù)量最多是n(n-1)個(gè)奇钞;因此,要表達(dá)各個(gè)頂點(diǎn)之間的關(guān)聯(lián)關(guān)系漂坏,最清晰易懂的方式是使用二維數(shù)組(矩陣)景埃。無向圖/有向圖:
* 頂點(diǎn)0和頂點(diǎn)1之間有邊關(guān)聯(lián),那么矩陣中的元素A[0][1]與A[1][0]的值就是1顶别;
* 頂點(diǎn)1和頂點(diǎn)2之間沒有邊關(guān)聯(lián)谷徙,那么矩陣中的元素A[1][2]與A[2][1]的值就是0。
* 矩陣從左上到右下的一條對(duì)角線驯绎,其上的元素值必然是0:任何一個(gè)頂點(diǎn)與它自身是沒有連接的完慧。
* 無向圖對(duì)應(yīng)的矩陣是一個(gè)對(duì)稱矩陣,因此A[m][n]和A[n][m]的值一定相等剩失。
* 有向圖不再是一個(gè)對(duì)稱矩陣屈尼,,因此A[m][n]和A[n][m]的值不一定相等拴孤。
優(yōu)點(diǎn):簡(jiǎn)單直觀脾歧,可以快速查到一個(gè)頂點(diǎn)和另一頂點(diǎn)之間的關(guān)聯(lián)關(guān)系。
缺點(diǎn):占用空間大演熟,如果一個(gè)圖有1000個(gè)頂點(diǎn)鞭执,其中只有10個(gè)頂點(diǎn)之間有關(guān)聯(lián)(這種情況叫做稀疏圖),卻不得不建立一個(gè)1000X1000的二維數(shù)組。
鄰接表 和 逆鄰接表
-
鄰接表
為了解決鄰接矩陣占用空間的問題兄纺。鄰接表中免猾,圖的每一個(gè)頂點(diǎn)都是一個(gè)鏈表的頭節(jié)點(diǎn),其后連接著該頂點(diǎn)能夠直接達(dá)到的相鄰頂點(diǎn)囤热。
* 鄰接表的存儲(chǔ)方式猎提,占用的空間比鄰接矩陣要小得多;
* 想查出從頂點(diǎn)0能否到達(dá)頂點(diǎn)1,該怎么做呢旁蔼?很簡(jiǎn)單锨苏,我們從頂點(diǎn)0開始,順著鏈表的頭節(jié)點(diǎn)向后遍歷棺聊,看看后繼的節(jié)點(diǎn)中是否存在頂點(diǎn)1伞租。
* 想查出頂點(diǎn)0能夠到達(dá)的所有相鄰節(jié)點(diǎn),也很簡(jiǎn)單限佩,從頂點(diǎn)0向后的所有鏈表節(jié)點(diǎn)葵诈,就是頂點(diǎn)0能到達(dá)的相鄰節(jié)點(diǎn)。
* 要想查出有哪些節(jié)點(diǎn)能一步到達(dá)頂點(diǎn)1祟同,這樣就麻煩一些了作喘,我們要遍歷每一個(gè)頂點(diǎn)所在的鏈表,看看鏈表節(jié)點(diǎn)中是否包含節(jié)點(diǎn)1晕城,最后發(fā)現(xiàn)頂點(diǎn)0和頂點(diǎn)3可以到達(dá)頂點(diǎn)1泞坦。
-
逆鄰接表
針對(duì)上述逆向查找的麻煩的問題,可以是用逆鄰接表來解決砖顷。逆鄰接表贰锁,和鄰接表是正好相反的。逆鄰接表每一個(gè)頂點(diǎn)作為鏈表的頭節(jié)點(diǎn)滤蝠,后繼節(jié)點(diǎn)所存儲(chǔ)的是能夠直接達(dá)到該頂點(diǎn)的相鄰頂點(diǎn)豌熄。
要想查出有哪些節(jié)點(diǎn)能一步到達(dá)頂點(diǎn)1就容易了,從頂點(diǎn)1向后的所有鏈表節(jié)點(diǎn)物咳,就是能一步到達(dá)頂點(diǎn)1的節(jié)點(diǎn)锣险。
根據(jù)實(shí)際需求,選擇使用鄰接表還是逆鄰接表所森。
十字鏈表
同理囱持,上述一個(gè)圖可能會(huì)存在要維護(hù)正反連個(gè)鄰接表夯接。十字鏈表正好是將兩種結(jié)合起來焕济。
十字鏈表的每一個(gè)頂點(diǎn),都是兩個(gè)鏈表的根節(jié)點(diǎn)盔几,其中一個(gè)鏈表存儲(chǔ)著該頂點(diǎn)能到達(dá)的相鄰頂點(diǎn)晴弃,另一個(gè)鏈表存儲(chǔ)著能到達(dá)該頂點(diǎn)的相鄰節(jié)點(diǎn)。
我們沒有必要把鏈表的節(jié)點(diǎn)都重復(fù)存儲(chǔ)兩次。在優(yōu)化之后的十字鏈表中上鞠,鏈表的每一個(gè)節(jié)點(diǎn)不再是頂點(diǎn)际邻,而是一條邊,里面包含起止頂點(diǎn)的下標(biāo)芍阎。
圖中每一條帶有黑色箭頭的鏈表世曾,存儲(chǔ)著從頂點(diǎn)出發(fā)可到達(dá)的邊;每一條彩色箭頭的鏈表谴咸,存儲(chǔ)著進(jìn)入頂點(diǎn)的邊轮听。
圖的搜索
- 深度優(yōu)先遍歷:
也有稱為深度優(yōu)先搜索,簡(jiǎn)稱DFS(Depth First Search)
岭佳。其實(shí)血巍,就像是一棵樹的前序遍歷。它從圖中某個(gè)結(jié)點(diǎn)v出發(fā)珊随,訪問此頂點(diǎn)述寡,然后從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖,直至圖中所有和v有 路徑相通的頂點(diǎn)都被訪問到叶洞。若圖中尚有頂點(diǎn)未被訪問鲫凶,則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn),重復(fù)上述過程衩辟,直至圖中的所有頂點(diǎn)都被訪問到為止掀序。
基本實(shí)現(xiàn)思想:
(1)訪問頂點(diǎn)v;
(2)從v的未被訪問的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)w惭婿,從w出發(fā)進(jìn)行深度優(yōu)先遍歷不恭;
(3)重復(fù)上述兩步,直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到财饥。
- 廣度優(yōu)先遍歷:
也稱廣度優(yōu)先搜索换吧,簡(jiǎn)稱BFS(Breadth First Search)
。BFS算法是一個(gè)分層搜索的過程钥星,和樹的層序遍歷算法類同沾瓦,它也需要一個(gè)隊(duì)列以保持遍歷過的頂點(diǎn)順序,以便按出隊(duì)的順序再去訪問這些頂點(diǎn)的鄰接頂點(diǎn)谦炒。
基本實(shí)現(xiàn)思想:
(1)頂點(diǎn)v入隊(duì)列贯莺。
(2)當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)行,否則算法結(jié)束宁改。
(3)出隊(duì)列取得隊(duì)頭頂點(diǎn)v缕探;訪問頂點(diǎn)v并標(biāo)記頂點(diǎn)v已被訪問。
(4)查找頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)col还蹲。
(5)若v的鄰接頂點(diǎn)col未被訪問過的爹耗,則col入隊(duì)列耙考。
(6)繼續(xù)查找頂點(diǎn)v的另一個(gè)新的鄰接頂點(diǎn)col,轉(zhuǎn)到步驟(5)。
直到頂點(diǎn)v的所有未被訪問過的鄰接點(diǎn)處理完。轉(zhuǎn)到步驟(2)芬探。
廣度優(yōu)先遍歷圖是以頂點(diǎn)v為起始點(diǎn)毒费,由近至遠(yuǎn),依次訪問和v有路徑相通而且路徑長(zhǎng)度為1,2,……的頂點(diǎn)。為了使“先被訪問頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問頂點(diǎn)的鄰接點(diǎn)”被訪問炫狱,需設(shè)置隊(duì)列存儲(chǔ)訪問的頂點(diǎn)。
下一節(jié)主要實(shí)現(xiàn):