HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What do we do instead of DFS on directed graphs?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whatgraphsdfsdirectedinstead

Problem

All the example of DFS I've seen so far are for undirected graph.
In a directed graph the basic DFS algorithm won't work because some vertex will be unreachable.

The algorithm I'm talking about :
https://en.wikipedia.org/wiki/Depth-first_search

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do 
9                  S.push(w)


Example :

So let's say I start with '1' I will never access 4,5,6 with this algorithm.

For directed graph it looks like we have to know all the vertex and iterate through them.

And so we cannot use a DFS for directed graph ?

Is there a DFS variant or another algorithm ?

Solution

The issue is not specific to DFS.

When looking at directed graphs, even for connected graphs not all nodes are reachable from everywhere. That's why the notion of a graph being strongly connected exists.

In a strongly connected graph, graph traversals starting in a single node will reach all nodes.
In other graphs, it won't.

This affects all traversal algorithms. For some reason, (some) canonical BFS implementations include looping over all starting nodes but DFS implementations do not. I don't know why; I assume historical reasons. There certainly is no conceptual difference; you can just as easily restart DFS with new starting nodes until you cover the whole graph.

Context

StackExchange Computer Science Q#86711, answer score: 5

Revisions (0)

No revisions yet.