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