假设无向量连通图采用邻接表存储 设计一个python算法输出一棵深度优先的🌲
时间: 2024-03-27 08:36:35 浏览: 22
好的,我可以帮你设计一个 Python 算法来输出一棵深度优先搜索树。以下是代码实现:
```python
# Node 类用于表示图中的每个节点
class Node:
def __init__(self, name):
self.name = name
self.children = []
self.visited = False
# dfs 函数用于遍历图,并返回一个深度优先搜索树
def dfs(node, tree):
# 标记当前节点已被访问
node.visited = True
# 遍历当前节点的所有邻居节点
for neighbor in node.children:
if not neighbor.visited:
# 如果邻居节点未被访问,则将其添加到当前节点的子节点列表中,并递归调用 dfs 函数
child = Node(neighbor.name)
tree.children.append(child)
dfs(neighbor, child)
return tree
# 构建无向图
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
# 将图转换为邻接表表示
nodes = {}
for key in graph.keys():
node = Node(key)
nodes[key] = node
for key in graph.keys():
for neighbor in graph[key]:
nodes[key].children.append(nodes[neighbor])
# 从节点 A 开始进行深度优先搜索,并输出搜索树
root = Node("A")
tree = dfs(nodes["A"], root)
print("深度优先搜索树:")
print(tree.name)
for child in tree.children:
print("-" + child.name)
for grandchild in child.children:
print("--" + grandchild.name)
```
当你运行代码后,控制台将输出以下结果:
```
深度优先搜索树:
A
-B
--D
--E
-C
--F
```
这就是从节点 A 开始进行深度优先搜索得到的搜索树。