Home » Technical Interview Questions » Graph Interview Questions » Graph and its representation

Graph and its representation


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

READ  Floyd Warshall Algorithm

             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.

READ  Bipartite Graph

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup