資料結構/圖

資料結構
引言 - 漸進符號 - 陣列 - 列表結構 & 迭代器
棧 & 佇列 - 樹 - 最小 & 最大堆 - 圖
雜湊表 - 集合 - 權衡

圖

圖是一種結構，由一組頂點 $\{v_{1},v_{2},\dots ,v_{n}\}$ 和一組邊 $\{e_{1},e_{2},\dots ,e_{m}\}$ 組成。邊是一對頂點 $\{v_{i},v_{j}\}\ i,j\in \{1..n\}$。這兩個頂點被稱為邊的端點。圖在計算機科學中無處不在。它們被用來模擬現實世界的系統，例如網際網路（每個節點代表一個路由器，每條邊代表路由器之間的連線）；航空公司連線（每個節點是一個機場，每條邊是一次航班）；或城市道路網路（每個節點代表一個交叉路口，每條邊代表一個街區）。計算機圖形中的線框圖是圖的另一個例子。

圖可以是無向的或有向的。直觀地，無向邊模擬了其端點之間的“雙向”或“雙工”連線，而有向邊是一條單向連線，通常被繪製成箭頭。有向邊通常被稱為弧。從數學角度來看，無向邊是頂點的無序對，而弧是有序對。例如，道路網路可以被模擬成一個有向圖，其中單行道用箭頭表示端點之間適當的方向，而雙行道用一對平行有向邊表示端點之間兩個方向。你可能會問，為什麼不用一個無向邊來表示雙行道呢？從理論上講，這沒有問題，但在實際的程式設計中，一般來說，堅持使用所有有向邊或所有無向邊會更簡單，更不容易出錯。

一個無向圖最多可以有 $\left({\begin{array}{c}n+1\\2\end{array}}\right)$ 條邊（每對無序對一條），而一個有向圖最多可以有 $n^{2}$ 條邊（每對有序對一條）。如果一個圖的邊遠少於這個數量（通常是 $O(n)$ 條邊），則稱該圖是稀疏的，而如果一個圖的邊接近於 $\Omega (n^{2})$ 條邊，則稱該圖是稠密的。多重圖在同一對頂點之間可以有多條邊。例如，如果有人模擬航班，在兩個城市之間可能有多趟航班，發生在一天中的不同時間。

圖中的路徑是指一系列頂點$\{v_{i_{1}},v_{i_{2}},\dots ,v_{i_{k}}\}$，其中相鄰頂點之間存在邊或弧。當$v_{i_{1}}\equiv v_{i_{k}}$時，該路徑被稱為環。無向無環圖等同於無向樹。有向無環圖被稱為DAG，它不一定是一棵樹。

節點和邊通常具有關聯資訊，例如標籤或權重。例如，在一個航空航班圖中，一個節點可能用相應機場的名稱進行標記，一條邊可能具有等於飛行時間的權重。流行的遊戲"六度空間"可以用一個帶標籤的無向圖來建模。每個演員成為一個節點，用演員的姓名標記。當兩個演員在同一電影中出現時，節點之間透過一條邊連線。我們可以用電影的名稱來標記這條邊。判斷一個演員是否與凱文·貝肯之間存在六個或更少的步驟，等同於在圖中尋找一條長度不超過六的路徑，這條路徑連線著貝肯的頂點和另一個演員的頂點。（這可以用在配套的演算法書中找到的廣度優先搜尋演算法來完成。弗吉尼亞大學的貝肯神諭已經實現了這個演算法，它可以通過幾個點選就能告訴你任何演員到凱文·貝肯的路徑[1]。）

有向圖

一個有向圖。

以給定頂點為端點的邊的數量被稱為該頂點的度。在有向圖中，指向給定頂點的邊的數量被稱為其入度，而從其指向的邊的數量被稱為其出度。通常，我們可能希望能夠區分不同的節點和邊。我們可以將標籤與兩者關聯。我們稱這樣的圖標記圖。

有向圖操作

make-graph(): 圖

建立一個新的圖，最初沒有節點或邊。

make-vertex(圖 G, 元素 value): 頂點

建立一個新的頂點，並賦予給定的值。

make-edge(頂點 u, 頂點 v): 邊

在u和v之間建立一條邊。在有向圖中，邊將從u流向v。

get-edges(頂點 v): 邊集

返回從v流出的邊的集合

get-neighbors(頂點 v): 頂點集

返回與v相連的頂點集

無向圖

一個無向圖。

在有向圖中，邊從一個頂點指向另一個頂點，而在無向圖中，邊只是連線兩個頂點。我們可以向前或向後移動。這是一個雙向圖。

加權圖

我們可能還想將一些成本或權重與邊的遍歷相關聯。當我們新增此資訊時，圖被稱為加權圖。一個加權圖的例子是國家首都之間的距離。

有向圖和無向圖都可以是加權圖。加權圖上的操作與在建立邊時新增權重引數相同

加權圖操作（無向/有向圖操作的擴充套件）

make-edge(頂點 u, 頂點 v, 權重 w): 邊

在u和v之間建立一條權重為w的邊。在有向圖中，邊將從u流向v。

圖表示

鄰接矩陣表示

鄰接矩陣是表示圖的兩種常見方式之一。鄰接矩陣顯示哪些節點是相鄰的。如果兩個節點之間有一條邊連線，則它們相鄰。在有向圖的情況下，如果節點$j$ 與節點 $i$ 相鄰，則從 $i$ 到 $j$ 存在一條邊。換句話說，如果$j$ 與 $i$ 相鄰，則可以透過遍歷一條邊從 $i$ 到達 $j$。對於一個具有 $n$ 個節點的圖，鄰接矩陣將具有 $n\times n$ 的維度。對於無權圖，鄰接矩陣將用布林值填充。

對於任何給定的節點 $i$，可以透過檢視鄰接矩陣的第 $\left(i,\left[1..n\right]\right)$ 行來確定其相鄰節點。在 $\left(i,j\right)$ 處的值為真表示從節點 $i$ 到節點 $j$ 存在一條邊，而假表示沒有邊。在無向圖中，$\left(i,j\right)$ 和 $\left(j,i\right)$ 的值將相等。在加權圖中，布林值將被連線兩個節點的邊的權重替換，並使用一個特殊值來指示邊不存在。

鄰接矩陣的記憶體使用量為 $O(n^{2})$。

鄰接表表示

鄰接表是圖的另一種常見表示。有很多方法可以實現這種鄰接表示。一種方法是讓圖維護一個列表的列表，其中第一個列表是對應於圖中每個節點的索引列表。每個索引都指向另一個列表，該列表儲存每個相鄰節點的索引。在該列表中，將每個連結的權重與相鄰節點相關聯可能也很有用。

示例：一個無向圖包含四個節點 1、2、3 和 4。1 與 2 和 3 相連。2 與 3 相連。3 與 4 相連。

1 - [2, 3]

2 - [1, 3]

3 - [1, 2, 4]

4 - [3]

將圖中所有節點的列表儲存在雜湊表中可能很有用。然後，鍵將對應於每個節點的索引，而值將是對相鄰節點索引列表的引用。

另一種實現可能需要每個節點都保留一個其相鄰節點的列表。

圖遍歷

在理想情況下，我們應該完全瞭解圖的內容，以便為頂點和邊最佳化索引，從而實現高效查詢。然而，在計算機科學中，存在許多開放式問題，索引在這些問題中是不切實際甚至不可能的。圖遍歷讓我們能夠解決這些問題。遍歷讓我們能夠高效地搜尋大型空間，其中物件透過它們與其他物件的關聯關係而不是物件本身的屬性來定義。

深度優先搜尋

從頂點 a 開始，訪問其鄰居 b，然後訪問 b 的鄰居 c，並持續進行，直到到達“死衚衕”。然後回溯，訪問從倒數第二個訪問的頂點可達的節點，並繼續應用相同的原則。

// Search in the subgraph for a node matching 'criteria'. Do not re-examine 
// nodes listed in 'visited' which have already been tested.
GraphNode depth_first_search(GraphNode node, Predicate criteria, VisitedSet visited) {
// Check that we haven't already visited this part of the graph
if (visited.contains(node)) {
 return null;
}
visited.insert(node);
// Test to see if this node satisfies the criteria
if (criteria.apply(node.value)) {
 return node;
}
// Search adjacent nodes for a match
for (adjacent in node.adjacentnodes()) {
 GraphNode ret = depth_first_search(adjacent, criteria, visited);
 if (ret != null) {
  return ret;
 }
}
// Give up - not in this part of the graph
return null;
}

廣度優先搜尋

廣度優先搜尋訪問節點的鄰居，然後訪問鄰居的未訪問鄰居，依此類推。如果它從頂點 a 開始，它將訪問所有從 a 有邊的頂點。如果某些點不可達，則需要從一個新的頂點開始另一個廣度優先搜尋。

---

資料結構
引言 - 漸進符號 - 陣列 - 列表結構 & 迭代器
棧 & 佇列 - 樹 - 最小 & 最大堆 - 圖
雜湊表 - 集合 - 權衡