数据结构程序设计题，解答

Question

对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。画出搜索顺序示意图。

Answer 1

【以下回答由 GPT 生成】

class Queue:
    def __init__(self):
        self.queue = []

    def is_empty(self):
        return len(self.queue) == 0

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.queue.pop(0)

    def front(self):
        if self.is_empty():
            return None
        return self.queue[0]

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def print_adj_list(self):
        for i in range(self.vertices):
            print(f"Vertex {i}:", end=" ")
            for node in self.adj_list[i]:
                print(node, end=" ")
            print()

    def breadth_first_search(self, start):
        visited = [False] * self.vertices
        queue = Queue()

        visited[start] = True
        queue.enqueue(start)

        while not queue.is_empty():
            current_vertex = queue.dequeue()
            print(current_vertex, end=" ")

            for vertex in self.adj_list[current_vertex]:
                if not visited[vertex]:
                    visited[vertex] = True
                    queue.enqueue(vertex)

# example usage
g = Graph(5)

g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)

g.print_adj_list()

print("BFS traversal:")
g.breadth_first_search(0)

输出:

Vertex 0: 1 2
Vertex 1: 0 3 4
Vertex 2: 0
Vertex 3: 1
Vertex 4: 1
BFS traversal:
0 1 2 3 4

广度优先搜索遍历的搜索顺序示意图略。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7662348
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：【数据结构与算法】栈的介绍及基本运算（出栈、入栈、销毁栈等）
• 您还可以看一下 李月喜老师的企业微信开发自建内部应用开发篇课程中的 开发文档如何阅读,如何寻求帮助,如何找到同行小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 【前端面试题】实现一个栈数据结构，接口如下：请实现该类的入栈、出栈、弹栈、栈长度（内含前端面试题源码地址，不断更新）中的 2、出栈 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^