CODEWITHSUNDEEP
algorithmgraph
user1429322
user1429322

Reputation: 1286

Best way to find if path exists in a unidirectional directed graph

I have a graph with huge number of nodes with one start node ( all edges are outward ) and one end node ( all edges towards it ). It is an unidirectional and unweighted graph.How to optimize the search in this kind of graph for finding out if path exists between two nodes ? I know BFS provides a solution. Is there anyway to optimize the search ( like adding some additional information ) as I will be doing frequent search on the graph?

EDIT : To add more information about the graph, the graph has one start node with multiple out-edges and one end node with multiple in-edges. In between, there are millions of nodes connected. It is an unweighted DAG. And there are no heuristics involved. Just check isConnected(node a,node b).

Upvotes: 6

Views: 5889

Answers (1)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Considering your graph is acyclic here is a way to do it : -

  1. Do DFS on graph start with source vertex(only outgoiong edges)

  2. For each edge (u,v) in the graph connected[u][v] = true

  3. Try to store the previous node in DFS stack in a array & for each vertex v visited check the previous nodes in the stack and do connected[u][v] = true where u is a previous node.

If graph is not acyclic then first calculate SCC's using Kosaraju or Tarjan and then reduce the graph to acyclic and do connected[u][v] = true for each pair in a SCC

pseudo code for modified DFS routine:-

bool connected[n][n] = {false};   
bool visited[n] = {false};   
int stack[n]; 

for each source vertex v do :   
     DFS(v,stack,0);


void DFS(int u,int stack[n],int depth) {


    if(!visited[v]) {

          visited[v] = true;

          for(int i=0;i<depth;i++) {

               connected[stack[i]][v] = true; 
          }

          stack[depth] = u;

          for each edge(u,v) {
             connected[u][v] = true;
             DFS(v,stack,depth+1);
          }
    }
}

Space Complexity : O(V^2)

Time Complexity : O(V^2)

Note:-

If your number of queries are less then try to use DFS for them individually and cache the results as this will be more time consuming then that.

Upvotes: 2

Related Questions