Chapter 3 -- Graph ( 2 )

發表於 更新於 分類於 ， 閱讀次數： Disqus：

Representing Graph

$G=(V,E)$ is a graph

  • $\mid V\mid=$ the number of nodes $\overset{let}{=} n$
    $\mid E\mid=$ the number of edges $\overset{let}{=} m$
    $\Longrightarrow n-1\leq m\leq \displaystyle{\binom{n}{r}} \leq n^2$
    $\Longrightarrow$ 我們會希望整個複雜度可以控制在 $O(m+n)$

Adjacency Matrix

The $adjacency\ matrix$ of $G$ 是一個 $n\times n$ 矩陣 $A$
$$
A=\begin{bmatrix}a_{11}a_{12}\cdots a_{1n}\a_{21}a_{22}\cdots a_{2n}\\vdots\a_{n1}a_{n2}\cdots a_{nn}\end{bmatrix}
$$

  • $a_{ij}=1$ , if $(i,j)\in E$
  • $a_{ij}=0$ , if $(i,j)\not\in E$
  • If $G$ is undirected graph, then $A$ is symmetric.
  • The time complexity for checking if $(i,j)\in E=O(1)$
    ( 我們只要找第 $i$ 列第 $j$ 行即可知道是否存在 $(i,j)$ )
  • The time complexity for finding out all neighbors of $i\in V=O(n)$
    ( 需要遍歷第 $i$ 行(列)，才能找出所有 neighbors )
  • The space complexity $=O(n^2)$

我們可以從這個矩陣中 0 的數量跟密集程度來看看這是 Sparse Graph 還是 Dense Graph，如果今天是一個 Sparse Graph，其矩陣也是 Sparse，那麼相當於我們必須利用許多的空間來儲存 0 這樣無意義的資料，由此我們可以知道， 使用 adjacency matrix 來表示 Sparse Graph 是不太適合的。

Adjacency List

$Adjacency\ List$ 中我們會先以一個 array 儲存每一個 vertex，之後再用 Linked List 來表示 vertex 與 vertex 之間的相鄰關係。

$$
Adj[i]={j\mid (i,j)\in E}\
\mid Adj[i]\mid=degree(i)=deg(i)=the\ number\ of\ neighbors\ of\ i
$$

  • The time complexity for checking if $(i,j)\in E=O(n)$
    ( the worse case 就是要遍歷完整串 Linked List 才會確認兩者是否存在 edge )
  • The space complexity $=O(n+m)$
  • in-degree : 指的就是指向自己的 edge 數
    out-degree : 指的就是指向別人的 edge 數


( Adjacency Mtrix v.s. Adjacency List，圖片來源 : Graph: Intro(簡介) )

Implementation

在介紹 BFS 與 DFS 的 implementation 之前，我們要先了解所使用的資料結構 : Queue and Stack

Queue

Queue 我們可以看作是一個水管，資料進出的型態是 「先進先出」 (First in, First out. FIFO)，而這樣的資料結構伴隨兩個 Pointer : front 以及 rear，這兩個指標分別指出目前資料的頭尾，其實也是指出接下來要輸出、輸入的資料位置。

Stack

而 Stack 比較像是一個水瓶，資料型態則是 「後進先出」 (Last in, First out. LIFO)，值得注意的是，在 Stack 這樣的資料型態中，我們只需要一個 Pointer : Top ，用來指出最後進來的資料是誰，也相當於指出接下來要輸出的資料是哪一筆。

不論是 Queue 還是 Stack，我們都可以利用 Linked List 來進行 implement。

Implementing BFS

在要進行 BFS 的 implementation 以前，我們得先決定 Garaph representation，在 BFS 裡面我們使用的是 Adjacency List 來表現一個 Graph，其原因是 Adjacency List 的儲存方式跟 BFS 的搜索方式是吻合的，如此一來可以有效降低 Complexity。

1
2
3
// T is a BFS tree rooted s
// Layers count i
// L[i] is Layer_list
1
2
3
4
5
6
7
8
9
10
11
BFS(s)
1. init i=0, L[0]={s}, T={} and mark[s]=True, marked[others] are False
# 設定各項初始值
2. while L[i] is not empty then L[i+1]={}
       for each u in L[i] 
           for each (u,v) in E :
               if marked[v] = false then
                   marked[v] = true
                   T = T + {(u,v)}
                   L[i+1] = L[i+1] + {v}
       i+=1

  • 對於 $L[i]$ ，我們應該要用什麼資料結構來處理 ?
    事實上，Queue / Stack 均可，這兩者差異在於資料處理的順序，但在 BFS 中，每個 Layer 內部的順序性並非那麼重要。( 但若我們今天只想要用一條 List 儲存所有的 Layer 那就必須使用 Queue，因為層與層之間的順序性必須被考慮進去。 )

  • Time Complexity : $O(m+n)$
    在 BFS 的過程中，每一個 Vertex 都必須 check 每一個 neighbor，如果我們選用的是 Adjacency List ，便可把複雜度控制在 $O(m+n)$ 之中。

但倘若我們選擇的是 Adjacency Matrix，則複雜度會趨近於 $n^2$ 。

Implementing DFS

之前我們給的 DFS 是一個 recursive code，也可以將其譯為一個 iterative 的版本。

這裡我們使用的是 stack 的型態來處理 vertex set S。

1
// S is a stack of vertice its neighbors haven't been marked entirely.
1
2
3
4
5
6
7
8
DFS(s)
1. init S={s}
2. while S is not empty then
       remove a vertex u from S
       if marked[u] = false then
           marked[u] = true
           for each (u,v) in E 
               S+={v}
  • iterative code 使用的是 stack 形式做處理，而 recursive code 其實也是 stack，因為 recursive 本身就是一個 stack 形式。
  • Time Complexity : $O(m+n)$ …. Adjacency List

Summary

Adjacency matrix VS. Adjacency list for graph

Scenario Choice Complexity
Find an edge Adjacency matrix $O(1)$
Find degree Adjacency list $<O(n)$
Traverse the graph Adjacency list $O(m+n)$
Storage for sparse graph Adjacency list $<O(n^2)$
Storage for dense graph Adjacency matrix $O(n^2)$
Edge insertion/deletion Adjacency matrix $O(1)$
Most application Adjacency list -

Graph traversal

  • Data structure of BFS : queue / stack
  • Data structure of DFS : stack
  • Implementation of BFS/DFS with Adjacency list : $O(n+m)$