Graph Note

How to represent a graph?

1. adjacent matric

class Graph {
    boolean[][] adjacentMatrix;
}

class Graph {
    Weight[][] adjacentMatric;
}

Space: O(|V|^2) Pros: Lookup edge for a certain pair - O(1) Cons: Possible sparse matrix if |E| << |V|

2. Adjacent List

class Vertex {
    int id;
    List<Vertex> neighbors;
}

class Graph {
    List<Vertex> vertices;
}

Pros: space: O(|V| + |E|) Cons: Time complexity is O(v) to check whether there is an edge from a node to the other.

Some common scenarios:

1. Using integers to denote each of the nodes in the graph.

Map<Integer, List/Set<Integer>>
     vertex    adjacent list(edges)

Map<Integer, Map<Integer, Integer>>
     vertex    neighbor, weight 

Connected Graph

A graph is connected only if it meets the requirement: From any vertex vi, there exists a path from vi to any other vertex vj in the graph.

It does not related to whether the graph is directed or not

Tips: A connected graph can be represented by one of the the nodes in graph.

How would you do DFS from graph

Marking visited method 1

• mark visited when first time entering the node
• try to mark visited the node before all its decendants.

Mark the node as visited when first time entering the node.

enum State {
	UNVISITED, VISITED;
}

class Vertex {
	State state = UNVISITED;
	List<Vertex> neighbors;
}

void dfs(Vertex v) {
	if (v.state == VISITED) return;

	v.state = VISITED; // first time entering the node
	for (Vertex n : v.neighbors) {
		dfs(n);
	}
}

• Time: O(|V| + |E|)
• 每个node只会被visited一次 《＝》每个node只会被expand一次O（｜V｜）
• 在expand一个node的时候，从这个node出发的所有edge都被generate一次 => 总共generate的次数 ＝＝ edge的总数 O（｜E｜）
• 每个node可能被generate多次，但是只有第一次有效（mark visited），并且会继续从这个node expand

Mark Visited Method 2

Starting N1, after visited all the nodes reachable from N1, then we mark N1 visited once and only once.

• Only after visited all the reachable nodes from n, we can make n visited
• we need some additional state for each node in "visiting": a special marker of the nodes on the current DFS path to avoid duplicately visiting nodes.

unvisited
visiting
visited

class Vertex {
    State state = UNVISITED;
    List<Vertex> neighbors;
}

enum State {
	UNVISITED, VISITING, VISITED;
}

void travers(Vertex v) {
	dfs(v);
}

void dfs(Vertex v) {
	if (v.state == VISITED) return;
    if (v.state == VISITING) return; // there is a cycle.

	v.state = VISITING; // first time entering the node
	for (Vertex n : v.neighbors) {
		dfs(n);
	}
	v.state = VISITED
}

Time: O(|V| + |E|) - polynomial at most |V|^2.

• for each node, only do dfs once and only once.
• for each edge, only do dfs once and only once.

In what scenario, we will need method 2 instead of method 1?

• We would like to follow the order of mark the node visited last.
• We would like to know if there is any cycle in the graph. If we don't care about distinguishing the cycle, we can use method 1.

Three Categories of typical graphs

                                       Mark Visited 1                     Mark Visited 2

Tree                       do not need to mark visit at all: XXX               XXX

DAG                                    necessary                             not need visiting

Graph possibly with cycle           OK (can not detect cycle)                OK(can detect cycle)

One last thing: Starting from one node x, DFS can only help you traverse all the nodes reachable from x.

So, what we need to do:

class Graph {
	List<Vertex> vertices;
}

void traverse(Graph graph) {
	for (Vertex v : graph.vertices) {
		if v is not visited -> there is new (weak) connected compontent.
	    dfs(v); // method 1 & method 2 both applicable
	}
}

Comparing to DFS on Binary Tree (a special kind of graph)

• Why we don't need to mark visited in this case?

Because for each node in the tree, there is <= 1 incoming edges, there is no alternate paths reaching the node, in another word, during DFS, there is only one way to reach the node so that marking visited is unnecessary.

Mark visited method 3 (O(# of paths))

We care about the path, instead of if the vertex is reachable in this case.

• find all possible paths from the start node, on the path there is no duplicate vertices.
• 这个mark visited只是mark在当前DFS path上的node。 为了保证，在当前这条DFS路径上没有cycle*

enum State {
	UNVISITED, VISITED;
}

class Vertex {
	List<Vertex> neighbors;
	State state = State.UNVISITED;
}

void allPaths(Vertex v) {
	if (v.state == VISITED) return;

	v.state = VISITED;
	for (Vertex n : v.neighbors) {
		allPaths(n);
	}

	v.stae = UNVISITED;
}

                                     Mark Visited                  Mark Visited 1,2
Tree                       no need (reason: no cycle), O(n)          O(n) = O(|V| + |E|) : **|E| = |V| - 1**
DAG                        no need (reason: no cycle). worst O(b^V)   O(|E| + |V|)
Graph with cycle              necessary, worst O(b^|V|)               O(|E| + |V|)
b = branching factor

Classic Questions

1. Two int arrays with same length, how to get the dot product?

1.1 If the array is very long, but most of elements in the arrays are 0. How to improve it?

(Answer: Two lists of Pairs (index, value). Move them together)

Time: O(# of non-zero elemets in both of the two arrays)

1.2 What if one of the array has very samll number of non-zeros, the other one has a lot of non-zeros? Two lists with size n1, n2, where n1 >> n2.

(Answer: binary search. O(n2 * logn1))