Find if there is a path between 2 nodes in an undirected graph

Problem Statement:

You are given an undirected graph along with 2 nodes.

You need to check if there is a path between the 2 nodes.

Solution

We can solve this problem by using Floyd Warshall Algorithm.

For that we will create an adjacent matrix and we need to fill all the intermediate paths as:

1. If there is a direct edge, then update the same.

2. Or if we have a path from node src to node “a” and from node “a” to dest node, then we update that also in the adjacency matrix.

Later we check if there is a path from source to destination and get the result.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <list> 

using namespace std;

class Graph
{

private:
   int V; 
   list<int> *adj; // to hold adjacency list
   int **adj_matrix;// to hold o/p for Floyd Warshall Algorithm
 public:
   Graph(int V); // Constructor
   void add_edge(int v, int w); // to add an edge to graph
   void print_graph();
   bool check_if_is_reachable(int src, int dest);
   void calculate_paths();
};

Graph::Graph(int V)
{
   // get the total number of nodes
   this->V = V;

   // initialize adjacency list for that number of nodes
   adj = new list<int>[V];

   // initialize the adj_matrix also
   adj_matrix = new int*[V + 1];
   for (int i = 0; i < V; i++) {
      adj_matrix[i] = new int[V + 1];
      memset(adj_matrix[i], 0, (V + 1) * sizeof(int));
   }

   for (int i = 0; i < V; i++)
      adj_matrix[i][i] = 1;
}

void Graph::add_edge(int v, int w)
{
   // add the edge to adjacency list
   adj[v].push_back(w); 
   // uncomment below to make the graph as undirected
   adj[w].push_back(v); 

   //fill adj_matrix also
   adj_matrix[v][w] = 1;
   adj_matrix[w][v] = 1;
}

void Graph::print_graph()
{
   for(auto i = 0; i < V; i++)
   {
      cout<<"\nAdjacency list of vertex "<<i<<endl;

      for(auto j = adj[i].begin(); j != adj[i].end(); j++)
      {
         cout<<" ->"<<*j;
      }
   }
}

void Graph::calculate_paths()
{
   // floyd warshall algo to check if a path exist
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                adj_matrix[i][j] = adj_matrix[i][j]
                          | (adj_matrix[i][k]
                             && adj_matrix[k][j]);
            }
        }
    }
}

bool Graph::check_if_is_reachable(int src, int dest)
{
 
    if (adj_matrix[src][dest] == 1)
        return true;
    else
        return false;
}

int main()
{

   Graph g(5);
   g.add_edge(1, 0);
   g.add_edge(0, 2);
   g.add_edge(2, 1);
   g.add_edge(0, 3);
   g.add_edge(1, 3);
   g.add_edge(2, 3);

   g.calculate_paths();

   if(g.check_if_is_reachable(1, 3)){
      cout<<"They are reachable"<<endl;
   } else {
      cout<<"They are not reachable"<<endl;
   }
   return 0;
}

Output:

They are reachable