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

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