DAY 07 : 圖形

7.1 什麼是圖形?

線性串列是一對一的儲存結構，具有線性關係；樹型結構是一對多的儲存結構，具有階層關係，那麼若是多對多呢?

圖形是一種比線性串列和樹形結構更加複雜的資料結構，在圖形結構，節點之間的關係是任意的，意思就是每兩個資料元素之間都可能有關係。

• 圖形在非為空的狀態下，由｢頂點的集合」和｢邊的集合」所組成，表示方法為:G(V,E)，G表示一個圖形，V表示頂點集合，E表示邊的集合。
• 在圖形中我們將每一筆資料元素稱為頂點(Vertex/Node)。
• 在圖形結構中不允許沒有頂點存在，若V是頂點的集合，則須強調頂點集合V是有限但非為空的。不過邊的集合可以為空，頂點之間的邊可以表達邏輯關係。
• 簡單圖形(Simple Graph):
  1.沒有從頂點連到自己的邊。
  2.同一條邊不重複出現。
• 稠密圖與稀疏圖:
  取決於邊的條數。
• 權(Weight)以及加權圖形:
  與邊相關的數字稱為權，而這種加權的圖形就叫做加權圖形。
• 子圖(Subgraph):
  (請參考圖7.1)
  
  圖7.1
  圖中的左下角就是a)的子圖
  圖中的右上角就是b)的子圖

7.2 無向圖形

• 若兩個頂點的邊沒有方向性，則這條邊為無向邊(Edge)，用無序對(Vi,Vj)表示。
• 若圖形中的任意兩頂點之間的邊都是無向邊，則稱該圖形為無向圖形(Undirected Graphs)。
• 集合表示法E = {(A,B),(B,C)……}
• 若任意兩個頂點之間都存在無向邊，則稱為無向完全圖形(每個頂點要與除了自己以外的頂點連線)。
• 含有n個頂點的無向完全圖形會有n(n-1)/2條邊。

7.3 有向圖形

• 若兩個頂點的邊具有方向性，則這條邊為有向邊，用有序對(Vi,Vj)表示，Vi為箭尾(Tail)，Vj為箭頭(Head)。
• 注意!!!對的順序不可以調換!!!
• 集合表示法E = {<B,A>,<B,C>……}
• 若圖形中的任一兩點的邊都是有向邊，則稱該圖形為有向圖形(Undirected Graphs)。
• 若任意兩個頂點之間都存在方向互為相反的有向邊，則稱為有向完全圖形(每個頂點要與除了自己以外的頂點連線)。
• 含有n個頂點的有向完全圖形會有n*(n-1)條邊。