圖形簡介

作天的樹狀結構是描述節點與節點之間，而圖形結構是兩個頂點之間是否相連。在圖形中連接兩點的邊若填上加權值，這類就稱為網路。

圖形理論最早是18世紀的尤拉提出的，為了解決「肯尼茲堡橋樑」，而想出來的理論，是著名的七橋理論。尤拉當時使用的方法就是圖形理論。

當時東普魯士柯尼斯堡跨普列戈利亞河，和中心有兩個小島。小島與河的兩岸有七條橋連接。在所有橋都能只走一遍的前提下，如何才能把所有的橋都走遍？

尤拉把實際的抽象問題轉化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區視為點。這樣若從某點出發後再回到這個點，這一點的線數必須是偶數，稱為偶頂點。連有奇數條線的點稱為奇數點。

尤拉的結論是，當所有頂點的分支度皆為偶數時，才能從某頂點出發，經過每一邊一次再回到起點。但在肯尼茲堡每個頂點分支度是奇數，所以思考的問題不可能發生，此理論就是尤拉環(Eulerian cycler)理論。

但如果條件改成從某頂點出發，經過每邊一次，不一定要回到起點，只允許其中兩個頂點的分支度是奇數，其餘則必須是偶數，符合這樣的稱為尤拉鏈(Eulerian chain)。

圖形是由頂點和邊所組成的集合，用G = (V,E)表示，其中V是所有頂點所成的集合，而E代表所有邊的集合。

圖形有分兩種:無向圖形及有向圖形，無向圖形以(V1,V2)表示，有向圖形以< V1, V2>表示。

🧋 無向圖形(Undirected Graph)

無向圖形是一種具備同邊的兩個頂點沒有次序關係，且邊集合的每一個邊都沒有方向性。

V = {A,B,C,D,E}
E = {(A,B), (A,E), (B,C), (B,D), (C,D), (C,E), (D,E)}

🧋 有向圖形(Directed Graph)

有向圖形的邊集合中的每個邊都有方向性

V = {A,B,C,D,E}
E = {<A,B>, <A,E>, <B,C>, <B,D>, <C,D>, <C,E>, <D,E>}

雜湊表

雜湊表示一種儲存記錄的連續記憶體，能透過雜湊函數的應用，快速存取與搜尋資料。雜湊函數就是將本身的鍵值，經由特定的數學函數運算或用其他方法，轉換成相對應的資料儲存位址。

雜湊表的優勢:

🐧 在資料大時，仍然維持常數時間的高效能

🐧 若資料數量上限已知，就可避免重新配置記憶體，效能更好

🐧 若資料型態已知，就可針對該資料型態找尋適合的雜湊函數最佳化

相對湊表劣勢:

🐔 資料量不夠大時，單一操作需要雜湊計算，開銷相對高

🐔 效能與雜湊函數相關，較差的函數容易雜湊碰撞，較佳函數成本較高

🐔 只能以某種偽隨機的順序疊代雜湊表

這邊來介紹有關雜湊的名詞:

🍚 bucket(桶): 雜湊表中儲存資料的位置，每一個位置對應到唯一的一個位址，桶就好比一筆紀錄

🍚 slot(槽): 每一筆紀錄中可能包含好幾個欄位，而slot就是桶中的欄位

🍚 collision(碰撞): 若兩筆不同的資料，經過雜湊函數運算後，對應到相同的位址時就稱為碰撞

🍚 溢位: 如果資料經過雜湊函數運算後，對應到的bucket已滿，就會使bucket溢位

🍚 雜湊表: 儲存記錄的連續記憶體。就像資料表的索引表格，可分為n個bucket，每個bucket又可分為m個slot

🍚 同義字(synonym): 當兩個識別字I1及I2，經過雜湊函數運算後所得的數值相同，即f(I1) = f(I2)，則稱I1與I2對於f這個雜湊函數是同義字

🍚 載入密度(loading factor): 指識別字的使用數目除以雜湊表內槽的總數

α(載入密度) = n(識別字的使用數目) / s(每一個桶內的槽數) * b(桶的數目)

🍚 完美雜湊(perfect hashing): 指沒有碰撞或溢位的雜湊函數