《圖說演算法-使用C#》要點摘錄

書名：《圖說演算法-使用C#》

作者：吳燦銘、胡昭民

所讀版本：博碩文化

非線性結構
描述節點和節點之間「層次」的關係
由一個或一個以上的節點組成
- 存在一個根節點
- 每個節點代表數據和指標組合而成的紀錄
- 根節點以外的節點可分為n >= 0個互斥的集合
- 每一個子集合本身也是一種樹狀結構
一個合法的樹，節點間可以互相連結，但不能沒有出口
分支度（Degree）：每個節點所有的子樹個數
階層（Level）：樹的層級
高度（Height）：樹的最大階層
葉節點（Terminal Nodes）：沒有子節點、分支度為0的節點
父節點（Parent）：節點的上一層節點
子節點（Children）：節點的下一層節點
祖先（Ancestor）：從樹根節點到該節點路徑上的所有節點
子孫（Descendant）：該節點下的所有子節點
兄弟節點（Siblings）：共同父節點的節點
非終端節點（Nonterminal Nodes）：葉節點外的節點
同代（Generations）：同階層數的節點
樹林（Forest）：移去樹根的所有節點
二叉樹與一般樹的不同
- 樹不可為空集合，二叉樹可以
- 樹的分支度為d >= 0，二叉樹的分支度為0 <= d <= 2
- 樹的子樹間沒有次序關係，二叉樹有

由「頂點」和「邊」組成的集合（G = (V, E)）
討論兩個頂點之間「相連與否」的關係
在圖形中連接兩點的邊添上加權值（cost），該圖形則為「網路」。
歐拉環（Eulerian cycle）
- 所有頂點的分支度皆為偶數，才能從某頂點出發，經過每一邊一次，再回到起點。
歐拉鏈（Eulerian chain）
- 從某頂點出發，經過每邊一次，不一定要回到起點，亦即只允許其中兩個頂點的分支度是奇數，其餘則必須全部為偶數。
無向圖形 (V1, V2)
- 具有同邊的兩個頂點沒有次序關係
有向圖形 <V1, V2>
- 具有同邊的兩個頂點有次序關係
- <V1, V2> != <V2, V1>
  - 前者是V1尾端指向V2首端
  - 後者是V2尾端指向V1首端

儲存紀錄的連續記憶體，表裡有n個bucket，每個bucket又可分為m個slot
雜湊函數（hash function）
- 將數據的鍵值經由特定數學運算或其他方法轉換成對應的數據存儲位址
桶（bucket）：儲存數據的位置，一筆記錄
槽（slot）：桶的欄位，一個桶可以有好幾個欄位
碰撞（collision）：兩筆不同的數據，經hash function運算後指向了同一個位址
溢位：數據經過hash function運算後，所指向的bucket已滿，bucket就會發生溢位
同義字（synonym）：兩個識別字經hash function運算後數值相同，這兩個字則為同義字
載入密度（loading factor）：識別字使用數 / (slot * bucket)
- 載入密度越大，hash空間使用度越高，發生collision和溢位的機會越高
完美離湊（perfect hashing）：沒有collision，沒有溢位的hash function
設計hash function的原則：
- 降低collision和溢位的產生
- hash function越易計算越好
- 盡量把文字的鍵值轉換為數字，方便運算
- hash function得出的值盡量均勻分布在每一個bucket中，避免過度集中，從而降低發生collision和溢位的機會