Nail Your Next Job Interview - Graph

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
2
3
4
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < num; i++) {
adjList.add(new ArrayList<>);
}

Connected component

Leetcode 323. Number of Connected Components in an Undirected Graph

DFS + visited + adj list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Soluction {
public static int countComponents(int n, int[][] edges) {
if (edges.length == 0) return -1;

// create adj list
ListNode[] adj = new ListNode[n];
boolean[] visited = new boolean[n];
int res = 0;

for (int i = 0; i < n; i++) {
adj[i] = new ListNode(i);
}

for (int[] edge : edges) {
int x = edge[0];
int y = edge[1];
addToAdjList(adj, x, y);
addToAdjList(adj, y, x);
}

for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(visited, adj, i);
res++;
}
}

return res;
}

public static void addToAdjList(ListNode[] adj, int key, int n) {
ListNode node = adj[key];
while (node.next != null) {
node = node.next;
}
node.next = new ListNode(n);
}

public static void dfs(boolean[] visited, ListNode[] adj, int n) {
if (visited[n]) return;
visited[n] = true;

ListNode node = adj[n];
while (node.next != null) {
dfs(visited, adj, node.next.val);
node = node.next;
}
}
}

Union find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public static int countComponents2(int n, int[][] edges) {
// n = 5
// edges = [[0, 1], [1, 2], [3, 4]]

// 0 1 2 3 4
// roots[ 1, 2, -1, 4, -1]

int res = n;
int[] roots = new int[n];
for (int i = 0; i < n; i++) {
roots[i] = i;
}

// union
for (int[] edge : edges) {
int x = find(roots, edge[0]);
int y = find(roots, edge[1]);
if (x != y) {
// define root as edge[1], oppsite should also works
roots[x] = y;
res--;
}
}
return res;
}

/**
* find root of given node i.
* root defines as
* @param roots
* @param i
* @return
*/
private static int find(int[] roots, int i) {
while (roots[i] != i) {
i = roots[i];
}
return i;
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Queue<Integer> result = new LinkedList<>();
int[] inEdges = new int[numCourses];

while (!queue.isEmpty()) {
int n = queue.poll();
result.offer(n);
count++;
for (int i = 0; i < graph[n].size(); i++) {
// inEdges[i] -= 1;
int index = (int)graph[n].get(i);
inEdges[index] -= 1;
if (inEdges[index] == 0) { // when we has 0 in-edge, we can push it into queue
queue.offer(index);
}
}
}

// head of cycle will NOT be explored (not pushed into queue) since inEdge != 0, node in cycle will NOT be pushed into process queue
// numCourses > count
if (numCourses > count) {
// cycle detect
return new int[0];
}

207. Course Schedule

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {

int[] inEdges = new int[numCourses];
ArrayList[] graph = new ArrayList[numCourses];
Queue<Integer> queue = new LinkedList<>();
Queue<Integer> result = new LinkedList<>();

// initialize graph
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList();
}

// build graph & compute incoming edges
for (int[] edge : prerequisites) {
int startNode = edge[1];
int endNode = edge[0];

inEdges[endNode] += 1;
graph[startNode].add(endNode);
}

int count = 0;
// push node with 0 incoming edges into queue
for (int i = 0; i < inEdges.length; i++) {
if (inEdges[i] == 0) {
queue.offer(i);
}
}

// apply BFS topo sort algorithm
while (!queue.isEmpty()) {
int n = queue.poll();
result.offer(n);
count++;
for (int i = 0; i < graph[n].size(); i++) {
// inEdges[i] -= 1;
int index = (int)graph[n].get(i);
inEdges[index] -= 1;
if (inEdges[index] == 0) {
queue.offer(index);
}
}
}

// detect cycle
if (numCourses == count) {
return true;
} else {
return false;
}
}
}

210. Course Schedule II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] inEdges = new int[numCourses];
List<List<Integer>> graph = new ArrayList<List<Integer>>(numCourses);

Queue<Integer> queue = new LinkedList<>();
Queue<Integer> result = new LinkedList<>();

// initialize graph
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<Integer>());
}

// build graph & compute incoming edges
for (int[] edge : prerequisites) {
int startNode = edge[1];
int endNode = edge[0];

inEdges[endNode] += 1;
graph.get(startNode).add(endNode);
}

int count = 0;
// push node with 0 incoming edges into queue
for (int i = 0; i < inEdges.length; i++) {
if (inEdges[i] == 0) {
queue.offer(i);
}
}

// apply BFS topo sort algorithm
while (!queue.isEmpty()) {
int n = queue.poll();
result.offer(n);
count++;
for (Integer i : graph.get(n)) {
int index = (int)i;
inEdges[index] -= 1; // # of prerequisite for node [idx]
if (inEdges[index] == 0) { // prerequisite all finish
// queue.offer(i);
queue.offer(index);
}
}
}
// cycle will NOT be explored since inEdge != 0, node in cycle will NOT be pushed into process queue
// numCourses > count
if (numCourses > count) {
// cycle detect
return new int[0];
}

// normal output
int[] res = new int[result.size()];
int index = 0;
while (!result.isEmpty()) {
res[index++] = result.poll();
}
return res;
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:
Given the following words in dictionary,
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
The correct order is: "wertf".

Example 2:
Given the following words in dictionary,
[
"z",
"x"
]
The correct order is: "zx".
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public static String alienOrder(String[] words) {
if (words == null || words.length == 0) return "";

// initialze inEdge, adj list
Map<Character, Integer> inEdge = new HashMap<>();
List<List<Character>> adjList = new ArrayList<>();

for (int i = 0; i < 26; i++) {
adjList.add(new ArrayList<>());
}

// build graph and count inEdges
String pre = words[0];
for (int i = 1; i < words.length; i++) {
String cur = words[i];
for (int idx = 0; idx < pre.length() && idx < cur.length(); idx++) {
char start = pre.charAt(idx);
char end = cur.charAt(idx);
if (start == end) continue;

// add to adjList
adjList.get(start - 'a').add(end);
// add to inEdges
inEdge.putIfAbsent(start, 0);
inEdge.put(end, inEdge.getOrDefault(end, 0) + 1);
break;
}
pre = cur;
}
int totalCount = inEdge.keySet().size();

// topological sort
Deque<Character> q = new ArrayDeque<>();
for (Map.Entry<Character, Integer> entry : inEdge.entrySet()) {
if (entry.getValue() == 0) q.add(entry.getKey());
}

StringBuilder res = new StringBuilder();
while (!q.isEmpty()) {
char c = q.remove();
res.append(c);
for (char neighbor : adjList.get(c - 'a')) {
inEdge.put(neighbor, inEdge.get(neighbor) - 1);
if (inEdge.get(neighbor) == 0) {
q.offer(neighbor);
inEdge.remove(neighbor);
}
}
}

if (totalCount != res.length()) return ""; // cycle detected

return res.toString();
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
return cloneHelper(node, new HashMap<UndirectedGraphNode, UndirectedGraphNode>());
}

private static UndirectedGraphNode cloneHelper(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> clones) {
if (node == null) {
return node;
}

UndirectedGraphNode clone = clones.get(node);
if (clone != null) {
return clone;
}
clone = new UndirectedGraphNode(node.label);
clones.put(node, clone);
for (UndirectedGraphNode neighbor : node.neighbors) {
clone.neighbors.add(cloneHelper(neighbor, clones));
}
return clone;
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public UndirectedGraphNode cloneGraph2(UndirectedGraphNode node) {
if (node == null) return node;
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
Deque<UndirectedGraphNode> queue = new ArrayDeque<>();
queue.add(node);

UndirectedGraphNode graphCopy = new UndirectedGraphNode(node.label);
map.put(node, graphCopy);

while (!queue.isEmpty()) {
UndirectedGraphNode n = queue.remove();
UndirectedGraphNode clone = map.get(n);
for (UndirectedGraphNode neighbor : n.neighbors) {
UndirectedGraphNode copy = map.computeIfAbsent(neighbor, k -> { // k is key, equals to neighbor
queue.add(k);
return new UndirectedGraphNode(k.label);
});
clone.neighbors.add(copy);
}
}

return graphCopy;
}

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

434. Number of Islands II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/

public class Solution {
/**
* @param n: An integer
* @param m: An integer
* @param operators: an array of point
* @return: an integer array
*/
private static int islandCount = 0;
public List<Integer> numIslands2(int n, int m, Point[] operators) {
// write your code here
List<Integer> result = new ArrayList<>();
if (n == 1 && m == 1) {
return result;
}

int[] visited = new int[n * m];
Arrays.fill(visited, -1);

for (Point p : operators) {
int x = p.x;
int y = p.y;
int index = x * m + y;

// key2: duplicate ops ([[0,0],[0,1],[2,2],[2,2]])
if (visited[index] != -1) {
// operation already executed
result.add(islandCount);
continue;
}

visited[index] = index;
islandCount++;

// check neighbor
checkNeighbor(visited, p, n, m);
result.add(islandCount);
}
return result;
}

public static void checkNeighbor(int[] visited, Point p, int n, int m) {
findAndMerge(visited, p, p.x, p.y-1, n, m);
findAndMerge(visited, p, p.x, p.y+1, n, m);
findAndMerge(visited, p, p.x-1, p.y, n, m);
findAndMerge(visited, p, p.x+1, p.y, n, m);
}

// (x, y) is the neighbor for p
public static void findAndMerge(int[] visited, Point p, int x, int y, int n, int m) {

int neighborIdx = x * m + y;
int pIdx = p.x * m + p.y;

if (x < 0 || x > n - 1 || y < 0 || y > m - 1 || visited[neighborIdx] == -1) {
return;
}

int pRoot = findRoot(visited, pIdx);
int neighborRoot = findRoot(visited, neighborIdx);

// key1: when two group share different root, either make p OR q the new root
// so that two groups merge into one group
if (pRoot != neighborRoot) {
visited[pRoot] = neighborRoot;
islandCount--;
}
}

public static int findRoot(int[] visited, int neighbor) {
while (visited[neighbor] != neighbor) {
neighbor = visited[neighbor];
}
return neighbor;
}
}

Cycle Detection

For Directed Graph

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

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