Graph extended - adjacency list representation

/***
Graph implement:
1. BFS
2. DFS
3. test is cyclic
4. topological sort
http://www.geeksforgeeks.org/topological-sorting/
http://www.cs.washington.edu/education/courses/cse373/02au/lectures/lecture19l.pdf
5. Find a path between two node in a graph --> if node v is reachable with node w
http://www.geeksforgeeks.org/find-if-there-is-a-path-between-two-vertices-in-a-given-graph/
***/

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

using namespace std;

class graph {
       int V;
       list<int> *adj;
       bool cyclicUtil(int, bool*, bool*);
       void BFSUtil(bool *, queue<int> &);
       void DFSUtil(int, bool*);
       void update_degree(int, int *, queue<int> &);
       bool rareachableUtil(int, int, bool *);
public:
       graph(int);
       void addEdge(int, int);
       bool iscycle();
       bool isreachable(int, int);
       void BFS();
       void DFS();
       //only acyclic graph can do topological sort
       bool topological_sort();
};

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

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

bool graph::cyclicUtil(int v, bool *visited, bool *check) {

       if(check[v]) return true;

       if(!visited[v]) {
              visited[v] = true;
              check[v] = true;

              list<int>::iterator it;   
              for(it = adj[v].begin(); it != adj[v].end(); it++) {
                     if(cyclicUtil(*it, visited, check)) return true;
              }
       }
       check[v] = false;
       return false;
}

bool graph::iscycle() {
       bool *visited = new bool[V];
       bool *check = new bool[V];

       //initial bool array
       for(int i=0; i<V; i++) {
              visited[i] = false;
              check[i] = false;
       }

       for(int i=0; i<V; i++) {
              if(!visited[i] && cyclicUtil(i, visited, check)) {
                     delete [] visited;
                     delete [] check;
                     return true;
              }
       }

       delete [] visited;
       delete [] check;
       return false;
}

void graph::BFSUtil(bool *visited, queue<int> &bfs) {
       list<int> :: iterator it;
       while(!bfs.empty()) {
              int cur = bfs.front();
              for(it = adj[cur].begin(); it != adj[cur].end(); it++) {
                     if(!visited[*it]) {
                           bfs.push(*it);
                           visited[*it] = true;
                     }
              }
              cout<<cur<<" ";
              bfs.pop();
       }     
}

void graph::BFS() {
       bool *visited = new bool[V];
       for(int i = 0; i<V; i++)
              visited[i] = false;

       queue<int> bfsqueue;

//     for(int i=0; i<V; i++) {
//            if(!visited[i]) {
                     bfsqueue.push(2);
                     visited[2] = true;
                     BFSUtil(visited, bfsqueue);
//            }
//     }

       delete [] visited;
}

void graph::DFSUtil(int v, bool *visited) {
       list<int> :: iterator it;
      
       visited[v] = true;
       cout<<v<<" ";

       for (it = adj[v].begin(); it != adj[v].end(); it++)
       {
              if (!visited[*it])
                     DFSUtil(*it, visited);
       }
}

void graph::DFS() {
       bool *visited = new bool[V];
       for(int i = 0; i<V; i++) visited[i] = false;

//     for(int i = 0; i < V; i++) {
//            if (!visited[i])
                     DFSUtil(2, visited);
//     }
       delete [] visited;
}

void graph::update_degree(int v, int *degree, queue<int> &zero) {
       list<int> :: iterator it;
       for(it = adj[v].begin(); it != adj[v].end(); it++) {
              --degree[*it];
              if(degree[*it] == 0)
                     zero.push(*it);
       }
}

bool graph::topological_sort() {
       int *degree = new int[V];

       //initial degree of each node
       for(int i=0; i<V; i++)
              degree[i] = 0;

       list<int> :: iterator it;
       for(int i=0; i<V; i++) {
              for(it = adj[i].begin(); it != adj[i].end(); it++) {
                     ++degree[*it];
              }
       }

       queue<int> zero;
       for(int i = 0; i<V; i++) {
              if(degree[i] == 0) {
                     zero.push(i);
              }
       }

       if(zero.empty()) return false;

       while(!zero.empty()) {
              int cur = zero.front();
              cout<<cur<<" ";
              zero.pop();
              update_degree(cur, degree, zero);
       }

       delete [] degree;
       return true;
}

bool graph :: rareachableUtil(int v, int w, bool *visited) {
       if(v == w) return true;

       visited[v] = true;
       list<int> :: iterator it;
       for(it = adj[v].begin(); it != adj[v].end(); it++) {
              if(!visited[*it] && isreachable(*it, w)) return true;
       }
       return false;
}

bool graph :: isreachable(int v, int w) {
       bool *visited = new bool[V];
       for (int i=0; i<V; i++)
       {
              visited[i] = false;
       }

       if (rareachableUtil(v, w, visited)) {
              delete [] visited;
              return true;
       } else {
              delete [] visited;
              return false;
       }
}

int main()
{
       // Create a graph given in the above diagram
       graph g(6);
       g.addEdge(5, 2);
       g.addEdge(5, 0);
       g.addEdge(4, 0);
       g.addEdge(4, 1);
       g.addEdge(2, 3);
       g.addEdge(3, 1);

       if (g.iscycle())
              cout<<"There is a cycle."<<endl;
       else cout<<"No cycle"<<endl;

       g.topological_sort();
       cout<<endl;

       if (g.isreachable(5, 3))
       {
              cout<<"reachable"<<endl;
       } else cout<<"not reachable"<<endl;
       return 0;

}

Comments

Post a Comment

Popular posts from this blog

Sudoku

/*** Sudoku Given a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits (from 1 to 9) to the empty cells so that every row,   column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9. Backtracking Algorithm Like all other Backtracking problems, we can solve Sudoku by one by one assigning numbers to empty cells.  Before assigning a number, we check whether it is safe to assign. We basically check that the same number  is not present in current row, current column and current 3X3 subgrid. After checking for safety,  we assign the number, and recursively check whether this assignment leads to a solution or not.  If the assignment doesn’t lead to a solution, then we try next number for current empty cell.  And if none of number (1 to 9) lead to solution, we return false. ***/ #include <iostream> using namespace std; class Sudoku { public :      ...
Read more

Longest prefix matching - trie

/*** Longest prefix matching Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary. Example: Let the dictionary contains the following words: {are, area, base, cat, cater, children, basement} Below are some input/output examples: -------------------------------------- Input String            Output -------------------------------------- caterer                 cater basemexy                base child                   < Empty > ***/ #include <iostream> #include <string> using namespace std; struct node {        char val; ...
Read more

Climbing Stairs

You are climbing a stair case. It takes  n  steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note:  Given  n  will be a positive integer. class Solution { public:     int climbStairs(int n) {         if (n == 0) return 0;                  if (n == 1) return 1;                  // dp space complexity is O(n)         vector<int> dp(n);         dp[0] = 1;         dp[1] = 2;                  for(int i = 2; i<n; i++)         {             dp[i] = dp[i-1] + dp[i-2];         }                  return dp[ n-1 ]...
Read more