一、今日的學習的是圖這一部分，圖這一部分是個人感覺最難的，所以最先開始復習，并且分幾塊復習。

圖（Graph）G是由兩個集合V和E組成，記為G=(V,E).

V是頂點的的有窮非空集合，V(G)表示圖的頂點集（頂點的單詞為vertex）.

E是邊的有窮非空集，E(G)表示圖的邊集合，若邊集為有向邊的集合，則稱該圖為有向圖；若邊集為無向邊的集合，則稱該圖為無向圖。（邊的單詞為：edge）。

二、一些基本術語

（1）子圖：假設有兩個圖，G=（V，E）和G1=（V1，E1），如果V1?集合屬于V，E1集合屬于E，則稱G1為G的子圖。

（2）對于無向圖，若具有n(n-1)/2條邊，則稱為無向完全圖；對于有向圖，若具有n(n-1)條弧則稱為有向完全圖。

（3）有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。對于稀疏圖，鄰接表的表示法更適合；對于稠密圖，鄰接矩陣的表示法更適合

（4）權和網：在實際應用中，每條邊可以表上具有某種含義的數值，該數值稱為該邊上的權，這些權可以表示從一個頂點到另一個頂點的距離或耗費。這種帶權的圖通常稱為網。

（5）鄰接點：對于無向圖G，如果圖的邊（v，v1）∈E，則稱頂點v和v1互為鄰接點，即這兩點相鄰接。邊（v，v1）依附于頂點v,v1,或者說v,v1相關聯(lián)。

（6）度：頂點v的度就是指和v相關聯(lián)的邊的數目，記為TD(v).

（7）對于有向圖，頂點v的度分為出度和入度。出度是以頂點v為尾的弧的數目，記為OD(v),入度是以頂點v為頭的弧的數目，記為ID(v)。

一般地，如果一個頂點的度記為TD(vi),那么一個有n個頂點，e條邊的圖，滿足如下關系

e=1/2∑?TD（vi）

（7）在無向圖G中，從頂點v到v1的路徑是一個頂點序列，如果G為有向圖，則路徑也是有向的。路徑長度是一條路徑上經過的弧或者邊的數目。

（8）第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)。

（9）序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑。除第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路稱為簡單回路或簡單環(huán)。

（10）如果從頂點v到頂點v1有路徑，則稱v和v1是連通的。如果對于圖中任意兩個頂點都是連通的，則稱G為連通圖。連通分量就是指無向圖中的極大連通子圖。

（11）對于有向圖，如果對于每一對v1,v2∈V,v1≠ v2,從v1到v2和v2到v1都存在路徑（即任意兩點存在雙向路徑），則稱G為強連通圖。有向圖的強連通分量就是指有向圖中的極大強連通子圖。

（參考自教材嚴蔚敏版《數據結構》）