Depth-first search

Depth-first search starts at a node, moves to an unvisited neighbour, then to that node's unvisited neighbour, and keeps going until it hits a dead end. Then it backtracks to the most recent node that still has unexplored neighbours. It is written with recursion (the call stack) or an explicit stack.

DFS visits every reachable node once, so it costs O(V + E) time, the same as BFS. It does not find shortest paths, but it naturally answers questions about structure: which nodes are connected, does a cycle exist, what order must things finish in, and what are all the paths.

In directed graphs, DFS tracks three states per node: unvisited, on the current path (in progress), and finished. Meeting a node that is still on the current path means you found a back edge, which is exactly a cycle.

1. 1Mark the current node visited.
2. 2For each neighbour that is not visited, recurse into it (or push it onto a stack).
3. 3When all neighbours are done, the call returns: this is the moment the node is finished, which postorder-style algorithms (like topological sort) use.
4. 4To cover a whole graph, loop over every node and start a new DFS from each one that is still unvisited. Each start is a new connected component.
5. 5Directed cycle check: colour nodes 0 (unvisited), 1 (on the current path) and 2 (finished). Reaching a colour-1 node means a cycle.
6. 6Undirected cycle check: a visited neighbour that is not the node you came from (the parent) means a cycle.

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            count += 1
            grid[r][c] = '0'          # sink it so it is never counted again
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1':
                        grid[ni][nj] = '0'
                        stack.append((ni, nj))
    return count

def has_cycle(n, adj):
    state = [0] * n                   # 0 new, 1 on current path, 2 done
    def dfs(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1 or (state[v] == 0 and dfs(v)):
                return True           # back edge found
        state[u] = 2
        return False
    return any(state[u] == 0 and dfs(u) for u in range(n))

num_islands uses an explicit stack so deep regions cannot overflow Python's recursion limit, and marks cells when pushed. has_cycle is the three-colour check for directed graphs. Both are O(V + E); for the grid that is O(rows x cols).

Cost: O(V + E) time. Space O(V) for the visited set plus O(depth) for the stack, which can reach O(V).