How to implement breadth-first search algorithm using Python?

How to implement breadth-first search algorithm using Python?

Breadth-first search (BFS) is a basic graph search algorithm used to find the shortest path to a specific node (or state) in a graph or tree. It can be widely used in many fields, such as finding the shortest friend relationship chain in social networks, solving maze problems, etc. Python provides powerful data structures and function libraries, making implementing BFS a relatively easy task. This article will introduce how to use Python to implement the BFS algorithm and provide specific code examples.

First, we need to define a graph data structure. Graphs can be represented using adjacency lists or adjacency matrices. In this article, we will represent graphs using adjacency lists. The following is the data structure definition of the graph:

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]
    
    def add_edge(self, src, dest):
        self.adj[src].append(dest)

The above code defines a Graph class, including a constructor and two methods: add_edge() is used to add edges, __init__ () is used to initialize the class.

Next, we can implement the BFS algorithm. The basic idea of ​​the BFS algorithm is to start from a given starting node and traverse the nodes in the graph layer by layer until the target node is found. During the traversal process, a queue is used to store the nodes to be visited. The following is the code to implement the BFS algorithm using Python:

from collections import deque

def BFS(graph, start, goal):
    visited = [False] * graph.V
    queue = deque()

    queue.append(start)
    visited[start] = True

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        if node == goal:
            print("目标节点已找到")
            break

        for i in graph.adj[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

    if not queue:
        print("目标节点未找到")

The above code defines a function named BFS. This function accepts three parameters: graph object graph, starting node start and target node goal. The algorithm uses a visited list to record the nodes that have been visited, and a queue to store the nodes to be visited. In each loop, the first element in the queue is taken out, the node is visited, and its unvisited neighbor nodes are added to the queue. Loop until the target node is found or the queue is empty.

Finally, we can use the graph and BFS algorithm defined above for practical application. The following is an example:

g = Graph(6)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 4)
g.add_edge(3, 4)
g.add_edge(3, 5)
g.add_edge(4, 5)

print("BFS遍历结果为：")
BFS(g, 0, 5)

The above code first creates a graph object g containing 6 nodes, and adds several edges. Then call the BFS function to search the path starting from node 0 to node 5. The program will output the results of the BFS traversal.

In summary, this article introduces how to use Python to implement the breadth-first search algorithm and provides specific code examples. With Python's powerful data structure and function library, we can easily implement the BFS algorithm and apply it to various practical scenarios.

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