• 線(xiàn)性表是一對(duì)一，樹(shù)是一對(duì)多，圖是多對(duì)多的關(guān)系。
• 圖中的數(shù)據(jù)元素我們稱(chēng)為頂點(diǎn)（相對(duì)于樹(shù)中的結(jié)點(diǎn)），頂點(diǎn)集合不能為空，邊集合可以為空。
• 無(wú)向圖——只要圖中有一條邊是無(wú)向邊（A,B）。
• 有向圖——任意兩頂點(diǎn)之間的邊都是有向邊（?。?lt;A,B>。
• 無(wú)向完全圖——n個(gè)頂點(diǎn)中任意兩頂點(diǎn)之間都存在邊的無(wú)向圖。邊的總數(shù)是n*(n-1)/2。
• 有向完全圖——n個(gè)頂點(diǎn)中任意兩頂點(diǎn)之間都存在方向相反的有向邊的有向圖。邊的總數(shù)是n*(n-1)。
• 權(quán)——與圖的邊相關(guān)的數(shù)字。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。
• 網(wǎng)——帶權(quán)的圖。如網(wǎng)絡(luò)圖中，各條邊就是鏈路，鏈路都是有帶權(quán)（距離或帶寬）的。
• 子圖——G=(V,{E})，G'=(V',{E'})，其中V'是V的子集，E'是E的子集，則稱(chēng)G'是G的子圖(subgraph)。
• 頂點(diǎn)v的度degree——是和頂點(diǎn)v相連接的邊的數(shù)目。對(duì)于有向圖的頂點(diǎn)的度還分為出度和入度。
• 鄰接點(diǎn)——同一條邊的兩個(gè)點(diǎn)互為鄰接點(diǎn)。
• 路徑——指從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)過(guò)的頂點(diǎn)的序列。樹(shù)的路徑唯一，但圖的路徑不唯一，所以有很多求最短路徑的算法。在網(wǎng)絡(luò)圖中，路徑又叫路由。
• 路徑的長(zhǎng)度——路徑上的邊或弧的數(shù)目。
• 回路或環(huán)——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。
• 簡(jiǎn)單路徑——路徑序列中沒(méi)有重復(fù)出現(xiàn)的頂點(diǎn)。
• 簡(jiǎn)單回路——除了第一個(gè)和最后一個(gè)頂點(diǎn)相同外，其余的頂點(diǎn)都不相同。
• 連通圖（connected graph）——無(wú)向圖中任意兩個(gè)頂點(diǎn)都有路徑（即都是連通的）。
• 非連通圖——存在兩個(gè)頂點(diǎn)之間沒(méi)有路徑，即不連通。有n個(gè)頂點(diǎn)，但只有小于n-1條邊，一定是非連通圖。
• 連通分量——無(wú)向圖中的極大連通子圖。連通圖本身即是，而非連通圖中最大的連通子圖即是。
• 強(qiáng)連通圖——有向圖中，任意兩個(gè)頂點(diǎn)都存在雙向連通的路徑。有向圖的非強(qiáng)連通圖，對(duì)應(yīng)有強(qiáng)連通分量。
• 生成樹(shù)——一個(gè)連通圖的極小連通子圖，它含有圖中全部的n個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的n-1條邊（即去掉了環(huán)路）。不過(guò)n個(gè)頂點(diǎn)有n-1條邊并不一定是生成樹(shù)，比如一個(gè)非連通圖中有一部分是個(gè)環(huán)路。因此生成樹(shù)的前提一定是連通圖。
• 有向樹(shù)——一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0（根結(jié)點(diǎn)），其余頂點(diǎn)的入度均為1。
• 生成森林——一個(gè)有向圖的所有頂點(diǎn)，被分成若干顆不相交的有向樹(shù)，這些有向樹(shù)就組成了有向森林。

圖的存儲(chǔ)結(jié)構(gòu)

• 因?yàn)轫旤c(diǎn)間多對(duì)多的關(guān)系，所以不能用簡(jiǎn)單的順序結(jié)構(gòu)數(shù)組來(lái)表示。
• 因?yàn)楦鱾€(gè)頂點(diǎn)的度不一致，所以不能用數(shù)據(jù)域+若干指針域的多重鏈表形式來(lái)表示，否則將造成很大的浪費(fèi)。
• 圖的存儲(chǔ)結(jié)構(gòu)有5種特別的。

1、鄰接矩陣——重點(diǎn)關(guān)注頂點(diǎn)

2、鄰接表——對(duì)鄰接矩陣空間浪費(fèi)的改進(jìn)，重點(diǎn)關(guān)注頂點(diǎn)

3、十字鏈表——對(duì)有向圖的鄰接表進(jìn)行改進(jìn)，重點(diǎn)關(guān)注頂點(diǎn)

• 將展示出度的鄰接表和展示入度的逆鄰接表整合在一起。

4、鄰接多重表——對(duì)無(wú)向圖的鄰接表進(jìn)行改進(jìn)，重點(diǎn)關(guān)注邊

• 更關(guān)注邊的操作，仿照十字鏈表。
• 鄰接多重表與鄰接表的差別：同一條邊，在鄰接表中要用兩個(gè)結(jié)點(diǎn)表示，因此不便于刪除一條邊。然而在鄰接多重表中，每個(gè)節(jié)點(diǎn)表示一條邊，要?jiǎng)h除邊很簡(jiǎn)單。

5、邊集數(shù)組——重點(diǎn)關(guān)注邊，特別是與邊的權(quán)值有關(guān)的最小生成樹(shù)問(wèn)題

圖的遍歷方式

1、深度優(yōu)先搜索遍歷DFS——類(lèi)似于樹(shù)的先序遍歷，使用遞歸

2、廣度優(yōu)先搜索遍歷BFS——類(lèi)似于樹(shù)的層序遍歷，使用隊(duì)列

總結(jié)分析兩種遍歷方式

尋找最小生成樹(shù)——最小代價(jià)生成樹(shù)

以最小的成本完成任務(wù)？
在一個(gè)帶權(quán)值的圖中，即網(wǎng)中，n個(gè)頂點(diǎn)找到n-1條邊將他們連起來(lái)成為連通圖，并且各邊的權(quán)值總和最小，即為成本（代價(jià)）最小。類(lèi)似的問(wèn)題就是最小生成樹(shù)問(wèn)題。

1、普里姆(Prim)算法——鄰接矩陣，以某頂點(diǎn)為起點(diǎn)，逐步找各頂點(diǎn)上最小權(quán)值的邊來(lái)擴(kuò)展生成樹(shù)，然后將新的生成樹(shù)的各個(gè)頂點(diǎn)往外擴(kuò)展又加入一條最小權(quán)值的邊，以此類(lèi)推，直到所有頂點(diǎn)都加入得到最小生成樹(shù)。算法時(shí)間復(fù)雜度O(n^2)。其中n為頂點(diǎn)個(gè)數(shù)。

2、克魯斯卡爾(Kruskal)算法——邊集數(shù)組，先將各條邊按照權(quán)值排序，然后再依次將各邊加入到最小生成樹(shù)，遇到形成回路的邊就舍棄，直到所有頂點(diǎn)都加入了。算法時(shí)間復(fù)雜度O(n*logn)，其中n為邊數(shù)?？梢?jiàn)邊數(shù)較少的稀疏圖時(shí)，用該算法更優(yōu)，但是邊數(shù)很多的稠密圖用普里姆算法效果更好。