Python输出广度搜索代码
时间: 2023-11-21 13:46:41 浏览: 14
以下是一个简单的Python广度搜索代码示例:
```
from queue import Queue
# 定义图的邻接矩阵
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# 定义广度搜索函数
def bfs(graph, start):
visited = set() # 记录已访问的节点
q = Queue() # 定义队列
q.put(start) # 将起点加入队列
visited.add(start) # 记录起点已访问
while not q.empty():
node = q.get() # 取出队首节点
print(node, end=" ")
for neighbor in graph[node]: # 遍历该节点的邻居节点
if neighbor not in visited: # 如果邻居节点未被访问,则加入队列
visited.add(neighbor)
q.put(neighbor)
# 测试广度搜索函数
bfs(graph, 'A')
```
希望能对您有所帮助。
相关问题
广度优先搜索python
广度优先搜索(BFS)是图论中常用的算法,用于遍历或搜索图中的节点。在Python中,可以使用队列(queue)来实现BFS算法。以下是一个简单的广度优先搜索的Python实现示例:
```python
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)
# 示例图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 从节点A开始进行广度优先搜索
bfs(graph, 'A')
```
以上代码中,我们使用了一个队列来保存待访问的节点,通过不断从队列中取出节点并访问其邻居节点,实现了广度优先搜索算法。`visited`集合用于记录已经访问过的节点,以避免重复访问。
以上示例中的图使用邻接表表示,每个节点对应一个列表,列表中存储了该节点的邻居节点。你可以根据实际需求,修改图的表示方式。
希望对你有所帮助!如果还有其他问题,请继续提问。
Python 邻接矩阵 广度优先搜索
邻接矩阵是一种表示图的数据结构,可以用它来存储图中的节点和边。在邻接矩阵中,每个节点与其他节点之间的关系用一个矩阵来表示,矩阵中的每个元素表示两个节点之间是否有边相连。
广度优先搜索(BFS)是一种图遍历算法,从指定的起始节点开始,依次访问与其相邻的节点,直到遍历完所有节点。BFS的遍历方式类似于层次遍历,先访问起始节点,然后访问所有与其相邻的节点,再访问这些节点的相邻节点,依此类推。
下面是 Python 中邻接矩阵的实现:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, i, j):
self.adj_matrix[i][j] = 1
self.adj_matrix[j][i] = 1
def bfs(self, start_vertex):
visited = [False] * self.num_vertices
queue = []
queue.append(start_vertex)
visited[start_vertex] = True
while queue:
current_vertex = queue.pop(0)
print(current_vertex, end=' ')
for i in range(self.num_vertices):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
```
上面的代码中,Graph 类中的 adj_matrix 用于存储邻接矩阵,add_edge 方法用于添加边,bfs 方法用于实现广度优先搜索。
在 bfs 方法中,visited 用于记录每个节点是否被访问过,queue 用于存储待访问的节点。首先将起始节点加入队列,并将其标记为已访问。然后,如果队列不为空,就取出队列中的第一个节点,打印它,并将它的相邻节点加入队列。最后,将已访问的节点标记为 True。重复执行以上步骤,直到队列为空,搜索结束。
下面是一个示例:
```python
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(2, 4)
g.bfs(0)
```
输出:
```
0 1 2 3 4
```
这个示例中,起始节点是 0,我们按照广度优先的顺序遍历了整个图。