## Summary

- graph representation
- find connected component
- topological sort
- clone graph
- union-find algorithm
- cycle detection

## Graph Representation

**Adjacency matrix:**

- 2D array of size $V \times V$ where $V$ is the number of vertices in a graph.
- $adj[i][j]$ indicates there is an edge from vertex $i$ to vertex $j$
- Adj matrix for
**undirected graph**is always**symmetric** - Adj matrix can also be used to represent
**weighted****graph**, where $adj[i][j] = w$

1 | int[][] matrix = new int[num][num]; |

**Adjacency List**

- Array of linked-list
- Size of array equals to number of vertices
- $array[i]$ represents the linked list of vertices adjacent to the $i$ th vertex
- Adj list can also be used to represent a
**weighted graph**, which stored in node of linked list

1 | List<List<Integer>> adjList = new ArrayList<>(); |

## Connected component

### Leetcode 323. Number of Connected Components in an Undirected Graph

#### DFS + visited + adj list

1 | class Soluction { |

#### Union find

1 | class Solution { |

## Topological Sort

**Sorting**technique over**Directed Acyclic Graphs (DAG)**- Group w/ cycle has no topological sort
- common for ordering tasks and jobs

### Topological sort algorithm

- build graph (adj. matrix OR adj. array of list
`List[] graph`

) - compute incoming edges (
`int[] inEdges`

) - push nodes with 0 incoming edges into the
`queue`

- apply topological sort alogirhtm

1 | Queue<Integer> result = new LinkedList<>(); |

### 207. Course Schedule

1 | class Solution { |

### 210. Course Schedule II

1 | class Solution { |

### Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

1 | Example 1: |

1 | public static String alienOrder(String[] words) { |

## Clone Graph

- cycle should be considered
- remember cloned nodes stored in
`Map<UndirectedGraphNode, UndirectedGraphNode> clones`

### DFS

- Go all the way to left subtree, create nodes alone the way. add neighbors when recursive back

1 | /** |

### BFS

- bfs: create node if node has not been copied, each node got chance to be visited once to add its neighbors in a BFS manner
- O(n) extra space for queue

1 | public UndirectedGraphNode cloneGraph2(UndirectedGraphNode node) { |

## Union-Find (Disjoint Set) Algorithm

- Disjoint Set is a Data structure
- Unionf-Find uses two of the related methods on disjoint set data structure (
`find()`

and`union()`

), that is why union-find and disjoint set are sometimes interchangeable. **two steps**:`find`

and`union`

`find`

: find the root of current group`union`

: if two group does not share the same root, union them by making connection (`root1 -> root2`

)

https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

https://blog.csdn.net/cuit/article/details/78633729

### Applications

- detect cycle in an
**undirected**graph https://www.geeksforgeeks.org/union-find/ - count unique groups after some union operations (ex. number of island)

### 434. Number of Islands II

1 | /** |

## Cycle Detection

### For Directed Graph

- DFS/BFS
- topolocial sort (cycle detected
`if count != node.size()`

) - Three Color??: https://quip.com/-/blob/XBPAAAT9D5M/y0WE6WB0QbST0vOyo94HRw?s=E7FmAsFC3F2S&name=DetectCycle.java

### For Undirected Graph

- union find
- disjoint-set https://youtu.be/n_t0a_8H8VY?t=510
- makeset: create initial set
- findset: return root element represent of the set
- union: join two set

- DFS https://youtu.be/n_t0a_8H8VY?t=324
- start from any vertex, explore its neighbor (exclude where it came from)
- eg. u - v, when exploring
`v`

‘s neighbor, should exlude`u`

.

- eg. u - v, when exploring
- maintain visited set
- when visiting neighbor vertex, pass
`currNode`

as argument so neighbor know where predecessor comes from - for edge
`v - u`

from edge`v`

to`u`

, if`u`

already in`visited`

then cycle exsits

- start from any vertex, explore its neighbor (exclude where it came from)

src: https://www.geeksforgeeks.org/detect-cycle-undirected-graph/

## BFS vs DFS

- BFS: solution is not far from the root of the tree, less space efficient when tree is complete/balanced.
- DFS: more space efficient $O(logN)$ where complete balacned tree BFS has $O(N)$ space complexity

## Logs

- 06/02/2018: added topological sort & union find algorithm
- 08/16/2018: add alien dictionary for topological sort
- 09/07/2019: add more examples for cycle detection in graph