Graph and its representation

Difficulty Level Medium
Frequently asked in Delhivery Factset Infosys MAQ o9 solutions
Data Structure Graph TheoryViews 1233

A graph is an abstract data type representing relations or connections between objects(like cities are connected by rough road). In the graph and its representation, basically, the relation is denoted by edges and objects by vertices(nodes). A graph consists of a finite set of vertices and edges. A graph is a non-linear Data Structure. Let’s take an example of Facebook, we all aware that friends are in a bidirectional relationship on Facebook, if A is a friend of B then B is also the friend of A. The group of friends in which each friend is the friend of remaining friends is an example of Undirected Graph.

 

Graph and its representation

                        Figure 1: A undirected graph consists of vertices={1,2,3,4,5,6} and edges={12,14,23,35,45,56}
  • Nodes/Vertices:  It’s like entities whose relationship is defined by edges.
  • Edges: It’s like components that represent the relationship between nodes/vertices.

Types of Graphs

  • Undirected Graph: It’s a set of objects(nodes/vertices) that are connected together by edges which are bidirectional in nature(See Figure 1).
  • Directed Graph: It’s a set of objects(nodes/vertices) that are connected together by edges, where all the edges are directed from one node to another(See Figure 2).
  • Weighted Graph: It’s a set of objects(nodes/vertices) that are connected together by edges, where each edge of a graph has an associated numerical value called a weight(See Figure 3).

Graph and its representation                                                        Graph and its representation

             Figure 2: Directed Graph                                                                                     Figure 3: Weighted Graph

Implementation of Graph

There are different ways to optimally represent a graph, depending on the density of its edges and the type of operations we want to perform.

Adjacency Matrix

It’s a connection matrix of size V*V where V is the total number of vertices that contains only 0,1. Where i is adjacent to j and 1 <= i, j<=V then its value is 1 otherwise 0. Let us see some example of adjacency matrix:

Graph and its representation                   

Undirected graph adjacency matrix       Directed graph adjacency matrix        Weighted graph adjacency matrix

(See Fig. 1)                                                          (See Fig. 2)                                                              (See Fig. 3)

NOTE: If there is no self-loop in the graph then all cells where i=j must be 0(See above matrices).

/*C++ Implementation of adjacency matrix for undirected graph*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int nodes,edges;
    cin>>nodes>>edges;
    int adj_matrix[nodes+1][nodes+1];
    memset(adj_matrix,0,sizeof(adj_matrix));
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        adj_matrix[x][y]=1;
        adj_matrix[y][x]=1;// for directed graph we don't write for y->x;
    }
    /*Print the adjacency matrix*/
    for(int i=1;i<=nodes;i++)
    {
        for(int j=1;j<=nodes;j++)
        {
            cout<<adj_matrix[i][j]<<" ";
        }
        cout<<"\n";
    }
  return 0;
}
/* TIME COMPLEXITY: O(N*N) WHERE N IS THE NUMBER OF NODES IN GRAPH */

Adjacency List

It’s a linked representation that contains N (total nodes) lists in which each list describes the set of neighbors of a vertex in the graph. The size of the list (for any vertex) is equal to the degree of that vertex.

Directed graph Adjacency List(See fig. 2)

/*C++ Implementation of adjacency list for directed graph using STL*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int nodes,edges;
    cin>>nodes>>edges;
    vector<int> v[nodes+1];
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y); /* add v[y].push_back(x) also for undirected graph beacuse edge is bidirectional in nature*/
    }
    /*Print the adjacency matrix*/
    for(int i=1;i<=nodes;i++)
    {
        int degree=v[i].size();
        for(int j=0;j<degree;j++)
        {
            cout<<v[i][j]<<" ";
        }
        cout<<"\n";
    }
  return 0;
}
/* TIME COMPLEXITY: O(V+E) WHERE V IS THE NUMBER OF VERTICES/NODES IN GRAPH AND E IS THE NUMBER OF EDGES */

Reference

Reference1

Translate »