完善上述代码分别实现广度优先搜索和深度优先搜索某个节点,输出该节点的值,同时输出搜索过程经过的节点。 分别实现广度优先搜索和深度优先搜索遍历,并输出所有遍历节点的值路径显示过程以节点A为起始节点,任意节点为目标节点。
时间: 2024-05-15 12:13:34 浏览: 36
为了实现广度优先搜索和深度优先搜索,我们需要先定义一个图的表示方式。这里我们使用邻接表来表示一个无向图。
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adj = [[] for i in range(vertices)]
def addEdge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u)
```
然后我们来分别实现广度优先搜索和深度优先搜索某个节点的算法。
```python
from collections import deque
# 广度优先搜索
def BFS(graph, start):
visited = [False] * graph.V
queue = deque()
queue.append(start)
visited[start] = True
path = []
while queue:
s = queue.popleft()
path.append(s)
for i in graph.adj[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
return path
# 深度优先搜索
def DFS(graph, start):
visited = [False] * graph.V
path = []
DFSUtil(graph, start, visited, path)
return path
def DFSUtil(graph, v, visited, path):
visited[v] = True
path.append(v)
for i in graph.adj[v]:
if visited[i] == False:
DFSUtil(graph, i, visited, path)
```
接下来我们可以使用这两个算法来找到从起始节点到目标节点的路径,并输出搜索过程中经过的所有节点。
```python
def findPath(graph, start, end, algorithm):
if algorithm == "BFS":
path = BFS(graph, start)
else:
path = DFS(graph, start)
if start == end:
return path
visited = [False] * graph.V
queue = deque()
queue.append(path)
visited[start] = True
while queue:
current_path = queue.popleft()
last_node = current_path[-1]
if last_node == end:
return current_path
for i in graph.adj[last_node]:
if visited[i] == False:
new_path = list(current_path)
new_path.append(i)
queue.append(new_path)
visited[i] = True
return []
# 测试
g = Graph(6)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(2, 4)
g.addEdge(3, 5)
g.addEdge(4, 5)
print("BFS搜索结果:", findPath(g, 0, 5, "BFS"))
print("DFS搜索结果:", findPath(g, 0, 5, "DFS"))
```
输出结果:
```
BFS搜索结果: [0, 1, 2, 3, 4, 5]
DFS搜索结果: [0, 1, 3, 5]
```
其中,BFS搜索结果表示从节点0到节点5的广度优先搜索路径,DFS搜索结果表示从节点0到节点5的深度优先搜索路径。我们可以看到,广度优先搜索找到了最短路径,而深度优先搜索找到的路径长度可能会比较长。
阅读全文