數(shù)據(jù)結(jié)構(gòu)-圖基礎(chǔ)

圖的定義

圖是由定點(diǎn)的有窮非空集合和頂點(diǎn)之間邊組成,通常表示為G(V,E),其中G表示一個(gè)圖赚抡,V表示圖G的頂點(diǎn)锣夹,E表示圖G邊的集合

圖的性質(zhì)

線性表我們把數(shù)據(jù)元素叫做做元素谦趣,樹(shù)中我們將數(shù)據(jù)元素叫做結(jié)點(diǎn)烫扼,在圖中的數(shù)據(jù)元素我們叫做頂點(diǎn)(Vertex)

線性表可以沒(méi)有元素胡嘿,叫空表链患。樹(shù)可以沒(méi)有結(jié)點(diǎn)嘶摊,做空樹(shù)曼追。

線性表中栅受,相鄰元素之間具有線性關(guān)系族铆。在樹(shù)中岩四,相鄰兩層結(jié)點(diǎn)具有層次關(guān)系。而圖中哥攘,任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系剖煌,頂點(diǎn)之間的邏輯關(guān)系用邊來(lái)表示,邊集可以是空集逝淹。

圖的分類

  • 無(wú)向圖
    直觀來(lái)說(shuō)耕姊,若一個(gè)中每條邊都是無(wú)方向的,則稱為無(wú)向圖栅葡。
    無(wú)序?qū)?vi茉兰,vj)和(vj,vi)表示同一條邊妥畏。

    無(wú)向圖.png

    在無(wú)向圖中邦邦,若每?jī)蓚€(gè)頂點(diǎn)都有邊安吁,則稱該圖為無(wú)向完全圖。
    無(wú)向完全圖.png

  • 有向圖
    若從頂點(diǎn)Vi到Vj的邊有方向燃辖,則這條邊為有向邊鬼店,也稱為弧。用序偶<Vi,Vj>表示黔龟,Vi稱為弧尾(Tail)妇智,Vj稱為弧頭(Head)。
    如果圖中任意兩條邊的都是有向邊氏身,則稱該圖為有向圖巍棱。


    有向圖.png

在有向圖中,若每?jī)蓚€(gè)頂點(diǎn)都有互為相反方向的兩條有向邊蛋欣,則稱該圖為有向完全圖航徙。

  • 圖的權(quán)
    有些圖的邊或者弧度具有與他相關(guān)的數(shù)字,這種與圖的邊或者弧相關(guān)的數(shù)字叫做權(quán)陷虎。
image.png
  • 連通圖

在一個(gè)無(wú)向圖 G 中到踏,若從頂點(diǎn)i到頂點(diǎn)j有路徑相連(當(dāng)然從j到i也一定有路徑),則稱i和j是連通的尚猿。圖中任意兩個(gè)頂點(diǎn)Vi窝稿,Vj都是聯(lián)通的,則稱圖G為連通圖

注意 :是有路徑凿掂,不是有邊伴榔。

image.png

無(wú)向圖頂點(diǎn)的邊數(shù)叫度,有向圖頂點(diǎn)的邊數(shù)叫出度和入度


image.png

image.png

圖的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

不能用簡(jiǎn)單的順序存儲(chǔ)結(jié)構(gòu)表示庄萎,也不能用多重鏈表結(jié)構(gòu)踪少,因?yàn)橛锌臻g的浪費(fèi)。

  • 鄰接矩陣


    image.png

    在無(wú)向圖中惨恭,邊是相當(dāng)于兩個(gè)頂點(diǎn)相互指向秉馏,鄰接矩陣關(guān)于斜邊對(duì)稱


    image.png

使用數(shù)組的形式來(lái)儲(chǔ)存數(shù)據(jù)

  • 鄰接表
  • 十字鏈表(有向圖)
  • 鄰接多重表(無(wú)向圖)
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市脱羡,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌免都,老刑警劉巖锉罐,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異绕娘,居然都是意外死亡脓规,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門险领,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)侨舆,“玉大人秒紧,你說(shuō)我怎么就攤上這事“は拢” “怎么了熔恢?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)臭笆。 經(jīng)常有香客問(wèn)我叙淌,道長(zhǎng),這世上最難降的妖魔是什么愁铺? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任鹰霍,我火速辦了婚禮,結(jié)果婚禮上茵乱,老公的妹妹穿的比我還像新娘茂洒。我一直安慰自己,他們只是感情好瓶竭,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布获黔。 她就那樣靜靜地躺著,像睡著了一般在验。 火紅的嫁衣襯著肌膚如雪玷氏。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天腋舌,我揣著相機(jī)與錄音盏触,去河邊找鬼。 笑死块饺,一個(gè)胖子當(dāng)著我的面吹牛赞辩,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播授艰,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼辨嗽,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了淮腾?” 一聲冷哼從身側(cè)響起糟需,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎谷朝,沒(méi)想到半個(gè)月后洲押,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡圆凰,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年杈帐,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡挑童,死狀恐怖累铅,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情站叼,我是刑警寧澤娃兽,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站大年,受9級(jí)特大地震影響换薄,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜翔试,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一轻要、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧垦缅,春花似錦冲泥、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至怔球,卻和暖如春嚼酝,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背竟坛。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工闽巩, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人担汤。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓涎跨,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親崭歧。 傳聞我的和親對(duì)象是個(gè)殘疾皇子隅很,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

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