小小陈11 2023-02-21 08:47 采纳率: 50%
浏览 29
已结题

数据结构算法求详细解

5、对任意给定的图(顶点数和边数自定),建立它的邻接表并输出,利用队列的基本运算实现图的广度优先遍历;利用栈的基本运算实现图的深度优先遍历;从键盘输入初始出发的顶点的序号,要求在遍历过程中输出访问过的结点序号。

  • 写回答

3条回答 默认 最新

  • 答主 2023-02-21 10:11
    关注

    对给定图进行邻接表表示,并利用队列和栈实现广度优先遍历和深度优先遍历的Python代码实现。同时,程序还支持从键盘输入初始出发的顶点序号,并在遍历过程中输出访问过的结点序号

    from collections import defaultdict, deque
    
    class Graph:
        def __init__(self, vertices):
            self.graph = defaultdict(list)
            self.vertices = vertices
    
        def add_edge(self, u, v):
            self.graph[u].append(v)
    
        def print_graph(self):
            for vertex in self.graph:
                print(vertex, "->", " -> ".join(str(i) for i in self.graph[vertex]))
    
        def bfs(self, start_vertex):
            visited = [False] * self.vertices
            queue = deque()
    
            visited[start_vertex] = True
            queue.append(start_vertex)
    
            while queue:
                start_vertex = queue.popleft()
                print(start_vertex, end=" ")
    
                for vertex in self.graph[start_vertex]:
                    if not visited[vertex]:
                        visited[vertex] = True
                        queue.append(vertex)
    
        def dfs(self, start_vertex):
            visited = [False] * self.vertices
            stack = []
    
            visited[start_vertex] = True
            stack.append(start_vertex)
    
            while stack:
                start_vertex = stack.pop()
                print(start_vertex, end=" ")
    
                for vertex in self.graph[start_vertex]:
                    if not visited[vertex]:
                        visited[vertex] = True
                        stack.append(vertex)
    
        def traverse(self):
            start_vertex = int(input("Enter the starting vertex: "))
            print("BFS traversal: ")
            self.bfs(start_vertex)
            print("\nDFS traversal: ")
            self.dfs(start_vertex)
    
    
    # Create a sample graph
    g = Graph(5)
    g.add_edge(0, 1)
    g.add_edge(0, 4)
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(1, 4)
    g.add_edge(2, 3)
    g.add_edge(3, 4)
    
    # Print the graph
    g.print_graph()
    
    # Traverse the graph
    g.traverse()
    
    
    

    输出

    0 -> 1 -> 4
    1 -> 2 -> 3 -> 4
    2 -> 3
    3 -> 4
    Enter the starting vertex: 0
    BFS traversal: 
    0 1 4 2 3 
    DFS traversal: 
    0 4 1 3 2 
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 3月3日
  • 已采纳回答 2月23日
  • 创建了问题 2月21日

悬赏问题

  • ¥15 为啥快手广告联盟的广告这么难出来
  • ¥15 k8s集群重启后,kubelet一直报systemctl restart kubelet.service "Failed to delete cgroup paths"
  • ¥15 微信小程序构建工具类发布到npm,install后报错
  • ¥15 amesim液压仿真问题
  • ¥15 MATLAB优化设计
  • ¥15 ANN预测模型 200大米
  • ¥20 优秀学生的问题 oj java
  • ¥15 scratch-gui 如何集成进 react native
  • ¥15 把全局悬浮窗改为局内悬浮窗
  • ¥15 Excel vba编程调用word如何读取换行符