Graphs

Graph’s Representation:

To solve graph problems, we should firstly understand how to store. We also need to figure out that in what data structure we store the graph will help us solve the problem. The first step to solve graph problem is to properly store the graph in a correct data structure. Generally, there are four ways to represent graphs. Each with its advantages and disadvantages.

• Nodes as objects and edges as pointers.

Most problems about (binary) trees usually use this pattern.

Time complexity: O(V)

Memory complexity: O(V)

• A list of edges represented by two nodes.

For Example,

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]

Graph problems in general are likely use this pattern. Sometimes, we would like to convert it to an adjacent list.

Time complexity: O(E)

Memory complexity: O(E)

• Adjacency lists

Representing a graph with adjacency lists combines adjacency matrices with edge lists.

Time complexity: O(Deg(V))

Memory complexity: O(V∗Deg(V))

• Adjacency Matrices

from node in column to node in row, if there is an edge, represent by 1 or not by 0.

Time complexity: O(1)

Memory complexity: O(V2)

Reference

[1] KHANACADEMY