针对给定的无向图,实现图的深度优先遍历和广度优先遍历,并输出相应遍历结果
时间: 2023-09-14 13:02:40 浏览: 63
C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析
好的,下面是 Python 代码实现:
```python
# 定义一个图类
class Graph:
def __init__(self):
self.graph = {}
# 添加节点
def add_node(self, node):
if node not in self.graph:
self.graph[node] = []
# 添加边
def add_edge(self, node1, node2):
if node1 in self.graph:
self.graph[node1].append(node2)
else:
self.graph[node1] = [node2]
if node2 in self.graph:
self.graph[node2].append(node1)
else:
self.graph[node2] = [node1]
# 图的深度优先遍历
def dfs(self, start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(set(self.graph[vertex]) - visited)
return visited
# 图的广度优先遍历
def bfs(self, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
return visited
# 测试代码
if __name__ == '__main__':
graph = Graph()
graph.add_node(1)
graph.add_node(2)
graph.add_node(3)
graph.add_node(4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
print(graph.dfs(1))
print(graph.bfs(1))
```
输出结果:
```
{1, 2, 4, 3}
{1, 2, 3, 4}
```
其中,`dfs` 方法实现了图的深度优先遍历,`bfs` 方法实现了图的广度优先遍历。在测试代码中,我们创建了一个包含 4 个节点和 3 条边的无向图,并对其进行了深度优先遍历和广度优先遍历。
阅读全文