Graph - 圖

1.如何定義一張圖：
 
圖(Graph)是由點(Vertex)與邊(Edge)構成，以G = (V,E)表示。



2.名詞定義：

• 度：頂點邊的數量
• 入度：進入該點的邊
• 出度：離開該點的邊
• 圖的方向：由邊決定，如果邊有方向為有向圖，沒有方向則為無向圖
• 子圖(Subgraph)：如果S是圖G的一部分，則S稱為G的子圖
• 路徑(Path)：路徑是由一序列的頂點所構成的，比如V1→V2→V5就是一條路徑
• 路徑的長度：路徑中邊的個數，比如 V1→V2→V5的長度為2
• 簡單路徑：(Simple Path)：沒有經過相同頂點的路徑
• 環：是一個起點與終點相同的簡單路徑
• 連通分量(Connected component)：
• 假設有一張圖G=(V,E)
• 連通分量是G的子圖，而且這些子圖必須包含所有的頂點。
• 連通分量可以有很多個，比如C1,C2,C3......
• 兩個不同的連通分量不會共用同一個點
• 他們所包含的頂點總數要 = V → VC1+VC2+VC3+...... = V
• 連通：
• 如果點A可以通到點B，則A與B是連通的
• 一張無向圖G=(V,E)如是連通，則G任意一點都能通至G的剩餘其他點
• 強連通：
• 如果點A可以通到點B，點B也能通至點A，則AB是強連通的
• 一張有向圖G=(V,E)如是強連通，則G任意點都能通至G的剩餘其他點
• 強連通分量：為最大的強連通子圖
• 關節點： 
• 對於一無向張圖G而言，如果刪除了點V，會將圖切割成至少兩個連通分量，那麼V便是一個關節點
• 雙連通圖：不存在關節點的圖
• 雙連通單元：圖形中最大的雙連通子圖

3.如何表示一張圖：

• 相鄰矩陣：對於G=(V,E)，需要一個V*V的陣列，若V1可通至V2 → A[V1][V2]=1
• 相鄰串列：利用鍊表連接該頂點可通往的所有頂點
• 對一個無向圖而言，耗費空間為：V*2E (每個頂點都儲存邊，無向圖邊是雙向的故乘上2)
• 相鄰多元串列

4.如何遍歷一張圖：

• 深度優先(DFS)：利用堆疊的概念。
• 廣度優先(BFS)：利用佇列的概念。