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

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

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

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

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

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

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

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

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

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

圖的遍歷方式

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

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

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

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

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

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

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