Depth-first search

Given an adjacency-list representation of a graph and a starting vertex, visit and print every reachable vertex in depth-first order.

Hint

Use recursion and a visited array. Mark the current vertex before exploring its neighbors, then recursively visit each neighbor that has not been visited. This prevents cycles from causing repeated visits.

• Python
• Javascript
•  Run

graph = [[1, 2], [2, 0], [1, 0, 3, 4], [2], [2]]
visited = [False] * len(graph)

def dfs(graph, visited, src):
    visited[src] = True
    print(src, end=" ")

    for i in graph[src]:
      if not visited[i]:
        dfs(graph, visited, i)

dfs(graph, visited, 1)

//=include dfs.js