# Graph
## path
- a sequence P of nodes v1, v2, ..., vk-1, vk with the property that each consecutive pair vi, vi+1 is joined by an edge in E.
- simple: path上沒有重複走過的點(distinct)
- cycle: path至少多於2個點，頭尾相連，中間的點distinct
- connected: 如果任意點到任意點之間都有path，則graph is connected
- distance: minimum number of edges in a u-v path
## tree
- An undirected graph is a tree if it is **connected** and does **not contain a cycle**
- G若滿足兩個條件即為樹:
- G is connected.
- G does not contain a cycle.
- G has n-1 edges.
- rooted tree: a tree with its root at r
## BFS
- 從s(source)開始一層一層往外擴散直到visit所有可到達的點
- Layer ${L_i}$: i is the time that a node is reached.
- $L_0$ = {s}
- $L_{j+1}$ = $L_{j}$的鄰居中不屬於更上層layer的node
- i: 從s到$L_{i}$的distance
- BFS Tree:
- tree edge v.s. non tree edge
- 一棵BFS tree中，若x屬於$L_{i}$，y屬於$L_{j}$，且(x,y)有edge連接(不一定是tree edge)，則i跟j最多差1
- proof(by contradiction):
1. 不失一般性，假設j>i，且j-i>1
2. 根據定義，x屬於$L_{i}$，則x的鄰居不是屬於$L_{i+1}$就是屬於更上層的layer
3. 因為(x,y)有edge連接，(x,y)必互為鄰居，且y屬於$L_{j}{\ }{\rightarrow}$ j ≤ i+1。
4. ${\rightarrow}{\leftarrow}$
- non tree edge: 跟自己同層(兄弟姊妹)或是差一層但不是父母(叔叔姪子...)


## DFS
- 從s開始一直走，直到走到dead end，再回頭換別條路
- 
- 一條edge會被檢查兩次(去跟回)
- DFS tree
- tree edge必連接爸爸跟小孩，non tree edge必連接祖先子孫(跨層)
- 一棵DFS tree中，若(x,y)之間為non tree edge，則x, y為祖先子孫關係
- proof:
- 不失一般性，假設x先被看到
- (x,y)為non tree edge表示x看y時y已經被explored
- 但是在剛看到x時y還沒explored ${\rightarrow}$ y是在剛呼叫DFS(x)跟DFS(x)的遞迴完全結束的過程中被發現的
- y必存在由x往下的tree之中 ${\rightarrow}$ y為x的子孫
## connected component
- A connected component containing s is the set of nodes that are **reachable** from s.
- 通常取到最大
- 
- 
- Correctness:
- 所有R裡面的node都reachable from s
- 課本
- 所有不屬於R的node都unreachable from s
- 反證法
## Implementation
- Graph representing
- A graph G(V,E):
- |V| = the number of nodes = n
- |E| = the number of edges = m
- n – 1 (lower bound of edges, tree) ≤ m ≤ ${\binom{n}{2}}$ (upper bound of edges) ≤ n² for a connected graph
- O(n) v.s O(n²)
- Linear time (O(m+n)):
- adjacency matrix:
- graph G = (V, E) with n nodes, V = {1, ..., n}
- adjacency matrix of G is an nxn martix A where
- A[u, v] = 1 if (u, v) ${\in}$ E;
- A[u, v] = 0, otherwise.
- time
- O(1): check if (u, v) ${\in}$ E
- O(n): 找出任一點的所有鄰居(掃過row跟column)
- visit many 0 for sparse graph
- space
- O(n²)
- adjacency list:
- adjacency list of G is an array Adj[] of n lists, one for each node represents its neighbors
- Adj[u] = a linked list of {v | (u, v) ${\in}$ E}.
- degree of u: u有多少鄰居
- time:
- O(deg(u)) time for checking one edge or all neighbors of a node.
- space:
- undirected: n+2m ${\rightarrow}$O(n+m)
- directed: n+m ${\rightarrow}$O(n+m)
- indegree and outdegree for directed graph
- Implementing BFS
- 
- Implementing DFS
- 
- Summary
- 
## Testing Bipartiteness
- bipartite graph (bigraph): a graph whose nodes can be partitioned into sets X and Y in such a way that every edge has one one end in X and the other end in Y.
- X and Y are two disjoint sets
- No two nodes within the same set are adjacent
- node可分成兩個group，group內的node不相連，所有edge的兩端必落在不同group
- Check if bipartite: Color the nodes with blue and red (two-coloring)
- If a graph G is bipartite, then it cannot contain an odd cycle.
- 
- Procejure
1. 假設G=(V,E)是connected
- 若不是，不同的connected component分開執行
2. 選一個任意起始點s塗成紅色
3. 把s的鄰居塗成藍色
4. 重複塗色直到整張圖都塗完顏色
5. Test bipartiteness: 所有edge兩端都是不同顏色
- 如果欲塗色的點已經被塗色而且其顏色跟欲塗的顏色不同，則不是bipartite graph
- 可用BFS實作
- time: O(m+n)
- 在最後加上著色的動作
- 
- Correctness
- 2 case:
1. 沒有連接同層間node(兄弟姊妹)的edge${\rightarrow}$bipartite
2. 有連接同層間node(兄弟姊妹)的edge${\rightarrow}$有odd cycle${\rightarrow}$not bipartite
- BFS特性: Let x${\in}$L_i, y${\in}$L_j, and (x, y) ${\in}$E. Then i and j differ by at most 1.
- edge兩端的layer差必小於等於1
- proof case 2:
1. 假設(x,y)是兩端皆在同個layer L_j的edge
2. z = lca(x, y) = lowest common ancestor
- x跟y往上層layer看時最早的共同祖先
- 
3. Let L_i be the layer containing z
4. 考慮經過x,y,z及(x,y)的cycle
5. 長度為1+2(j-i)，為奇數

## Connectivity in Directed Graphs
- **directed** graph: **asymmetric** relationships
- Representation: Adjacency list
- Each node is associated with two lists, to which and from which
- mutually reachable: 對node u跟v，有從u到v的path，也有從v到u的path
- strongly connected: every pair of nodes are mutually reachable
- Lemma: If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable.
- 
- determine strongly connectivity in linear time
1. 選擇graph G中的任意起始點s
2. R = BFS(s, G)
3. R^rev = BFS(s, G^rev)
- 因為要雙向都有path可到達對方，把G的edge方向全部反轉再做一次，就可以知道是否有反向的path連結
4. 如果(R = V = R^rev)則為strongly connected
- time: O(m+n)
- Strong Component
- strong component containing s in a directed graph is the maximal set of all v s.t. s and v are mutually reachable.
- Theorem: For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.
- directed graph中的任意兩點，不是在同個strong component就是在不同的strong component
- proof:
- Identical if s and t are mutually reachable
- Disjoint if s and t are not mutually reachable
## Directed Acyclic Graphs (DAG)
- an undirected graph has no cycles: tree (or forest)
- DAG: directed graph without cycles
## Topological Ordering
- Given a directed graph G, a topological ordering is an ordering of its nodes as v1, v2, ..., vn so that for every edge (vi, vj), we have i<j.
- node可以照順序排好，排好後edge的方向都相同
- 

- Precedence constraints: edge (vi, vj) means vi must precede vj
- Lemma: If G has a topological ordering, then G is a DAG.
- If G is a DAG, then does G have a topological ordering?
- yes
- proof by contradiction:
- assume graph has cycle
- Lemma: In every DAG G, there is a node with no incoming edges.
- proof by contradiction:
1. 假設某DAG中每一點都有incoming edge
2. 任選一點v，挑一條他的incoming edge往回走
3. 因為每個點都有incoming edge，此動作可以一直重複，沒有上限
4. 重複n+1次後，因為只有n個點，我們必會走到重複的點上
5. C為兩次走到重複點w之間走過的點，C是cycle${\rightarrow}$矛盾
- 
- 
- Lemma: If G is a DAG, then G has a topological ordering.
- proof by induction
1. base case: n=1時成立(只有一個點，直接編號1號)
2. inductive step:
- 假設n個點時成立: n個點的DAG有topological ordering
- 對於一個有n+1點的DAG，把一個沒有incoming edge的點分出來
- 
- 拿掉一個點及其連接的edge並不會創造cycle ${\rightarrow}$ G – {v}是有n個點的DAG
- 根據假設，有n個點的DAG有topological ordering
- 把v放在topological ordering的最前端是安全的(不會有cycle)
- ${\rightarrow}$ G也有topological ordering
- Linear-Time Algorithm
- 
- time
- O(n²): n個點執行n次函式，每次執行函式第1行找沒有incoming edge的點要掃過{n, n-1, n-2 ...}個點
- O(m+n):
- Initialization: 建立adjacency list及紀錄indeg，把沒有incoming edge的點放到S
- indeg(w) = # of incoming edges from undeleted nodes
- S = set of nodes without incoming edges from undeleted nodes
- O(m+n)
- 原算法的line 3改為：
1. Remove v from S
2. 把所有從v連到w的indeg(w)減1，如果indeg(w)為0把w放進S
- 單獨動作皆為O(1)
- 這步會做m次(m條edge)
- O(m+n)
- line 4改為check S