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)條邊。
