4. Coding a Graph #
Created Monday 30 March 2020
- Note: Consider |V| << |E|. Vertices are less.|E| ~ |V|^2^
There are 3 types of implementations:
- Edge List
We can save all the vertices in a vector. Edges are stored as 2-tuples of neighbours(vertices).
- V = {v1, v2, v3 …}
- E = {(v1,v2), (v2, v3),…}
- This is very slow, even checking if A and B are neighbours, requires a linear search of the edge list i.e ~nC2 searches = O(n^2^) = O(E)
- Space is O(E)
- Definitely not good.
- Adjacency List
Store a list of vertex. Also, store a table containing vertiex-{neighbours of vertex}. Neighbours are a vector of the neigbhouring vertices. This is very nice.
- V = {v1, v2, v3 …}
- E = An array of neighbour lists for each vertex.
- Checking A is a neigbour of B is O(V) for a children array, or we can use a hashmap O(1) whp.
- It is space efficient - takes into account sparsity of the graph.
- Really fast.
- But difficult to implement.
- Adjacency Matrix
We don’t need to store the vertices seperately. Both V, E are stored in the same structure.
- We’ll make a square matrix(i.e 2D array) of size |V|*|V| with each element storing true or false or number of edges(for multigraphs), corresponding to the value of isNeighbour(A,B).
- The fastest - O(1). Just access G[A][B] for checking if A and B are neighbours.
- The most space inefficient. Any graph occupies the same space as a complete graph.
- Bad for sparse graphs. i.e where edges ~ V. Very few trues and many falses.
Verdict: Adjacency matrix is faster than Adjacency list. We use it if we have no space constraint. We use a list when space is scarce. Generally matrices are used for competitions, where speed matters.
We will be using adjacency matrix as it is the most easy to implement.
Note: The representations discussed are applicable for all types of graphs - directed, undirected, multi, self-loop etc.