# [資演] 14- 圖 (I): 圖簡介

###### tags: `資演`

一個圖 (graph) $G$，是一個由頂點 (vertex) 的集合 $V$ 與邊 (edge) 的集合 $E$ 所組成的資料結構，表示成 $G(V,E)$。


圖比樹更加廣義，其定義僅僅使用了集合(set)，並且不限制結構裡的node/vertex只能有唯一的parent，因此，更多的問題能夠以圖來建立模型。

## 圖的術語
* 頂點（vertex）
組成圖的最基本的元素。
* 邊（edge）
表示頂點和頂點之間的關係。
* 有向圖 (directed graph)
邊都具有方向性，也就是說，從$u$到$v$和從$v$到$u$是不同的。
* 無向圖 (undirected graph)
邊不具有方向性，兩點間為雙向關係。
* 鄰點（neighbors）
點$u$透過一條邊可以連結到的所有點，稱為點$u$的鄰點。
* 道路（walk）
一個walk是一個相互連接的點邊構成的序列。
參考上圖，$D \rightarrow B \rightarrow A \rightarrow C \rightarrow E \rightarrow D \rightarrow E \rightarrow C$ 就構成了一個walk。
* 跡（trail）
邊不重複（但頂點可能重複）的walk，稱為trail。
* 路徑（path）
除了起始點與終點外頂點皆不重複、邊也不重複的walk，稱為path。
* 環（cycle）
起始點和終點相同的path稱為一個cycle。
* 度（degree）
在無向圖中，對於一個點$u$，與該點直接連接的邊數量，稱為該點的degree。
* 入度（in-degree）
在有向圖中，對於一個點$u$，連到$u$的邊數量，稱為$u$的in-degree。
* 出度（out-degree）
在有向圖中，對於一個點$u$，從$u$指出去的邊數量，稱為$u$的out-degree。
* 權重（weight）
有時候我們會給邊帶上一個數字，稱為權重，用來表示例如兩個地點間的距離或運輸成本之類的額外資訊。
## 圖的表示方式
通常我們會用鄰接表 (adjacency list) 或鄰接矩陣 (adjacency matrix) 來儲存一個圖帶有的資訊。
### Adjacency List
先以一個一維陣列列出所有的vertex，再用一個list列出所有從vertex可以連結到的vertex。
### Adjacency Matrix
一個二維矩陣，若從第$i$個vertex到第$j$個vertex有邊，則矩陣位置$[i][j]$值為1，反之，則為0。若是有權重的圖，則矩陣位置$[i][j]$的值可以設成權重。無向圖的adjacancy matrix是對稱的。

## 圖的尋訪：DFS 和 BFS
如果我們想要從其中的一個節點開始，走訪到從該節點直接或是間接連接的其它所有節點，可以依靠**深度優先搜尋**（DFS, Depth-first Search）或是**廣度優先搜尋**（BFS, Breadth-first Search）來達成。
### DFS
先選定一個頂點開始走訪，接著從此頂點相鄰未被走過的頂點中，擇一走訪標示為記錄點，以此類推，不斷從新記錄點的相鄰未被走過頂點中尋找。
若新紀錄點的相鄰頂點都被走過，則退回前一個紀錄點，繼續從未被走過頂點中尋找。

深度優先可以利用堆疊(Stack)的方式來處理。


### BFS
先選定一個頂點開始走訪，逐一走過此頂點相鄰未被走過的頂點，若相鄰頂點都被走過，再從走訪過的頂點中擇一為新記錄點，逐一走過新記錄點相鄰未被走過的頂點，以此類推。

廣度優先可以利用佇列(Queue)的方式來處理。


### 在二元樹上的DFS和BFS
前面學過樹的尋訪有前、中、後序及層序尋訪這幾種。我們又能看出來，其實樹是一種特化的圖，因此樹的尋訪事實上只有 DFS 與 BFS 兩種：
* 前、中、後序屬於 DFS，只不過更動了節點的輸出順序
* 層序屬於 BFS

因此，我們也能夠使用stack和queue分別來實作二元樹的尋訪。（前面我們在實作前、中、後序是用遞迴，現在我們要用迴圈來做）

我們將一個二元樹定義如下：

class Node:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None

:::spoiler 用queue來實作層序尋訪/BFS

def printLevelOrder(root):
    # Base Case
    if root is None:
        return

    queue = [root]
 
    while queue:
 
        # Print front of queue and
        # remove it from queue
        node = queue.pop(0)
        print(node.data)
        
        # Enqueue left child
        if node.left:
            queue.append(node.left)
 
        # Enqueue right child
        if node.right:
            queue.append(node.right)
 

:::

:::spoiler 用stack來實作前、中、後序尋訪/DFS

def printPreOrder(root):
    if root is None:
        return

    stack = [root]

    while stack:
        node = stack.pop(-1)
        print(node.data)

        if node.left:
            stack.append(node.left)
 
        if node.right:
            stack.append(node.right)



def printInOrder(root):
    if root is None:
        return

    stack = [root]

    while stack:
        node = stack.pop(-1)

        if node.left:
            stack.append(node.left)
 
        print(node.data)

        if node.right:
            stack.append(node.right)

def printPostOrder(root):
    if root is None:
        return

    stack = [root]

    while stack:
        node = stack.pop(-1)

        if node.left:
            stack.append(node.left)

        if node.right:
            stack.append(node.right)

        print(node.data)

:::