I am looking to check if a directional graph is Strongly connected i.e all nodes can be reached by any node.(not necessarily through direct edge).
One way of doing this is running a dfs and bfs on every node and see all others are still reachable. Is there a better approach to do that?
Tarjan's strongly connected components algorithm (or Gabow's variation) will of course suffice; if there's only one strongly connected component, then the graph is strongly connected.
Both are linear time.
As with a normal depth first search, you track the status of each node: new, seen but still open (it's in the call stack), and seen and finished. In addition, you store the depth when you first reached a node, and the lowest such depth that is reachable from the node (you know this after you finish a node). A node is the root of a strongly connected component if the lowest reachable depth is equal to its own depth. This works even if the depth by which you reach a node from the root isn't the minimum possible.
To check just for whether the whole graph is a single SCC, initiate the dfs from any single node, and when you've finished, if the lowest reachable depth is 0, and every node was visited, then the whole graph is strongly connected.
You can calculate the All-Pairs Shortest Path and see if any is infinite.
One way of doing this would be to generate the Laplacian matrix for the graph, then calculate the eigenvalues, and finally count the number of zeros. The graph is strongly connection if there exists only one zero eigenvalue.
Note: Pay attention to the slightly different method for creating the Laplacian matrix for directed graphs.
Tarjan's Algorithm has been already mentioned. But I usually find Kosaraju's Algorithm easier to follow even though it needs two traversals of the graph. IIRC, it is also pretty well explained in CLRS.
test-connected(G) { choose a vertex x make a list L of vertices reachable from x, and another list K of vertices to be explored. initially, L = K = x.
while K is nonempty find and remove some vertex y in K for each edge (y,z) if (z is not in L) add z to both L and K
if L has fewer than n items return disconnected else return connected }