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
   

   

   	a	b	c	d	e	f	g
   Step1	∞	∞	∞	∞	∞	∞	∞
   Step2	0	32	∞	∞	∞	3	∞

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

   

   	a	b	c	d	e	f	g
   Step1	∞	∞	∞	∞	∞	∞	∞
   Step2	0	32	∞	∞	∞	3	∞
   Step3	0	3 + 7	3 + 2	∞	∞	3	∞

4. Repeat 3 (i.e c node)
   

   

   	a	b	c	d	e	f	g
   Step1	∞	∞	∞	∞	∞	∞	∞
   Step2	0	32	∞	∞	∞	3	∞
   Step3	0	10	5	∞	∞	3	∞
   Step4	0	10	5	∞	5 + 6	3	5 + 11

5. Repeat 3 (i.e b node)
   

   

   	a	b	c	d	e	f	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)
   

   

   	a	b	c	d	e	f	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	11 + 13	11	3	16

7. Repeat 3 (i.e g node)
   

   

   	a	b	c	d	e	f	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	24	11	3	16
   Step7	0	10	5	24	11	3	16

8. Repeat 3 (i.e d node)

   	a	b	c	d	e	f	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	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 directed-graph.

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 5 –> 4 –> 2 –> 3 –> 1 –> 0

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 disc( c ) < low( g )
  

  

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});
            }
        }
    }
};