Graph basics and representation

Graph is a data structure which consists a set of vertices which is called as Node, together with a set of collection of pair of vertices which is called as an Edge. A graph data structure can be represented as a pair (V, E) where V is a set of nodes called vertices and E is a collection of pairs of vertices called edges. Graphs are used to solve many real life problems such as fastest wasy to go from A to B etc.

Graph Representation

Following methods are most commonly used in graphs representation:

Adjacency Matrix

struct Graph {
    int V;
    int E;
    int** edges;
};

In this method we save number of nodes present in Graph (V), Total number of edges present in Graph (E) and a matrix of V * V which contains the information related to specific edges.
For eg: if edges[u, v] is set then an edge occurs between Node “u” and Node “v” else there is no edge present in the Graph between Node “u” and Node “v”.
The Adjacency matrix for graph with 4 nodes would be something like this

Advantage

In case Graph is dense (lots of edges are present), then this representation is better as accessing these edges would be easier and memory is highly utilised.

Disadvantage

In case Graph is sparse, lots of memory would be wasted.

Adjacency List

struct Graph {
    int V;
    int E;
    int* list;
};

In this method we save number of nodes present in Graph (V), Total number of edges present in Graph (E) and list is an array of linked list head pointers corresponding to each vertices.
For eg: list[0] will represent a linked list which contains all nodes connected to vertex “0” and so on.
The Adjacency matrix for graph with 4 nodes would be something like this

Advantage

In case Graph is sparse, then this representation is better as memory usage will be less.

Disadvantage

Some operation such as deletion of node would be costly as corresponding linked list also needs to be adjusted which would require traversing and adjusting linked list pointers.

Let’s have a more detailed comparison on both representations:

Important Graph topics

• Graph and its basic implementation
• Breadth First Search Algorithm
• Depth First Search Algorithm