## Summary

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

## Graph Representation

• 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$

• 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

## 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

### 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.

## 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

### 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

## 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)

## Cycle Detection

### 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.
• 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

## 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