# Graph Problem
## Dijkstra
Refer to :
> http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dijkstra.html

Find the minimum distance from a start node to any other nodes.

**Algorithm:**
1. Construct a hash map that record the minimum distance from a to others in the current step.

|| a | b| c |d | e | f | g |
|---- | -------- | -------- | -------- |-------- |-------- |-------- |-------- |
| Step1 | ∞| ∞ | ∞ |∞ |∞ |∞ |∞ |

2. Find the neighbors of a, and update the distance in the hash map

|| <font color='blue'>a</font> | b| c |d | e | f | g |
|---- | -------- | -------- | -------- |-------- |-------- |-------- |-------- |
| Step1 | ∞| ∞ | ∞ |∞ |∞ |∞ |∞ |
| Step2 |<font color='red'>0</font>| <font color='red'>32</font> | ∞ |∞ |∞ |<font color='red'>3</font> |∞ |

3. Search for the minimum distance in hash map that has not been visited yet.(i.e. **f node**)

|| <font color='blue'>a</font> | b| c |d | e | <font color='blue'>f</font> | g |
|---- | -------- | -------- | -------- |-------- |-------- |-------- |-------- |
| Step1 | ∞| ∞ | ∞ |∞ |∞ |∞ |∞ |
| Step2 |0| 32 | ∞ |∞ |∞ |3 |∞ |
| Step3 |0| <font color='red'>3 + 7</font> | <font color='red'>3 + 2</font> |∞ |∞ |3 |∞ |
4. Repeat 3 (i.e **c node**)
|| <font color='blue'>a</font> | b| <font color='blue'>c</font> |d | e | <font color='blue'>f</font> | g |
|---- | -------- | -------- | -------- |-------- |-------- |-------- |-------- |
| Step1 | ∞| ∞ | ∞ |∞ |∞ |∞ |∞ |
| Step2 |0| 32 | ∞ |∞ |∞ |3 |∞ |
| Step3 |0| 10 | 5 |∞ |∞ |3 |∞ |
| Step4 |0| 10 | 5 |∞ |<font color='red'>5 + 6</font> |3 |<font color='red'>5 + 11</font> |

5. Repeat 3 (i.e **b node**)
|| <font color='blue'>a</font> | <font color='blue'>b</font>| <font color='blue'>c</font> |d | e | <font color='blue'>f</font> | g |
|---- | -------- | -------- | -------- |-------- |-------- |-------- |-------- |
| Step1 | ∞| ∞ | ∞ |∞ |∞ |∞ |∞ |
| Step2 |0| 32 | ∞ |∞ |∞ |3 |∞ |
| Step3 |0| 10 | 5 |∞ |∞ |3 |∞ |
| Step4 |0| 10 | 5 |∞ |11 |3 |16 |
| Step5 |0| 10 | 5 |∞ |11 |3 |16 |

6. Repeat 3 (i.e **e node**)
|| <font color='blue'>a</font> | <font color='blue'>b</font>| <font color='blue'>c</font> |d |<font color='blue'>e</font> | <font color='blue'>f</font> | g |
|---- | -------- | -------- | -------- |-------- |-------- |-------- |-------- |
| Step1 | ∞| ∞ | ∞ |∞ |∞ |∞ |∞ |
| Step2 |0| 32 | ∞ |∞ |∞ |3 |∞ |
| Step3 |0| 10 | 5 |∞ |∞ |3 |∞ |
| Step4 |0| 10 | 5 |∞ |11 |3 |16 |
| Step5 |0| 10 | 5 |∞ |11 |3 |16 |
| Step6 |0| 10 | 5 |<font color='red'>11 + 13</font> |11 |3 |16 |
8. Repeat 3 (i.e **g node**)
|| <font color='blue'>a</font> | <font color='blue'>b</font>| <font color='blue'>c</font> |d |<font color='blue'>e</font> | <font color='blue'>f</font> | <font color='blue'>g</font> |
|---- | -------- | -------- | -------- |-------- |-------- |-------- |-------- |
| Step1 | ∞| ∞ | ∞ |∞ |∞ |∞ |∞ |
| Step2 |0| 32 | ∞ |∞ |∞ |3 |∞ |
| Step3 |0| 10 | 5 |∞ |∞ |3 |∞ |
| Step4 |0| 10 | 5 |∞ |11 |3 |16 |
| Step5 |0| 10 | 5 |∞ |11 |3 |16 |
| Step6 |0| 10 | 5 |24 |11 |3 |16 |
| Step7 |0| 10 | 5 |24 |11 |3 |16 |

9. Repeat 3 (i.e **d node**)
|| <font color='blue'>a</font> | <font color='blue'>b</font>| <font color='blue'>c</font> |<font color='blue'>d</font> |<font color='blue'>e</font> | <font color='blue'>f</font> | <font color='blue'>g</font> |
|---- | -------- | -------- | -------- |-------- |-------- |-------- |-------- |
| Step1 | ∞| ∞ | ∞ |∞ |∞ |∞ |∞ |
| Step2 |0| 32 | ∞ |∞ |∞ |3 |∞ |
| Step3 |0| 10 | 5 |∞ |∞ |3 |∞ |
| Step4 |0| 10 | 5 |∞ |11 |3 |16 |
| Step5 |0| 10 | 5 |∞ |11 |3 |16 |
| Step6 |0| 10 | 5 |24 |11 |3 |16 |
| Step7 |0| 10 | 5 |24 |11 |3 |16 |
| Step8 |0| 10 | 5 |24 |11 |3 |16 |
---

## Union Find
https://leetcode.com/problems/sentence-similarity-ii/
We can generally divide this algorithm into 2 part --> **"Unoin" and "Find"**
* **Union**
Connect the undirected edge of the graph
* **Find**
Check whether two nodes is in the same set by checking whether they have identical root nodes.

## Topological Sort
This kind if sort can only be used on <span style="color:red">**directed-graph**</span>.

1. We should firstly use a **Hash Map** to record the edges of the graph.
2. Use an **array** to record whether the node has been visited.
3. Use a **Stack** to sort the graph

Please refer to below figure:

* **Step 1**
In this step, 0 has been considered. Since there is no other node that 0 points to, we directly save 0 into stack and mark 0 as visited.

* **Step 2**
1 has benn considered. Same as Step 1.

* **Step 3**
2 has been considered. Since there is a 3 that 2 points to, **we go to 3 and see whether there is a node that 3 points to**. Since 1 has been visited, we put 3 into stack then put 2 into stack.

* **Step 4**
4 has been considered. Since 0 and 1 have been visited. Directly put 4 into stack.

* **Step 5**

* **Step 6**
Pop out all elements in stack. That is <span style="color:red">**5 --> 4 --> 2 --> 3 --> 1 --> 0**</span>

## Bridge-finding algorithm
A bridge is the edge that will make the graph disconnected if it is removed. (As below)

### Example

* **Step 1**
Perform DFS that give each node a **order** and give each edge a **direction**.

* **Step 2**
Find the lowest order the current node can reach via the **directed graph** you make in the step1.

* **Step 3**
**For edge(c -> h), if disc( c ) < low( h )**, then we call edge(c, h) is a bridge.
In this example, since only edge(c, g)'s holds the cindition <font color='red'> **disc( c ) < low( g )** </font>

### Practice

### Solution

### Code Example --> LeetCode: **Critical connection in networks**

class Solution {
    vector<vector<int>> graph, ret;
    // create 2 array to record the essential information
    vector<int> disc, low;
    int time = 0;
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        //initialize the to record array
        disc = vector<int>(n);
        low = vector<int>(n);
        // make the graph contain n node
        graph.resize(n);
        for(auto c : connections)
        {
            // undirected graph
            graph[c[0]].push_back(c[1]);
            graph[c[1]].push_back(c[0]);
        }
        dfs(0, -1);
        return ret;
    }
    void dfs(int cur, int pre)
    {
        // the node has been travel before
        if(disc[cur] > 0) 
            return;
        // firstly set low and discovery time the same value
        disc[cur] = low[cur] = ++time;
        // search the connection of current node
        for(int next : graph[cur])
        {
            // Very important instruction --> to make an directed graph
            if(next == pre) continue;
            dfs(next, cur);
            // save the minimum low that the current node points to 
            low[cur] = min(low[cur], low[next]);
            // check whether it is a bridge
            if(low[next] > disc[cur])
            {
                ret.push_back({cur, next});
            }
        }
    }
};