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

圖形簡介

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

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

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

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

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

圖形的定義

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

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

🧋 無向圖形(Undirected Graph)

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

如此範例(V1,V2)與(V2,V1)

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

🧋 有向圖形(Directed Graph)

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

如此範例()

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

雜湊表

雜湊表是一種儲存記錄的連續記憶體，能透過雜湊函數的應用，快速存取與搜尋資料。透過雜湊函數，計算鍵對應到容器內部的索引位置，而找到對應的值(value)。簡單來說雜湊函數就是將本身的鍵值，經由特定的數學函數運算或用其他方法，轉換成相對應的資料儲存位址。

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

🍚 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): 指沒有碰撞或溢位的雜湊函數

• 降低碰撞與溢位的產生

• 雜湊函數不宜過於複雜，越容易計算越佳

• 盡量把文字的鍵值轉換成數字的鍵值，以利雜湊函數的運用

• 所設計的雜湊函數計算而得的值，盡量能均勻地分佈在每一桶中，不要太過於集中在某一桶內，以降低碰撞並減少溢位的處理

今天把資料結構的圖形和雜湊介紹完，資料結構大概就到這邊，後面都還會詳細的介紹這些資料結構的演算法。

但你要試著想一下，到底什麼是抽象資料型態(因為抽象所以無法想像🙄)，但其實日常就有在用到抽象的資料了，不覺得這些都很平易近人嗎🙆

目前應該不會太難吧🦉🦉！！

要是哪裡理解上還是邏輯上有錯請各位大大指正，感謝 🧙🧙🧙。

資料來源 :
[1]: https://en.wikipedia.org/wiki/Graph_theory
[2]: https://rust-algo.club/collections/hash_map/index.html