How to write a depth-first search algorithm in Python?

How to write a depth-first search algorithm in Python?

Depth-First Search (DFS) is a commonly used graph traversal algorithm. In depth-first search, starting from the starting node, adjacent nodes are continuously explored until no more exploration is possible, and then it falls back to the previous node and continues to traverse unexplored adjacent nodes until all nodes are visited.

The following is an example of a depth-first search algorithm written in Python:

# 定义图的类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 节点数量
        self.adj = [[] for _ in range(self.V)]  # 存储节点的邻接节点
        
    # 添加边
    def add_edge(self, u, v):
        self.adj[u].append(v)
        
    # DFS递归函数
    def dfs_util(self, u, visited):
        visited[u] = True  # 标记当前节点为已访问
        
        print(u, end=' ')  # 输出当前节点
        
        # 遍历当前节点的所有邻接节点
        for i in self.adj[u]:
            if not visited[i]:
                self.dfs_util(i, visited)
            
    # 对外接口，执行DFS
    def dfs(self, u):
        visited = [False] * self.V  # 标记所有节点均未访问
        
        self.dfs_util(u, visited)
        

# 测试代码
if __name__ == '__main__':
    # 创建一个具有4个节点的图
    g = Graph(4)
    
    # 添加图的边
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)
    g.add_edge(3, 3)
    
    print("深度优先遍历结果：")
    g.dfs(2)

The above code implements a Graph class to represent the structure of the graph, which includes the initial number of nodes and the definition of adjacent nodes . Then the function to add edges add_edge is defined.

DFS algorithm is performed with the assistance of dfs_util recursive function. The function accepts two parameters: the current node u and an array visited, using To mark whether the node has been visited. The algorithm first marks the current node as visited and outputs the value of the node. Then traverse all adjacent nodes of the current node. If the adjacent nodes have not been visited, the dfs_util function is called recursively.

Finally, the dfs function serves as the external interface, accepts the starting node as a parameter, and creates a visited array initialized to False. Call the dfs_util function to start DFS traversal.

In the test code, we create a graph with 4 nodes and add some edges. Then use starting node 2 to perform DFS traversal and output the results.

Hope this code example helps you understand how to write a depth-first search algorithm in Python. You can also modify and optimize the code according to your own needs.

The above is the detailed content of How to write a depth-first search algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!