数据结构算法求详细解

Question

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

Answer 1

对给定图进行邻接表表示，并利用队列和栈实现广度优先遍历和深度优先遍历的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