Graph Algorithms: Basic Guide for Your Next Technical Interview

This tutorial is about basic graph algorithms and how these can be used to solve some general problems asked in technical interviews.

Want to ace your technical interview? Schedule a Technical Interview Practice Session with an expert now!

Graph

A graph is a collection of finite sets of vertices (or nodes) (V) and edges (E). Edges are represented as ordered pairs (u, v) where (u, v) indicates that there is an edge from vertex u to vertex v. Edges may contain cost, weight, or length. The degree or valency of a vertex is the number of edges that connect to it.

Types of Graphs:

Undirected

An undirected graph is a graph in which all the edges are bidirectional, that is, edges don’t point in a specific direction.

Directed

A directed graph is a graph in which all the edges are unidirectional.

Weighted

Graph in which edges have some weight or cost assigned to them.

In the image below, we can see that there are many paths with some cost associated with them, for example, to go from vertex 0 to vertex 3, there are two possible paths

1. 0 -> 2 -> 3 with cost = 6 + 1 = 7
2. 0 -> 1 -> 3 with cost = 1 + 3 = 4

A graph is called Cyclic if it contains a path that starts and ends on the same vertex; such paths are called Cycle. A Graph containing no cycle is called Acyclic Graph.

A Tree is an Acyclic Graph such that there exists exactly one path between any pair of vertices and have N-1 edges with N vertices.

Graph Representation:

Mainly, a graph is represented in these two ways.

Adjacency Matrix:

Adjacency matrix is a V x V matrix in which entry A[i][j] = 1 if there exists a path from vertex i to vertex j—else it is 0. We can observe easily that if graph is Undirected then A[i][j] = A[j][i], while the same is not necessary in the case of a directed graph.
Adjacency matrix can be easily modified to store cost of path A[i][j] = C(i,j)
in case of weighted graph.
Time complexity of accessing information from Adjacency Matrix is O(1) while Space complexity is O(N^2)

Example of above can be seen in the image below

Code in cpp showing the use of Adjacency Matrix:

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int nodes, edges;
  cin >> nodes;      // input number of nodes in graph
  cin >> edges;      // input number of edges in graph

  int graph[nodes+1][nodes+1];
  for( int i =0 ; i <= nodes ; i++) 
    for( int j = 0 ; j <= nodes ; j++)
      graph[i][j] = 0; // initilise all nodes as disconnected from all nodes.

  for( int i = 0 ; i < edges ; i++)
  {
    int u , v ;
    cin >> u >> v;
    graph[u][v] = 1;  // graph[u][v] = c if c is weight of edge
    graph[v][u] = 1;  // if graph is Directed this line will be omitted.
  }

  for( int i = 1 ; i <= nodes ; i++ )
  {
    cout << " Node " << i << " is connected to : " ;
    for( int j = 1 ; j <= nodes ; j++)
    {
      if( graph[i][j] )
        cout << j << " ";
    }
    cout << endl;
  }
  return 0;

}

Adjacency List:

The adjacency list is another way to represent a graph. It is a collection of lists (A) where A[i] contains vertices which are neighbors of vertex i. For a weighted graph, we can store weight or the cost of the edge along with the vertex in the list using pairs.
The space complexity of Adjacency list is O( V + E ).
You can see an example in the image below:

Code in cpp showing the use of Adjacency List:

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int nodes, edges;
  cin >> nodes;      // input number of nodes in graph
  cin >> edges;      // input number of edges in graph

  vector< vector<int> > graph( nodes+1); // or we can use graph[nodes+1] ( array of vectors ) also
  
  for( int i = 0 ; i < edges ; i++)
  {
    int u , v ;
    cin >> u >> v;
    graph[u].push_back(v);      // we can use a pair of (v,cost) in case of weighted graph
    graph[v].push_back(u);      // if graph is Directed this line will be omitted.
  }

  for( int i = 1 ; i <= nodes ; i++ )
  {
    cout << " Node " << i << " is connected to : " ;
    for( int u : graph[i])
    {
      cout << u << " ";
    }
    cout << endl;
  }
  return 0;

}

Basic Graph Algorithms

Depth First Search (DFS):

Depth-first search is a recursive algorithm that uses the idea of backtracking. Basically, it involves exhaustive searching of all the nodes by going ahead—if it is possible. Otherwise, it will backtrack. By backtrack, we mean that when we do not get any further node in the current path, then we move back to the node from where we can find the further nodes to traverse. In other words, we will continue visiting nodes as soon as we find an unvisited node on the current path; and when the current path is completely traversed, we will select the next path.

Check out the code below:

#include <bits/stdc++.h>
using namespace std;
vector< int > vis;
vector< vector<int> > graph;
void dfs( int x)
{
  vis[x] = 1;
  cout << x << " ";
  for( int u : graph[x] )
  {
    if( !vis[u] )
      dfs(u);
  }
}

int main()
{
  int nodes, edges;
  cin >> nodes ;     // input number of nodes in graph
  cin >> edges ;     // input number of edges in graph

  graph.resize( nodes+1);
  vis.resize(nodes+1);
  for( int i =0 ; i <= nodes ; i++)
    vis[i] = 0;  // marking all nodes as not visited in starting

  for( int i = 0 ; i < edges ; i++)
  {
    int u , v ;
    cin >> u >> v;
    graph[u].push_back(v);      // we can use a pair of (v,cost) in case of weighted graph
    graph[v].push_back(u);      // if graph is Directed this line will be omitted.
  }

  dfs(1);
  return 0;

}

Breadth First Search (BFS):

Start traversing from a selected node (source or starting node) and traverse the graph layerwise. This means it explores the neighbor nodes (nodes which are directly connected to the source node) and then move towards the next level neighbor nodes. As the name suggests, we move in breadth of the graph, i.e., we move horizontally first and visit all the nodes of the current layer then we move to the next layer.
In BFS, all nodes on layer 1 will be traversed before we move to nodes of layer 2. As the nodes on layer 1 is closer from the source node when compared with nodes on layer 2.
As the graph can contain cycles, we may cross the same node again while traversing the graph. So to avoid processing the same node again, we use a boolean array which marks off the node if it has been processed. While visiting all the nodes of the current layer of the graph, we will store them in such a way that we can visit the children of these nodes in the same order as they were visited.
To accomplish the process, we will use a queue to store the node and mark it as visited. Then we will store it in the queue until all its neighbors (vertices which are directly connected to it) are marked. As the queue follows the FIFO order (First In First Out), nodes that were inserted first in the queue will be visited first.

Sample Code for BFS:

void bfs()
{
     memset( vis , 0 , sizeof(vis ) ); // Initiliseg the all nodes to no-visited,
     queue< int > q;
     q.push(0);
     vis[0] = 1;
     while( !q.empty() )
     {
            int x = q.front();
            q.pop();
            cout << x << " ";
            for( int i = 0 ; i < graph[x].size() ; ++i )
            {
                 if( !vis[ graph[x][i] ] )
                 {
                     q.push( graph[x][i] );
                     vis[ graph[x][i] ] = 1;
                 }
            }
     }
}

Sample problems where these can be used.

Problem 1. Finding connected components in a graph. | Solution code

1. Let's consider each vertex will have some Id; and vertices in the same connected component will have the same Id.
2. Make an array of size N to store the Id.
3. Iterate over all the vertices and call the DFS on the vertex if it's not visited (by DFS called before ).
4. Send a parameter in DFS call which will assign the Id to vertices discovered in the given DFS call.
5. Now vertices having the same Id are in the same connected component.
6. Now we can easily manipulate the data available to answer query related to the connected component.

Problem 2: Amazon
(Link to problem | Solution Code)

1. It is clear from the problem statement that we need to find the number of connected components consisting of 'X'.
2. Considering each (i, j) with value 'X' as a node, and nodes right, left, up, and down as it's neighbors (consider corner case of first and last row; and first and last column).
3. Iterate over all the nodes and call DFS if its value is 'X' and is not visited until now.
4. Return number of unique Id's allotted (we don't need to store the Ids of each vertex)

Problem 3: Google (Link to problem | Solution Code)

1. First, we find the connected component of 'O' just like in problem 2.
2. With little observation, we can say that the conversion of 'O' to 'X' will take the place for a connected component altogether.
3. The 'O' present on the boundary will not be converted.
4. The 'O's connected to boundary 'O' will not be converted.
5. So if in a connected component there lies an 'O' which is on the boundary, then this component will not change, else it will.
6. We can find Ids of a connected component that will change in step 5.
7. Finally, we convert the elements that are present in the connected component found in step 6.

Problem 4: Amazon (Link to problem)

1. Consider each (i,j) as node and nodes on up, down, left, and right as neighbors.
2. We iterate over the matrix to search the starting character of word.
3. Then we can call DFS( 0 , word)

Pseudo code

dfs( node , index, word)
  if ( node.char != word[index] )
    return false
  if ( index == word.length() )
    return true
  toreturn = false
  for nextnode in neighbor of node
    toreturn |= dfs( nextnode, index+1, word)
  return toreturn

Wrapping up

Hopefully, by knowing some basic graph algorithms this will be useful to your career not only during your technical interview but as you develop more applications in the future.