CareerCup4.2.cpp

CareerCup4.2.cpp

/*
 * Chapter 4
 * 4.2 Given a directeed graph, design an algorithm to find out
 * whether there is a route between two nodes.
 */

#include <iostream>
#include <queue>
#include <list>

using namespace std;

// Inspired from geeksforgeeks.com
// Definition of class Graph
class Graph
{
private:
    int V;  // No. of vertices
    list<int>* adj;  // Pointer points to an array of adjacent list
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w);  // Function: add an directed edge from v to w
    bool isRoute(int src, int des);  // Function: check if there is a route between src and des
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)  // v, w range from 0 ~ V-1
{
    adj[v].push_back(w);
}

bool Graph::isRoute(int src, int des)
{
    if (src == des)
        return true;
    // Mark all the vertices as unvisited
    bool* visited = new bool[V];
    for (int i = 0; i < V; ++i)
    {
        visited[i] = false;
    }
    // Bread-First-Search: add unvisited adjacent vertices to queue
    //
    // initialize queue
    queue<int> Q;
    Q.push(src);  // first element in queue
    visited[src] = true;  // marked as visited
    // loop
    while (!Q.empty()) {
        src = Q.front();
        Q.pop();
        for (list<int>::iterator it = adj[src].begin(); it != adj[src].end(); ++it) {
            if (*it == des)
                return true;
            if (!visited[*it]) {
                Q.push(*it);
                visited[*it] = true;
            }
        }
    }
    return false;
}

// Main Function to test
int main(int argc, char const *argv[])
{
    // Define and initialize a directed graph
    Graph G(4);
    G.addEdge(0, 1);
    G.addEdge(1, 2);
    G.addEdge(3, 1);
    // Test
    int src = 3, des = 2;
    if (G.isRoute(src, des))
        cout << src << " and " << des << " has a route between them." << endl;
    else
        cout << "No route between " << src << " and " << des << endl;
    return 0;
}