基于 BFS 算法的图的遍历问题求解 进行类的设计与实现，解决图的遍历问题。具体要求如下： （1）采用图的邻接短阵或邻接表实现最短路径问题中图的存储; （2）采用队列实现图的广度优先搜索 (BFS)； (3） 在图形界面类上编写一个测试该类的程序。

在基于BFS算法解决图的遍历问题时，首先我们需要设计一个表示图的数据结构。可以选择邻接矩阵或邻接表作为基础：

**邻接矩阵**：
- 图的每个节点用一个二维数组表示，行代表起点，列表示终点，值表示边的存在与否（通常是1表示有边，0表示无边）。

**邻接表**：
- 每个节点包含一个链接到其相邻节点的列表，通过链表结构节省空间，适用于稀疏图。

然后，我们将实现一个`BFS`类，其中包含以下关键方法：
- `__init__(self, graph)`：初始化方法，接受邻接矩阵或邻接表形式的图输入。
- `bfs(start_node)`：从给定的起始节点开始，执行广度优先搜索。这个函数会维护一个队列，将当前节点、前驱节点和未访问节点添加进去，直到找到目标节点或者遍历完整个图。
- `shortest_path(start_node, end_node)`：利用BFS计算从start_node到end_node的最短路径，返回经过的节点序列。

为了在图形界面类上测试BFS类，我们可以创建一个简单的用户界面，提供以下功能：
- 输入或选择起始和结束节点。
- 调用`shortest_path`方法并显示结果。
- 显示搜索过程中的状态更新。

下面是一个简化版的伪代码展示如何实现这个方案：

class Graph:
    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

class BFS:
    def __init__(self, graph):
        self.graph = graph

    def bfs(self, start_node):
        visited = set()
        queue = [(start_node, [])]
        while queue:
            node, path = queue.pop(0)
            if node not in visited:
                visited.add(node)
                path.append(node)
                for neighbor in self.graph[node]:
                    if neighbor not in visited:
                        queue.append((neighbor, path.copy()))

    def shortest_path(self, start_node, end_node):
        # 使用bfs并记录路径
        ...

class GraphUI:
    def main(self):
        graph = ...  # 初始化图
        bfs_instance = BFS(graph)
        start_node = input("Enter start node:")
        end_node = input("Enter end node:")
        result = bfs_instance.shortest_path(start_node, end_node)
        print(f"Shortest path from {start_node} to {end_node}: {result}")

# 示例运行
ui = GraphUI()
ui.main()