编写支持图的DFS、BFS遍历及交互式选择的程序需求

我来帮你搞定这个支持DFS和BFS的交互式图遍历程序，完全贴合你的需求。下面是完整的Python实现代码和详细说明：

核心功能说明 #

这个程序会提供你要的5个交互选项：

• 1. 执行深度优先遍历：询问目标图后输出DFS节点访问顺序
• 2. 执行广度优先遍历：询问目标图后输出BFS节点访问顺序
• 3. 直接对图1执行DFS搜索
• 4. 直接对图2执行BFS搜索
• 5. 退出程序

完整代码实现 #

# 定义示例图（邻接表形式，你可以根据需求修改图结构）
graphs = {
    "图1": {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    },
    "图2": {
        '1': ['2', '3'],
        '2': ['1', '4'],
        '3': ['1', '5', '6'],
        '4': ['2'],
        '5': ['3'],
        '6': ['3']
    }
}

def dfs(graph, start_node=None):
    """深度优先遍历函数，默认从图的第一个节点开始"""
    if start_node is None:
        start_node = next(iter(graph.keys()))
    visited = set()
    stack = [start_node]
    traversal_order = []
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            # 逆序入栈，保证遍历顺序和递归版本一致（可选，去掉reversed就是另一种顺序）
            stack.extend(reversed(graph[node]))
    return traversal_order

def bfs(graph, start_node=None):
    """广度优先遍历函数，默认从图的第一个节点开始"""
    if start_node is None:
        start_node = next(iter(graph.keys()))
    visited = set()
    queue = [start_node]
    traversal_order = []
    
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            queue.extend(graph[node])
    return traversal_order

def interactive_menu():
    """交互式菜单函数，处理用户输入和逻辑分支"""
    while True:
        print("\n=== 图遍历程序菜单 ===")
        print("1. 执行深度优先遍历（DFS）")
        print("2. 执行广度优先遍历（BFS）")
        print("3. 对图1执行DFS搜索")
        print("4. 对图2执行BFS搜索")
        print("5. 退出")
        
        choice = input("请输入你的选择（1-5）：")
        
        if choice == '1':
            graph_name = input("请输入目标图（图1/图2）：")
            if graph_name in graphs:
                order = dfs(graphs[graph_name])
                print(f"图{graph_name}的DFS遍历顺序：{' -> '.join(order)}")
            else:
                print("无效的图名称，请输入「图1」或「图2」！")
        elif choice == '2':
            graph_name = input("请输入目标图（图1/图2）：")
            if graph_name in graphs:
                order = bfs(graphs[graph_name])
                print(f"图{graph_name}的BFS遍历顺序：{' -> '.join(order)}")
            else:
                print("无效的图名称，请输入「图1」或「图2」！")
        elif choice == '3':
            order = dfs(graphs["图1"])
            print(f"图1的DFS遍历顺序：{' -> '.join(order)}")
        elif choice == '4':
            order = bfs(graphs["图2"])
            print(f"图2的BFS遍历顺序：{' -> '.join(order)}")
        elif choice == '5':
            print("程序退出，再见！")
            break
        else:
            print("无效的选择，请输入1-5之间的数字！")

# 启动程序
if __name__ == "__main__":
    interactive_menu()

使用说明 #

1. 自定义图结构：如果你想用自己的图，直接修改graphs字典里的内容就行，保持邻接表的格式（键是节点，值是该节点的相邻节点列表）
2. 遍历起点：默认从图的第一个节点开始遍历，如果需要指定起点，可以给dfs或bfs函数传start_node参数（比如dfs(graphs["图1"], start_node='B')）
3. 交互逻辑：运行程序后，按照菜单提示输入数字即可，所有输入都会做合法性校验，不用担心误操作

内容的提问来源于stack exchange，提问作者Rems