Algorithm for finding every weakly connected component of a directed graph

Question

I am searching for an algorithm for finding every weakly connected component in a directed graph. I know for an undirected graph you can do this via a dfs but this obviously doenst work for an directed graph. I am saving my graph as an adjacents list. For example:

A -> B
B -> C
D -> X

So A-B-C is a connected component an D-X

I am not searching for an algorithm for finding strongly connected components!!

Answer 1

Unless your memory constraints are too strict, you can keep a second, temporary adjacency list. In that second adjacency list you put each edge a->b and you also put edges in reverse direction. (i.e. b->a) Then, you can use DFS on that adjacency list to find connected components.

Answer 2

A pretty simple solution would be as follows:
Start by creating an undirected graph from the given graph - simply make a copy and add the reverse for each edge to the set of edges. Create a copy of the set of vertices, start with an arbitrary vertex and DFS-traverse the component containing the vertex, removing all traversed nodes from the set and adding them to a list. Repeat this until the list is empty.

In pseudocode:

bimap edges
edges.putAll(graph.edges())

set vertices = graph.vertices()

list result

while !vertices.isEmpty()
    list component

    vertex a = vertices.removeAny()
    dfsTraverse(a , v -> {
        vertices.remove(v)
        component.add(v)
    })

    result.add(component)