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)條邊。
#資料結構 #DataStructure #初學者







你可能感興趣的文章

C++筆記 以指標當作參數傳入函數

C++筆記 以指標當作參數傳入函數

Introducing Asymptotic Measures

Introducing Asymptotic Measures

C# 動態生成物件與其他物件綁定

C# 動態生成物件與其他物件綁定






留言討論