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

Question

I have a graph with a huge number of nodes with one start of the node (all edges are outward) and one end of the node (all edges to it). This is a unidirectional and unweighted chart. How to optimize the search in this type of graph to find out if there is a path between two nodes? I know that BFS provides a solution. Is there a way to optimize the search (for example, add additional information), since I will often visit the chart on the chart?

EDIT: to add additional information about the graph, the graph has one start node with several external edges and one end node with several edges. Between them millions of nodes are connected. This is an unweighted DAG. And there are no heuristics. Just check isConnected (node ​​a, node b).

Answer 1

Given that your schedule is acyclic, this is the way to do it: -

• Will DFS on the chart start at the top of the source (only for external borders)

• For each edge (u, v) in the graph associated with [u] [v] = true

• Try to save the previous node in the DFS stack in an array and for each verified vertex v check the previous nodes in the stack and make [u] [v] = true, where u is the previous node.

If the graph is not acyclic, then first calculate the SCC using Kosaraju or Tarjan, and then reduce the graph to acyclic and connect [u] [v] = true for each pair in SCC

pseudo-code for a modified DFS procedure: -

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); } } } 

Cosmic complexity: O(V^2)

Difficulty of time: O(V^2)

Note: -

If the number of queries is less, try using DFS for them separately and cache the results, as this will be more time consuming than that.