用Python代码实现广度优先搜索算法

下面是用Python实现广度优先搜索算法的示例代码：# 定义图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}# 定义广度优先搜索函数
def bfs(graph, start):
visited = [] # 已访问节点
queue = [start] # 搜索队列 while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
neighbours = graph[node] for neighbour in neighbours:
queue.append(neighbour) return visited# 调用函数
print(bfs(graph, 'A'))

相关问题

使用python实现广度优先搜索算法无向图

使用Python实现广度优先搜索算法可以通过以下步骤进行：

1. 首先，创建一个图的类，其中包含节点和边的信息。可以使用字典来表示节点和它们的邻居节点。

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, node, neighbor):
        if node not in self.graph:
            self.graph[node] = []
        self.graph[node].append(neighbor)

        if neighbor not in self.graph:
            self.graph[neighbor] = []
        self.graph[neighbor].append(node)

2. 接下来，实现广度优先搜索算法。使用队列来存储待访问的节点，并使用一个集合来记录已经访问过的节点。

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

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

        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

3. 最后，创建一个图对象并添加节点和边，然后调用广度优先搜索函数。

# 创建图对象
g = Graph()

# 添加节点和边
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('B', 'E')
g.add_edge('C', 'F')

# 调用广度优先搜索算法
bfs(g.graph, 'A')

这样就可以实现广度优先搜索算法来遍历无向图了。

python代码实现深度优先

以下是Python代码实现深度优先搜索算法的示例：

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

其中，`graph`是一个字典，用于存储图的邻接表；`start`是起始节点。

该算法的基本思想是从起始点开始，不断往他的下一层走，直到无法继续为止。然后回溯到上一个节点，再往他的下一层走，直到图中所有节点都被访问完为止。