Depth First Search

Applications:

• cycle detection
• Topological sorting
• path finding

Python

# s: source vertex
def DFS(adjL, s):
    visited = [False] * len(adjL)

    def helper(src):
        visited[src] = True
        print(src)
        for u in adjL[src]:
            if not visited[src]:
                helper(u)

    helper(s)

Disconnected Graph

Time: $O(V + E)$

Python

def DFSDisconnected(adjL):
    visited = [False] * len(adjL)

    def helper(src):
        visited[src] = True
        print(src)
        for u in adjL[src]:
            if not visited[src]:
                helper(u)

    for u in range(len(adjL)):
        if not visited[u]:
            helper(s)