圖的定義
圖是由定點(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)陷虎。
- 連通圖
在一個(gè)無(wú)向圖 G 中到踏,若從頂點(diǎn)i到頂點(diǎn)j有路徑相連(當(dāng)然從j到i也一定有路徑),則稱i和j是連通的尚猿。圖中任意兩個(gè)頂點(diǎn)Vi窝稿,Vj都是聯(lián)通的,則稱圖G為連通圖
注意 :是有路徑凿掂,不是有邊伴榔。
- 度
無(wú)向圖頂點(diǎn)的邊數(shù)叫度,有向圖頂點(diǎn)的邊數(shù)叫出度和入度
圖的數(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ú)向圖)