圖的定義
圖是由定點(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ú)向圖）
