03 數(shù)據(jù)結(jié)構(gòu)-初識(shí)數(shù)據(jù)結(jié)構(gòu)-圖

圖的定義

  • 圖是由頂點(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ù)組(矩陣)景埃。無向圖/有向圖:
AdjacencyMatrix.png
AdjacencyMatrix1.png
* 頂點(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)囤热。
AdjacencyTable.png
* 鄰接表的存儲(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í)際需求,選擇使用鄰接表還是逆鄰接表所森。
ReverseAdjacency.png

十字鏈表

同理囱持,上述一個(gè)圖可能會(huì)存在要維護(hù)正反連個(gè)鄰接表夯接。十字鏈表正好是將兩種結(jié)合起來焕济。

CrossLinked.png
十字鏈表的每一個(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)芍阎。


CrossLinked-finish.png

圖中每一條帶有黑色箭頭的鏈表世曾,存儲(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):

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末剔猿,一起剝皮案震驚了整個(gè)濱河市视译,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌归敬,老刑警劉巖酷含,帶你破解...
    沈念sama閱讀 206,311評(píng)論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異汪茧,居然都是意外死亡椅亚,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,339評(píng)論 2 382
  • 文/潘曉璐 我一進(jìn)店門舱污,熙熙樓的掌柜王于貴愁眉苦臉地迎上來呀舔,“玉大人,你說我怎么就攤上這事扩灯∶睦担” “怎么了?”我有些...
    開封第一講書人閱讀 152,671評(píng)論 0 342
  • 文/不壞的土叔 我叫張陵珠插,是天一觀的道長(zhǎng)惧磺。 經(jīng)常有香客問我,道長(zhǎng)捻撑,這世上最難降的妖魔是什么磨隘? 我笑而不...
    開封第一講書人閱讀 55,252評(píng)論 1 279
  • 正文 為了忘掉前任,我火速辦了婚禮顾患,結(jié)果婚禮上番捂,老公的妹妹穿的比我還像新娘。我一直安慰自己江解,他們只是感情好设预,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,253評(píng)論 5 371
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著膘流,像睡著了一般絮缅。 火紅的嫁衣襯著肌膚如雪鲁沥。 梳的紋絲不亂的頭發(fā)上呼股,一...
    開封第一講書人閱讀 49,031評(píng)論 1 285
  • 那天耕魄,我揣著相機(jī)與錄音,去河邊找鬼彭谁。 笑死吸奴,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的缠局。 我是一名探鬼主播则奥,決...
    沈念sama閱讀 38,340評(píng)論 3 399
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼狭园!你這毒婦竟也來了读处?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 36,973評(píng)論 0 259
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤唱矛,失蹤者是張志新(化名)和其女友劉穎罚舱,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體绎谦,經(jīng)...
    沈念sama閱讀 43,466評(píng)論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡管闷,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,937評(píng)論 2 323
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了窃肠。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片包个。...
    茶點(diǎn)故事閱讀 38,039評(píng)論 1 333
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖冤留,靈堂內(nèi)的尸體忽然破棺而出碧囊,到底是詐尸還是另有隱情,我是刑警寧澤纤怒,帶...
    沈念sama閱讀 33,701評(píng)論 4 323
  • 正文 年R本政府宣布呕臂,位于F島的核電站,受9級(jí)特大地震影響肪跋,放射性物質(zhì)發(fā)生泄漏歧蒋。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,254評(píng)論 3 307
  • 文/蒙蒙 一州既、第九天 我趴在偏房一處隱蔽的房頂上張望谜洽。 院中可真熱鬧,春花似錦吴叶、人聲如沸阐虚。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,259評(píng)論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)实束。三九已至奥秆,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間咸灿,已是汗流浹背构订。 一陣腳步聲響...
    開封第一講書人閱讀 31,485評(píng)論 1 262
  • 我被黑心中介騙來泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留避矢,地道東北人悼瘾。 一個(gè)月前我還...
    沈念sama閱讀 45,497評(píng)論 2 354
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像审胸,于是被迫代替她去往敵國(guó)和親亥宿。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,786評(píng)論 2 345

推薦閱讀更多精彩內(nèi)容

  • 1. 圖的定義和基本術(shù)語(yǔ) 線性結(jié)構(gòu)中砂沛,元素僅有線性關(guān)系烫扼,每個(gè)元素只有一個(gè)直接前驅(qū)和直接后繼;樹形結(jié)構(gòu)中碍庵,數(shù)據(jù)元素(...
    yinxmm閱讀 5,429評(píng)論 0 3
  • 圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間的邊的集合組成映企,通常表示為:G(V,E)怎抛,其中卑吭,G表示一個(gè)圖,V是圖中的頂點(diǎn)的集...
    keeeeeenon閱讀 530評(píng)論 0 2
  • 1)這本書為什么值得看: Python語(yǔ)言描述马绝,如果學(xué)的Python用這本書學(xué)數(shù)據(jù)結(jié)構(gòu)更合適 2016年出版豆赏,內(nèi)容...
    孫懷闊閱讀 12,439評(píng)論 0 15
  • 圖是一種比線性表和樹更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)掷邦,在圖中,結(jié)點(diǎn)之間的關(guān)系是任意的椭赋,任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)抚岗。圖是一種多對(duì)...
    Alent閱讀 2,284評(píng)論 1 22
  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系,并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算哪怔,而且確保經(jīng)過這...
    Winterfell_Z閱讀 5,654評(píng)論 0 13