Question

// (A) Implement the code below. For a given graph, return a Set of type T of all of the strongly connected nodes of the given key.

public Set<T> stronglyConnectedComponent(T key) {

return null;

}

// (B) Implement the code below. Optimally find the shortest path between the given start and end node.

public List<T> shortestPath(T startLabel, T endLabel) {
       return null;
}

Answer 1

(A) Implement the code below. For a given graph, return a Set of type T of all of the strongly connected nodes of the given key.

Program to check if a given directed graph is strongly connected

#include <iostream>
#include <stack>

#include <list>

using namespace std;

class Graph
{
   int V; // No. of vertices
   list<int> *adj; // An array of adjacency lists
   void DFSUtil(int v, bool visited[]);
public:
   Graph(int V) { this->V = V; adj = new list<int>[V];}
   ~Graph() { delete [] adj; }
   void addEdge(int v, int w);

   bool isStronglyConnected();
   Graph getTranspose();
};
void Graph::DFSUtil(int v, bool visited[])
{

   visited[v] = true;
   list<int>::iterator i;
   for (i = adj[v].begin(); i != adj[v].end(); ++i)
       if (!visited[*i])
           DFSUtil(*i, visited);
}
Graph Graph::getTranspose()
{
   Graph g(V);
   for (int v = 0; v < V; v++)
   {

       list<int>::iterator i;
       for(i = adj[v].begin(); i != adj[v].end(); ++i)
       {
           g.adj[*i].push_back(v);
       }
   }
   return g;
}

void Graph::addEdge(int v, int w)
{
   adj[v].push_back(w);
}

bool Graph::isStronglyConnected()
{
  
   bool visited[V];
   for (int i = 0; i < V; i++)
       visited[i] = false;

   DFSUtil(0, visited);

   for (int i = 0; i < V; i++)
       if (visited[i] == false)
           return false;

   Graph gr = getTranspose();
   for(int i = 0; i < V; i++)
       visited[i] = false;

   gr.DFSUtil(0, visited);

   for (int i = 0; i < V; i++)
       if (visited[i] == false)
           return false;

   return true;
}

int main()
{
  
   Graph g1(5);
   g1.addEdge(0, 1);
   g1.addEdge(1, 2);
   g1.addEdge(2, 3);
   g1.addEdge(3, 0);
   g1.addEdge(2, 4);
   g1.addEdge(4, 2);
   g1.isStronglyConnected()? cout << "Yes\n" : cout << "No\n";

   Graph g2(4);
   g2.addEdge(0, 1);
   g2.addEdge(1, 2);
   g2.addEdge(2, 3);
   g2.isStronglyConnected()? cout << "Yes\n" : cout << "No\n";

   return 0;
}

(B) Implement the code below. Optimally find the shortest path between the given start and end node.

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

void add-edge(vector<int> adj[], int src, int dest)
{
   adj[src].push_back(dest);
   adj[dest].push_back(src);
}

bool BFS(vector<int> adj[], int src, int dest, int v,
                           int pred[], int dist[])
{
   list<int> queue;

   bool visited[v];

   for (int i = 0; i < v; i++) {
       visited[i] = false;
       dist[i] = INT_MAX;
       pred[i] = -1;
   }

  
   visited[src] = true;
   dist[src] = 0;
   queue.push_back(src);

  
   while (!queue.empty()) {
       int u = queue.front();
       queue.pop_front();
       for (int i = 0; i < adj[u].size(); i++) {
           if (visited[adj[u][i]] == false) {
               visited[adj[u][i]] = true;
               dist[adj[u][i]] = dist[u] + 1;
               pred[adj[u][i]] = u;
               queue.push_back(adj[u][i]);
               if (adj[u][i] == dest)
               return true;
           }
       }
   }

   return false;
}
void printShortestDistance(vector<int> adj[], int s,
                                   int dest, int v)
{
   int pred[v], dist[v];

   if (BFS(adj, s, dest, v, pred, dist) == false)
   {
       cout << "Given source and destination"
           << " are not connected";
       return;
   }
   vector<int> path;
   int crawl = dest;
   path.push_back(crawl);
   while (pred[crawl] != -1) {
       path.push_back(pred[crawl]);
       crawl = pred[crawl];
   }

   cout << "Shortest path length is : "
       << dist[dest];

  
   cout << "\nPath is::\n";
   for (int i = path.size() - 1; i >= 0; i--)
       cout << path[i] << " ";
}

int main()
{

   int v = 8;

   vector<int> adj[v];

  
   add_edge(adj, 0, 1);
   add_edge(adj, 0, 3);
   add_edge(adj, 1, 2);
   add_edge(adj, 3, 4);
   add_edge(adj, 3, 7);
   add_edge(adj, 4, 5);
   add_edge(adj, 4, 6);
   add_edge(adj, 4, 7);
   add_edge(adj, 5, 6);
   add_edge(adj, 6, 7);
   int source = 0, dest = 7;
   printShortestDistance(adj, source, dest, v);
   return 0;
}