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

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

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