思維導圖

　圖的定義
圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。
在圖中需要注意的是：
　　（1）線性表中我們把數據元素叫元素，樹中將數據元素叫結點，在圖中數據元素，我們則稱之為頂點（Vertex）。
　?。?）線性表可以沒有元素，稱為空表；樹中可以沒有節點，稱為空樹；但是，在圖中不允許沒有頂點（有窮非空性）。
　　（3）線性表中的各元素是線性關系，樹中的各元素是層次關系，而圖中各頂點的關系是用邊來表示（邊集可以為空）。
　圖的基本概念
　 （1）無向圖：
如果圖中任意兩個頂點之間的邊都是無向邊（簡而言之就是沒有方向的邊），則稱該圖為無向圖（Undirected graphs）

　?。?）有向圖：
如果圖中任意兩個頂點之間的邊都是有向邊（簡而言之就是有方向的邊），則稱該圖為有向圖（Directed graphs）。

　?。?）無向完全圖：
a.無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。（含有n個頂點的無向完全圖有(n×(n-1))/2條邊）如下圖所示：

b.有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。（含有n個頂點的有向完全圖有n×(n-1)條邊）如下圖所示：

　?。?）鄰接點：
在一個無向圖中，若存在一條（i，j），則稱頂點i和頂點j為該邊的兩個端點，并稱它們互為鄰接點。
　　（5）度：
a.頂點的度：在一個無向圖中，一個頂點所關聯的邊的數目稱為該頂點的度。
b.入度：在有向圖中，以頂點j為終點的邊數目，稱為該頂點的入度。
c.出度：在有向圖中，以頂點i為起點的邊數目，稱為該頂點的出度。
　?。?）路徑：
在無向圖中，若從頂點Vi出發有一組邊可到達頂點Vj，則稱頂點Vi到頂點Vj的頂點序列為從頂點Vi到頂點Vj的路徑。
　?。?）簡單路徑：
若一條路徑上除開始點和結束點可以相同以外，其他點均不相同，則稱此路徑為簡單路徑。

　?。?）回路和環：
若一條路徑上的開始點和結束點為同一個頂點，則此路徑被稱為回路或環。
　　（9）連通圖：
在無向圖G中，任意兩個頂點都是連通的，則稱G為連通圖。
　?。?0）強連通圖：
在有向圖G中，任意兩個頂點i和j都連通，則稱圖G為強連通圖。
　?。?2）簡單回路(簡單環)：
除了第一個頂點和最后一個頂點之外，其余頂點不重復出現的回路。
　?。?3）連通：
在無向圖 G 中，從頂點 V 到頂點 S 有路徑，則稱 V 和 S 是連通的。
　?。?4）連通分量：
無向圖中的極大連通子圖。
　?。?5）強連通分量：
有向圖中極大強連通子圖稱為強連通分量。

　圖的存儲結構
　 （1）鄰接矩陣存儲方法：
圖的鄰接矩陣是一種采用鄰接矩陣數組表示頂點之間和頂點之間相鄰關系的存儲結構。

　?。?）鄰接表存儲方法：
圖的鄰接表是一種順序與鏈式存儲相結合的存儲方法。鄰接表由表頭節點和表節點兩部分組成，圖中每個頂點均對應一個存儲在數組中的表頭節點。如果這個表頭節點所對應的頂點存在鄰接節點，則把鄰接節點依次存放于表頭節點所指向的單向鏈表中。
　圖的疑難點
　?。?）拓撲排序問題：一種是“從前向后”的排序，一種是“從后向前”排。
　?。?）關鍵路徑問題：一是什么是關鍵路徑，二是最早時間是什么意思、如何求，三是最晚時間是什么意思、如何求。