Constructing a Graph/Tree in C++

Graph is a data structure that consists of following two components:
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not same as (v, u) in case of a directed graph(di-graph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.

A tree is a special graph in which, if there exists any path between two nodes, then that is the only path. In easy language a tree can be said as a graph with no cycles. Tree is basically used to store data in a hierarchical form.

An undirected graph with 5 vertices and 7 edges.

In this article I am going to tell how to construct a tree/graph in your codes:

Following two are the most commonly used representations of a graph.

1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix:
Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

The adjacency matrix for the above example graph is:
Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time. Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1).

Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges), it consumes the same space. Adding a vertex is O(V^2) time.

Adjacency List:
An array of lists is used. Size of the array is equal to the number of vertices. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is adjacency list representation of the above graph.

Adjacency List can be easily implemented using dynamic arrays i.e., vectors in C++ and ArrayList in Java. Following is the code implementation of constructing an adjacency list:

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define ll long long

#define mod 1000000007

#define N 100005

#define f(i,a,b) for(i=a;i<b;i++)

#define fr(i,a,b) for(i=a;i>=b;i--)

#define vi vector<int> 

vi graph[N]; //usually maximum no. of nodes in a graph is of order 10^5

void constructGraph()

{

    int n,m,i; //n=no. of nodes, m=no. of edges. m=n-1 when the graph is tree

    cin>>n>>m;

    int u,v; //will store the nodes having an edge between them

    f(i,0,m)

    {

        cin>>u>>v;

        graph[u].push_back(v); //signifies an edge from u -> v

        graph[v].push_back(u); //signifies an edge from v -> u

        //in case of directed graph only one of them will be present

    }

}

signed main() {

    constructGraph();

    return 0;

}

Pros: Saves space O(|V|+|E|) . In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.

Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).

Thanks for reading!

Reference:
Graph (abstract data type)