# [MIT QUIZ] Graph
好像很多dp問題都可以用graph解決
Edit distance
Square depth

發現很多graph題目都是改input
Type
0-1 BFS
1-2 BFS
Create 2 vertex
Alternate driving car (How I meet your midterm )
Changing Color
Road block
Star Power
Many-sink/source max-flow problem

有一種問題是把一個問題model成一個graph problem
word ladder
沒想到這種sequence similarity的題目可以用graph來model
Square Depth
A Vacation Home in Hawaii

:::success
# Number Of Paths From Source to Destination
:::
## DAGs Path - Number of path from s->t is odd/even

## ==Average Length in DAGs==
## Number of shortest path from s to t with unit distance in undirected graph
>跟 __Average Length in DAGs__ 可以比較
> 上題是求有多少條path
> 此題是求有多少條shortest path


:::success
# Advanced BFS
:::
## 0-1 BFS
### Solution 1 - Supernode
### [Solution 2](https://codeforces.com/blog/entry/22276) - dequeue
### 0-1 BFS example

## 1-2 BFS 
###### tags: 'dequeue'
:::info
### 其實如果weight不大都可以採用使手法 -$O(WV\log WV+WE)$
:::
>Ref:https://codeforces.com/blog/entry/22276

## SuperNode

:::success
# Change Transformation - Create A Copy Of Each Vertex
:::
:::info
Use Dijkstra as BLOCK-BOX
:::
## How I meet Your Midterm - Alternate Pass
## Shortest Path With ==Odd== Length
:::info
比較：__"[DAGs Path - Number of path from s->t is odd/even](https://hackmd.io/h1SAF0J5S-C5CvKc5IIYAA?view#DAGs-Path---Number-of-path-from-s-gtt-is-oddeven)"__
:::

## Changing Color - Different Color Edge, More 5 Cost
## Star Power! - Only 1 Free Weight At You Please
## Road Network - Only 1 Cross Block At You Please
## shortest path ==exactly== k vertex - ==$O(kE+kV \log kV)$==
:::danger
一個是at most => bellhman ford
一個是exactly => create copy of vertex
compare with [this](https://hackmd.io/NyokPtbmSUebzIZLSN5ZNQ?view#Smallest-cost-from-s-to-t-with-exactly-edge)
:::
:::info
比較 __"[[Bellman Ford]Shortest path with ~~exactly~~ ==at most== 𝑘 edges](https://hackmd.io/h1SAF0J5S-C5CvKc5IIYAA?view#Bellman-FordShortest-path-with-exactly-at-most-k-edges)"__
:::
### Not exactly
>最後要抓的東西必較多，ending node要全抓

## Traffic Planning

:::info
## 這種給定每個edge距離，又希望越早到的問題，通常的解法是 ==複製每一個node的個數。==
:::

## 重點
### 重點一：每一個vertex複製到 $T+1$ 份
ex:
1. 假設最多 $T$ 天要到目的地 => 每個node複製到有 $T+1$ 個
3. 希望有接下來 $k$ 小時會到 => 每個ndoe複製到有 $k+1$ 個
4. 希望剛好第 $m$ 天到 => 每個node複製到有 $m+1$ 個
>Take case 1 for example:
> ==$u$ => $u_{d}$ $\ \ d=0,1,2...T$==

### 重點二：同一個node間得edge?
1. 如果沒特別說 => 就由上到下把 __依序__ 同一個node裡面的node用 $weight=0$ 的edge連起來。
2. 如果說同一個地方不能待超過2天 => 同一個node裡面的node都不連起來

### 重點三：不同個node間的edge?

1. 給定一個函數$f(u,v,t)$説從 $u$ 到 $v$ 所需要花 $t$ 單位的時間 以及$g(u,v)$作為之間的距離 => ==add edge $(u_t,v_{t+f(u,v,t)})$ with weight = $g(u,v)$==

### 重點四：目標
>假設 $s$ 是起點， $t$ 是終點。

從$s_{0}$作為source做 Dijkstra

1. 越早到越好 => 從$t_{0},t_{1}...t_{T}$前面開始找第一個不為inifinity的為答案。
2. 只能在某個時間點剛好到 => $t_{T}$

## Traffic Planning - Optimization in two dimensions(Time, Distance)
## Traffic Planning - Optimization in one dimensions(Distance), but with Loose ++Time Constraint++


### Solution

可以看最後一個node的t=12是因為，不用像一樣找到最短時間
## Traffic Planning - exactly $m$ days with distance constriant

:::success
# Graph Model
:::
## Word Ladder - Graph Modeling

## [SpeedUp]Word Ladder

ref: https://www.programcreek.com/2012/12/leetcode-word-ladder/

### Use BFS and Save The Cost Of Construction Of Graph - $O(n^2m)$
##### Complexity

#### Key Point : Checking Valid Word = Check Adjacent Or Not
ref:https://www.geeksforgeeks.org/word-ladder-length-of-shortest-chain-to-reach-a-target-word/
## Square Depth - Graph Modeling
###### tags: `Dynamic Programming`

## A Vacation Home in Hawaii - Longest Path Modeling
### Similar peoblem
#### Solution in DP

是不是跟greedy algorithm中的 --- Interval Scheduling有關係啊？
## Heavy Hit

:::success
# Shortest Path - Change Edge's Weight
:::
## Linear Scale Up
## Quadratic Scale Up

:::success
# Modified Bellhamn
:::
## Equal in Relaxation => No shortrst Path Tree
### Shortrst Path Tree not exist but weight do
### Exapmple
## Not relaxed all edges at each iteration with the help of LEVEL build by BFS

:::success
# Modified Dijkstra with ==lower degree== graph
:::
:::info
## Lower Degree => ==$E=O(V)$==
:::
## Dijkstra Related – Insertion After Relaxation
### Why not Insertion Firstly?
###### tags: `relaxation`
>For __SpeedUp__
>Complexity depend on ==(# of vertex in the priority queue)==

#### 最近的K個點 = Extract-min K 次

### Lower Dijkstra complexity if degree of each vertex is limited - ==$O(V\log V)$==

原本把minimum edge weight理解成total的，後來才知道是單一的
假設有很多條path可以從s到t，我們會選
ref : https://www.quora.com/What-is-the-maximum-bottleneck-s-t-path-in-the-context-of-maximum-flow#
## SpeedUp using d-ary HEAP
### [SEE THIS FOR d-ary heap](https://hackmd.io/o5MDVxCtST24_F-7MCPwug#d-ary-HEAP)

:::success
# Cut Vertex(Articulation Point)
:::
###### tags: `Cut Vertex`
## Some property
### In undirected graph
#### leaf
cannot be a Articulation Point

#### root
only has one child cannot be Articulation Point

has more than one child can be Articulation Point

#### a non-leaf, non-root node
could be Articulation Point if not any back edge from a descendent to an ancestor in its DFS tree.

## How to check is connected ?
## Brute Forece Way to Find Articulation Point -==$O(V(V+E))$==
## Property
## Algorithm - ==low function== && ==discovery time== in DFS tree

:::success
# Cut Edge
## [SEE THIS](https://stellar.mit.edu/S/course/6/sp16/6.006/courseMaterial/topics/topic2/resource/pset4sols/pset4sols.pdf)
:::
###### tags: `Cut Edge`
##
## ==low function== && ==discovery time== in DFS tree
## 不太懂

## 在MINIMUNM SPANNING TREE中常用到

:::success
# Bottleneck Problem
:::
###### tags: `relaxation`
有分兩種
## ++Min-Max++ Bottleneck Problem
- __The ==Maximum== weight of any edge in P is ==Minimize== among all P__
### Dijkstra
#### Step 1 : Initialization
d[v] = infinity for v != s
d[s] = negative infinity;
#### Step 2 : Extract-==Min==
#### Step 3 : Relaxation
##### Version 1

def relaxtion(u,v,w):
    d[v] = min(d[v],max(d[u],w))

##### Version 2

def relaxtion(u,v,w):
    if d[v] > max(d[u],w):
        d[v] = max(d[u],w)
        pre[v] = u        


## ++Max-Min++ Bottleneck Problem
- __The ==Minimum== weight of any edge in P is ==Maximize== among all P__

### Dijkstra
#### Step 1 : Initialization
d[s] = infinity;
d[v] = negative infinity for v != s
#### Step 2 : Extract-==Max==
#### Step 3 : Relaxation
##### Version 1

def relaxtion(u,v,w):
    d[v] = max(d[v],min(d[u],w))

##### Version 2

def relaxtion(u,v,w):
    if d[v] < min(d[u],w):
        d[v] = min(d[u],w) 
        pre[v] = u        

## ==Max-Min== Bottleneck Problem
### Using Modifed Dijkstra Algorithm
>See Above

### Not Be Affected By Modifed Dijkstra Algorithm - O(VLogV+E)
>Note


###### tags: `Prim Algorithm`

### [Building Block]At Least Certain Edge Weight in Graph

### Using Binary Search with above Building Block - O(log(E)*(V+E))

> Notice How to apply binary search to ==Max-Min== Problem
> __==Min-Max==__ will be contray

###### tags: `Binary Search`

## [Similar Technique]Shortest Path with least edge
###### tags: `relaxation`
### ==Modified Relaxation==

Counting sort is efficient if K≅n.
:::success
# Edge Weight = (0,1], Find Maximum Product
:::
## Proabiliry Of ==EDGE== Droping Packet
## Proabiliry Of ==Vertex== Droping Packet

:::success
# Negative Weight
:::
## [Trick] Still Terminate!
## ==Exactly One Negative Weight==

:::success
# Two-way Shortest Path
:::
## Bi-directional shortest path using Dijkstra
### 終止條件：非相遇點, Counter-example。而是 ==$d_s[x]+d_t[x]$==
### Algorithm

## Find common vertex in the two different shortest path tree
## $V_c$ in shortest path <=> $d[s,V_c]+$==$d[V_c,t]$==$=d[s,t]$
step 1 : run 4 Dijkstra
- 1. run Dijkstra rooted at s
- 2. run Dijkstra rooted at u
- 3. run __reverse__ Dijkstra rooted at t
- 4. run __reverse__ Dijkstra rooted at v
>因為要算 ==$d[V_c,t]$== 所以才reverse

step 2 : iterate all vertex
## Can ==only== set one edge weight to 0, find shortest path
### [Method 2](https://hackmd.io/h1SAF0J5S-C5CvKc5IIYAA?both#Star-Power---Only-1-Free-Weight-At-You-Please)

## One-Way BFS vs Two-Way BFS

## Bi-directional BFS scenario

## Bi-directional BFS
> run two bfs
> - one with $G$
> - one with $G^T$

### Solution
>別忘了，還要跟原本的比較
#### Way 1 : Naive Way - ==$O(E^{'}(V+E))$==
#### Way 2 : Two-way BFS with one normal and one on transpose of original graph - ==$O(2(V+E)+E^{'})$==

## Want to stop at specific but don't want to add too mych cost

## ==Next== Minimum Shortest Path
:::success
Next : 第二小的
:::
###### tags: `modified Dijkstra`
### ==Notice how it modify Dijkstra==

### First shortest path跟 Next shortest path有兩種關係
#### Case 1 : 有部份重疊
當移掉first shortest path任一個edge就可以馬上找到next shortest path
#### Case 2 : 完全沒有重疊
要移掉first shortest path中沒有重疊的一段sub path中的任一個edge 才會找到next shortest path

__Case 2 example__


## ==Next== Minimum Shortest Path in DAG at ++each++ point

## Longest Path and each path with positive distance

:::success
# Edge Type
:::
### From Parent/Child View
### From Color View
## In UNDIRECTED graph, No cross edge / forward edge(=block edge)

------------

### 不是只有Parent /Child關係 => ==cross edge==

## Different Tree Edge when choosing Different vertex as source
:::info
### 不同的起始點選擇，會使得edge的性質變得不一樣
:::

## ==Singly Connected== - no cross/forward edge
### no need maintain $visited$ at each node when doing DFS

## ==Remove Back Edge <--> Acyclic==
## Number Of Cycles < Number Of Black Edge
## Remove Found ONE Back Edge doesn't mean only ONE edge
## Given a topological order, is there always a DFS traversal that produces such an order?

>從尾端做到頭部，每個DFS traversal tree都只有一個item

## Generation of ==ALL== cross edge and no ++tree edge++ by using DFS
> DFS 可以都沒有 tree edge
## If it's a tree, then no ==back==/cross/forward edge ==> no need $parent$ in DFS
:::danger
如果每個node只有一個incoming node的話，那可以不用紀錄node是否被visited過
:::

## Turn a mixed graph to a directed graph without bringing cycle
###### tags: `topological sort`

:::success
# Adjacent Matrix Multiplication
:::
## Square of Adjacent Matrix
### Solution

## [General Case]Only go ==5== edge at a time
## [More General Case]Transititve Clousure/Floyd–Warshall algorithm
###### tags: `Floyd–Warshall algorithm`,`Transititve Clousure`
### Transititve Clousure

:::success
# Belllman-Ford
:::
## Complexity - ==$|V|(\sum_{for\ all\ vertex}O(out-degree) )$==
### Adjacent Matrix - $|V|^3$
### Adjacent List - $|V||E|$
## In 2 different view
### Way 1 : Outer loop is ==|V|==, Inner loop is ==|E|==

### Way 2 : Outer loop is ==|V|-1==, Inner loop is ==|V|==


## Minimum Target = RoundTrip

:::success
# Dynamic Programming to Shortest Path
:::
## See [stanford slide](https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/18/Small18.pdf)
## Bellman-Ford Solved By DP in 2 Ways
## Floyd-Warshall Algorithm
### 看起來跟Bellhman Ford的dp形式很像，但其實有本質上的差異
#### Bellman Ford
- (o) increasing the number of edges in the path
#### Floyd-Warshall
- (x) increase the set of vertices we allow as intermediate
nodes in the path
## Belllman-Ford At Most ==K== edges

## [Bellman Ford]Shortest path with ~~exactly~~ ++at most++ $k$ edges
:::info
比較 __"[Pass through exactly k vertex](https://hackmd.io/h1SAF0J5S-C5CvKc5IIYAA?view#Pass-through-exactly-k-vertex )"__
:::
### number of subprobelm $O(kV)$
### Recurrsion of DP
### Complexity of each subproblem - $O(V)$
### Toal Complexity : $O(kE)$

## ==[??]== Short Path under Budget

## Pass through exactly k vertex
## ==[Concept]== 從vertex i 到 vertex j 且長度為k，有++幾種走法++？

:::success
# Maximum Length Of A Graph
:::
## Maximum Length DFS Could Pass

## Maximum Total Length Given Weight

:::success
# Cycle
:::

## Check for ==No Odd Cycles(Bipartite)==
### Solution

----

### ++Lemma : A graph does not contain odd cycles if and only if it is bipartite++
#### it is bipartite ==-->== A graph does not contain odd cycles
#### [比較難想]it is bipartite ==<--== A graph does not contain odd cycles
>用反證法 ：!（it is bipartite） ==-->== !（A graph does not contain odd cycles）


#### Note : Checking Bipartite = whether the graph is 2-colorable

----

## Can use Belllman-Ford to detect ==positive== cycle
>Belllman-Ford原本只能用來detect ==negative== __cycle__
>但可以透過negate weight的方式，來detect ==positive== cycle

## ==[??]== Given negative cycle, Label each vertex

## Negative Cycle - Arbitage
### Need an extra node as a start node, then add edge from start node to each other nodes
### Print all negative cycle

:::success
# Other Application/Property
:::
## Only 1 Shortest Distance, but not Shortest Path

## BFS Level


## Unversial Sink

## Minimum Vertex

## Diameter Of A GRAPH
### ==[??]==

## Dynamic Programming BFS/DFS

### Connected Component

## Better choice for dynamical graph : Adajacent Matrix

## 總是有方法可以把undirected變成DAG

## Triangle property

## ==[??]==
###
### 2009 q2

## Subproblem dependency graph

## DFS and Hamiltonian

## DFS is more deep than BFS

## No back edge in BFS doesn't mean acyclic

:::success
# Minimum Spanning Tree
:::
###### tags: `low degree`
## Each vertex with degree = 2
## Lightest and second lightest are in MST