Depth First Search (DFS) and graph traversal code implementation

Depth-First Search (DFS) is an algorithm used to traverse or search trees or graphs.

It traverses the nodes of the tree along the depth of the tree, searching for branches of the tree as deeply as possible.

When all sides of the node v have been explored, the search will go back to the starting node of the side where the node v was found.

This process continues until all nodes reachable from the source node have been discovered.

If there are still undiscovered nodes, select one of them as the source node and repeat the above process, the whole process repeats until all nodes are accessed.

In practical applications, DFS can be used to solve many problems, such as finding connected components in the graph, detecting rings in the graph, topological sorting, etc.

This paper will implement the DFS algorithm through recursion and stack, and apply it to the traversal of undirected graphs.

1. Recursively implement DFS.

Recursion is an intuitive way to implement DFS.

In this method, we use the function itself to simulate the behavior of the stack.

Each time we call the function, we mark the current node as accessed, and then recursively access all its unaccessed neighbors.

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 访问节点
    for next in graph[start] - visited:
        dfs_recursive(graph, next, visited)
    return visited

# 示例图的邻接表表示
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

# 从节点'A'开始递归DFS
dfs_recursive(graph, 'A')

In this example, we start DFS traversal from node 'A'.

First access node 'A', then recursively access its neighbors' B 'and' C '.

For each neighbor, we continue to recursively access their unvisited neighbors until all nodes are accessed.

2. The stack implements DFS.

Although the recursive method is simple and intuitive, it relies on the function call stack, which can lead to stack overflow problems when handling very large graphs.

To avoid this situation, we can use the explicit stack to simulate the recursive process.

def dfs_stack(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # 访问节点
            stack.extend(graph[vertex] - visited)
    return visited

# 从节点'A'开始使用栈进行DFS
dfs_stack(graph, 'A')

In this implementation, we use a list as a stack to store nodes to be accessed.

Initially, there are only starting nodes in the stack.

In each step, we pop a node from the stack, access it, and add all its unaccessed neighbors to the stack.

This process repeats until the stack is empty.

3. Application examples of DFS.

DFS has a wide range of applications in computer science.

The following are some practical application scenarios: - # Path Find #: Find the path from start to finish in a maze or map.

- # Connected Component #: Find all interconnected user groups in social networks.

- # Topological Sort #: Find a linear sort of vertices in a directed acyclic graph (DAG) so that for each directed edge uv, the vertex u appears before the vertex v in the sort.

- # Strongly connected component #: Find all strongly connected subgraphs in the directed graph.

4. Summary.

Depth First Search (DFS) is a powerful graph traversal algorithm that can be implemented in two ways: recursion and stack.

The recursive method is simple and intuitive, but it may encounter stack overflow problems when dealing with large graphs; while the method using the explicit stack is more powerful and suitable for processing large-scale graphs.

DFS has a wide range of uses in practical applications, including path lookup, connected component detection, topological sorting, etc.

By understanding and mastering DFS, we can effectively solve many complex graph theory problems.