什麼是圖|ω･`) 圖G是一個有序二元組(V,E)，其中V稱為頂集(Vertices Set)，E稱為邊集(Edges set)，E與V不相交。它們亦可寫成V(G)和E(G)。 E的元素都是二元組，用(x,y)表示，其中x,y∈V。 （摘自百度百科） 簡單來說，圖就是由點和邊組成的東西。也可以理解為 ...
什麼是圖|ω･`)
圖G是一個有序二元組(V,E)，其中V稱為頂集(Vertices Set)，E稱為邊集(Edges set)，E與V不相交。它們亦可寫成V(G)和E(G)。
E的元素都是二元組，用(x,y)表示，其中x,y∈V。 （摘自百度百科）
簡單來說，圖就是由點和邊組成的東西。也可以理解為若幹個元素之間關係的抽象表示，邊即代表著對應頂點之間的相互關係。
圖的分類|ω･`)
1.有向圖與無向圖：
如果我們給圖中的每個邊規定了方向，即邊< x,y >中頂點x和y的順序不能隨便顛倒，那這個圖就叫做有向圖，反之即為無向圖。
2.單圖：
一個圖如果任意兩頂點之間只有一條邊（在有向圖中為兩頂點之間每個方向只有一條邊）；邊集中不含環，則稱為單圖。
3.連通圖、非連通圖與強連通圖：
在無向圖中，如果從頂點vi到頂點vj有路徑，則稱vi和vj連通。如果圖中任意兩個頂點之間都連通，則稱該圖為連通圖，否則，將其中的極大連通子圖稱為連通分量。在有向圖中，如果對於每一對頂點vi和vj，從vi到vj和從vj到vi都有路徑，則稱該圖為強連通圖；否則，將其中的極大連通子圖稱為強連通分量。
*沒有環的有向圖叫做DAG。
4.簡單圖與樹：
如果對於任意的頂點x和y，最多只有一條邊把他們相連，也就是說邊集中不含兩個或以上的(x,y)，那麼圖G稱為簡單圖。簡單圖可以用矩陣表示。
沒有環的無向連通圖叫做無向樹。
如果把一個有向圖變為無向圖後成為無向樹，那麼稱這個有向圖為一棵有向樹。
特別的：一個點也叫作一棵樹，如果有很多樹就叫做森林。
如果有向樹中存在一個頂點x使得從x能夠到達其餘所有頂點，那麼有向樹G=(V,E)稱為根在x的樹形圖。
有關圖的定義|ω･`)
- 階（Order）： 圖G的頂集V的大小（即頂點的數量）。
-
度（Degree）：一個頂點的度是指與該頂點相連的邊的條數，頂點v的度記作d(v)。
*入度和出度：有向圖中，一個點的入度為以該點為終點的路徑數量，出度為以該點為起點的路徑數量。
- 子圖（Sub-Graph）：當圖G’=(V’,E’) 其中V‘含於V，E’含於E，則G’稱作圖G=(V,E)的子圖。每個圖都是本身的子圖。
- 生成子圖（Spanning Sub-Graph）：如果圖g的點集與G的點集相同，g的邊集含於G的邊集，那麼稱g為G的生成子圖。特別的，如果g為無向樹，那麼稱g為圖G的生成樹。
-
導出子圖（Induced Subgraph）：頂集V1為V的非空子集，以兩端點均在V1中的（E中的）全體邊為邊集的G的子圖，稱為V1導出的導出子圖；邊集E1為E的非空子集，以E1中邊關聯的頂點的全體為頂點集的G的子圖，稱為E1導出的導出子圖。
*可知，圖G的任何子圖，都可以看作是圖G的某個導出子圖的生成子圖。
-
路徑（Path）：從u到v的一條路徑是指一個序列v0,e1,v1,e2,v2,…ek,vk，（A–1–>B–2–>C…)，其中ei的頂點為vi及vi - 1，k稱作路徑長度。如果它的起止頂點相同，該路徑是“閉”的，反之，則稱為“開”的。如果這條路徑除了u和w以外其餘頂點都各不相等，那麼稱這條路徑為簡單路徑。
*路徑長度： 一條路徑所經過的邊的數量。
*長度：路徑中所有邊的權值的和（可能為負）。 - 行跡（Trace）：如果路徑P(u,v)中的邊各不相同，則該路徑稱為u到v的一條行跡。
- 軌道（Track）：如果路徑P(u,v)中的頂點各不相同，則該路徑稱為u到v的一條軌道。
*閉的行跡稱作迴路（Circuit），閉的軌稱作圈（Cycle） - 環：如果一條路徑的起點和終點相等，那麼這條路徑稱為環（迴路）。
- 自環（Loop）：若一條邊的兩個頂點為同一頂點，則此邊稱作自環。
- 橋（Bridge）：若去掉一條邊，便會使得整個圖不連通，該邊稱為橋。
- 割點：若去掉一個點，便會使得整個圖不連通，則該頂點成為割點。
（參考百度百科）
圖的儲存|ω･`)
1.列表：開三個數組分別記錄每條邊的起點，終點和權值。
2.鄰接矩陣：f[i][j]=d表示一條從i到j的權值為d的邊。
3.鄰接表：用鏈表和結構體存每一條邊，並記下每個點連出的邊。
4.有向圖的十字鏈表存儲表示。
5.無向圖的鄰接多重表存儲表示。
*一個不帶權圖中若兩點不相鄰，鄰接矩陣相應位置為0，對帶權圖(網)，相應位置為∞。一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一。
*在有向圖中，通常將邊稱作弧，含箭頭的一端稱為弧頭，另一端稱為弧尾，記作< vi,vj >，它表示從頂點vi到頂點vj有一條邊。若有向圖中有n個頂點，則最多有n(n-1)條弧，我們又將具有n(n-1)條弧的有向圖稱作有向完全圖。以頂點v為弧尾的弧的數目稱作頂點v的出度，以頂點v為弧頭的弧的數目稱作頂點v的入度。
*在無向圖中，邊記作(vi,vj)，它蘊涵著存在< vi,vj >和< vj,vi
>兩條弧。若無向圖中有n個頂點，則最多有n(n-1)/2條弧，我們又將具有n(n-1)/2條弧的無向圖稱作無向完全圖。與頂點v相關的邊的條數稱作頂點v的度。
（摘自百度百科）
圖的遍歷|ω･`)
深度優先搜索（dfs）和廣度優先搜索（bfs）。
樹中的邊|ω･`)
- 樹邊指的是從父節點找到子結點所用的邊
- 前向邊指的是從祖先結點指向其子孫結點的非樹邊
- 後向邊指的是從子孫結點往回指向祖先結點的邊
- 橫叉邊指的是沒有祖孫關係的兩個結點之間的邊，起點的遍歷順序在終點之後。
PS：就先整理這些吧，以後再補充2333ヾﾉ≧∀≦)o
