图的深度优先遍历和广度优先遍历合在一起的代码
时间: 2023-09-23 20:06:26 浏览: 86
图的深度优先遍历和广度优先遍历
### 回答1:
以下是一个将深度优先遍历和广度优先遍历合并在一起的图遍历代码(使用Python实现):
```python
from collections import deque
# 定义图类
class Graph:
def __init__(self, graph_dict=None):
if graph_dict is None:
graph_dict = {}
self.graph_dict = graph_dict
# 添加节点
def add_node(self, node):
if node not in self.graph_dict:
self.graph_dict[node] = []
# 添加边
def add_edge(self, edge):
edge = set(edge)
(node1, node2) = tuple(edge)
if node1 in self.graph_dict:
self.graph_dict[node1].append(node2)
else:
self.graph_dict[node1] = [node2]
# 深度优先遍历
def dfs(self, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(self.graph_dict[vertex] - visited)
return visited
# 广度优先遍历
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(self.graph_dict[vertex] - visited)
return visited
# 组合深度优先遍历和广度优先遍历
def dfs_bfs(self, start):
visited = set()
stack = [start]
queue = deque([start])
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(self.graph_dict[vertex] - visited)
queue.extend(self.graph_dict[vertex] - visited)
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(self.graph_dict[vertex] - visited)
return visited
```
这个代码中的 Graph 类使用字典来表示图,其中键是节点,值是与该节点相邻的节点列表。我们可以使用 add_node 和 add_edge 方法来添加节点和边。dfs 和 bfs 方法分别实现了深度优先遍历和广度优先遍历。最后,dfs_bfs 方法将深度优先遍历和广度优先遍历组合在一起,返回遍历过的节点列表。
### 回答2:
深度优先遍历(Depth-First Search)和广度优先遍历(Breadth-First Search)都是图遍历的常用方法。下面是将这两种遍历方法合并在一起的代码:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adj_list = [[] for _ in range(vertices)]
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def DFS(self, v, visited):
visited[v] = True
print(v, end=" ")
for i in self.adj_list[v]:
if not visited[i]:
self.DFS(i, visited)
def BFS(self, v, visited):
queue = []
queue.append(v)
visited[v] = True
while queue:
v = queue.pop(0)
print(v, end=" ")
for i in self.adj_list[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
def traverse(self):
V = self.V
visited = [False] * V
for v in range(V):
if not visited[v]:
self.DFS(v, visited)
# self.BFS(v, visited) # 如果希望先深度优先再广度优先,可以调换注释掉的这两行
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
print("图的遍历结果:")
g.traverse()
```
以上代码中,首先定义了图的类`Graph`,包含了建图及遍历所需的方法。其中,`__init__`方法用于初始化图的顶点数和邻接表,`add_edge`方法用于添加边,`DFS`方法用于执行深度优先搜索,`BFS`方法用于执行广度优先搜索,`traverse`方法可以用于遍历整个图。
在`traverse`方法中,首先初始化一个`visited`列表,用于记录顶点的访问情况。然后,通过一个`for`循环遍历所有顶点,对未访问过的顶点进行深度优先遍历(或广度优先遍历)。
其中,深度优先遍历方法`DFS`通过递归的方式访问与当前顶点相邻的未访问过的顶点,期间输出顶点值。广度优先遍历方法`BFS`通过队列来实现,将起始顶点入队,并将其标记为已访问。通过一个`while`循环,从队列中取出顶点,访问与其相邻的未访问过的顶点并将其入队,直到队列为空。
最后,通过创建一个`Graph`对象,并添加边,然后调用`traverse`方法进行遍历。执行代码后,会输出图的遍历结果。
### 回答3:
深度优先遍历(Depth First Search, DFS)和广度优先遍历(Breadth First Search, BFS)是图的两种常见遍历算法。下面是一个将深度优先遍历和广度优先遍历合并在一起的代码示例:
代码实现如下:
```
# 定义图的类
class Graph:
def __init__(self):
self.graph = {} # 图的字典表示
# 添加边
def add_edge(self, node, adjacent_nodes):
self.graph[node] = adjacent_nodes
# 深度优先遍历
def dfs(self, start):
visited = set() # 保存已访问过的节点
stack = [start] # 用栈来保存待访问的节点
while stack:
node = stack.pop() # 弹出栈顶节点
if node not in visited: # 如果节点未被访问过
print(node, end=" ") # 打印节点
visited.add(node)
# 将当前节点的邻接节点入栈
stack.extend([adj_node for adj_node in self.graph[node] if adj_node not in visited])
# 广度优先遍历
def bfs(self, start):
visited = set() # 保存已访问过的节点
queue = [start] # 用队列来保存待访问的节点
while queue:
node = queue.pop(0) # 弹出首个节点
if node not in visited: # 如果节点未被访问过
print(node, end=" ") # 打印节点
visited.add(node)
# 将当前节点的邻接节点入队列
queue.extend([adj_node for adj_node in self.graph[node] if adj_node not in visited])
# 测试代码
if __name__ == "__main__":
g = Graph()
g.add_edge(0, [1, 2])
g.add_edge(1, [2])
g.add_edge(2, [0, 3])
g.add_edge(3, [3])
print("DFS Traversal:")
g.dfs(2)
print("\nBFS Traversal:")
g.bfs(2)
```
在上述代码中,定义了一个Graph类,并包含了添加边、深度优先遍历和广度优先遍历三个方法。通过调用add_edge方法,可以向图中添加边。在dfs方法中,采用栈的数据结构实现深度优先遍历;而在bfs方法中,采用队列的数据结构实现广度优先遍历。在测试代码部分,创建一个图对象g,并添加了几个边,然后分别进行深度优先遍历和广度优先遍历的测试。
阅读全文