基本概念
- 數(shù)據(jù)元素之間是一種多對(duì)多的關(guān)系，用羅輯邊標(biāo)識(shí)元素之間的關(guān)系；
- 線性表中數(shù)據(jù)稱為
元素，樹中將元素稱為結(jié)點(diǎn)，圖中數(shù)據(jù)元素稱為頂點(diǎn)(vertex)，線性表可以為空表，樹可以為空樹，但是圖不允許有空結(jié)點(diǎn)； - 頂點(diǎn)
有窮非空集合和頂點(diǎn)之間的邊組成； - G(V,E) G: 表示一個(gè)圖，V: 表示頂點(diǎn)集合，E: 表示邊的集合；
簡單圖
- 不存在頂點(diǎn)到自身的邊；
- 同一條邊不重復(fù)出現(xiàn)；
- 是我們要討論的圖；
無向圖
- 頂點(diǎn)之間邊
無方向的邊稱為無向邊(A,B)； - 圖中任意兩個(gè)頂點(diǎn)之間的邊都是無向邊，稱該圖為
無向圖； - 無向圖中，任意兩個(gè)頂點(diǎn)都存在邊，稱該圖為
無向完全圖； - 無向完全圖有
(n*(n-1))/2條邊，n代表頂點(diǎn)數(shù)； - 無向圖頂點(diǎn)的度TD：
- 和頂點(diǎn)相關(guān)的邊的數(shù)目; TD=各頂點(diǎn)度的和；
- 邊的數(shù)量 e=(1/2)*TD
有向圖
- 頂點(diǎn)之間的邊
有方向的邊稱為有向邊或?。ˋrc）<A,B>； - 圖中任意兩個(gè)頂點(diǎn)之間的邊都是有向邊，稱該圖為
有向圖； - 圖中任意兩個(gè)頂點(diǎn)都存在方向
互為相反的兩條弧，稱該圖為有向完全圖； - 有向完全圖有
n*(n-1)條邊，n代表頂點(diǎn)數(shù)； - 有向圖頂點(diǎn)的度TD是各個(gè)頂點(diǎn)入度數(shù)+出度數(shù)之和：
- 度（TD）= 入度（ID）+出度（OD）;
- 邊的數(shù)量＝ID = OD;
網(wǎng)
- 與圖的邊或弧相關(guān)的數(shù)叫做
權(quán)； - 帶權(quán)的圖稱為
網(wǎng)；
路徑
路徑長度：路徑上的邊或弧的數(shù)量；
回路或環(huán)（cycle）：路徑中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)是
同一個(gè)頂點(diǎn)；簡單路徑：頂點(diǎn)不重復(fù)出現(xiàn)的路徑；
簡單回路（簡單環(huán)）：除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其他頂點(diǎn)不不重復(fù)的回路；
連通圖：
- 無向圖：
- 連通：兩個(gè)頂點(diǎn)間存在路徑，稱為這兩個(gè)頂點(diǎn)是連通的；
- 連通圖：圖中任意兩個(gè)頂點(diǎn)都是連通的；
- 連通分量：極大連通子圖；
- 子圖
- 子圖要連通
- 連通子圖含有極大頂點(diǎn)數(shù)；
- 連通子圖含有極大邊數(shù)；
- 連通分量再加入一個(gè)原圖頂點(diǎn)或邊就不連通了；
- 有向圖：
- 強(qiáng)連通圖：圖中任意頂點(diǎn)A,B A!=B, 存在A到B和B到Ａ的路徑；
- 強(qiáng)連通分量：極大連通子圖
生成樹
- 無向圖中連通并且有ｎ個(gè)頂點(diǎn)，n-1條邊叫
生成樹； - 有向圖中一頂點(diǎn)入度為０，其他各個(gè)頂點(diǎn)入度為１的叫
有向樹；
存儲(chǔ)結(jié)構(gòu)
鄰接矩陣
- 一個(gè)一維數(shù)組存頂點(diǎn)；
- 一個(gè)二維數(shù)組存圖中的邊/弧的信息（鄰接矩陣）；
- arc[1][3] = 0; v1到v3不存在邊；
- arc[2][4] = 1; v2到v4存在邊；
- 如果是網(wǎng)則 arc[i][j] = 權(quán)值；
- 無向圖頂點(diǎn)vi的度＝矩陣中第ｉ行或第ｉ列中值的和；
- 有向圖頂點(diǎn)vi的
入度＝矩陣中vi列的各數(shù)之和； - 有向圖頂點(diǎn)vi的
出度＝矩陣中vi行的各數(shù)之和；
鄰接表
- 對(duì)于邊數(shù)相對(duì)較小的圖，
鄰接矩陣會(huì)存在浪費(fèi)空間的情況； - 鄰接表：頂點(diǎn)存在一個(gè)一維數(shù)組中；
- 無向圖邊表：某一頂點(diǎn)所有鄰接點(diǎn)構(gòu)成一個(gè)單鏈表；( 有向圖分出邊表和入邊表（逆鄰接表） )；
十字鏈表
- 把鄰接表和逆鄰接表整合在一起；
- 為
有向圖設(shè)計(jì)； - 一維數(shù)組+單鏈表；
鄰接多重表
- 優(yōu)化無向表的鄰接表結(jié)構(gòu)；
- 同一條邊在鄰接表中用
兩個(gè)結(jié)點(diǎn)表示； - 同一條邊在鄰接多重表中用
一個(gè)結(jié)點(diǎn)表示； - 一維數(shù)組+單鏈表；
邊集數(shù)組
- 由兩個(gè)一維數(shù)組構(gòu)成，（一個(gè)存頂點(diǎn)信息，另一個(gè)存邊的信息）；
- 適合對(duì)對(duì)邊的處理；
