编程实现图的深度优先和广度优先搜索遍历两种算法（邻接矩阵和邻接表两种存储方式任选其一）

深度优先搜索遍历算法：

邻接矩阵存储方式：

1. 从起点开始，将其标记为已访问。
2. 遍历起点的所有邻居节点，如果邻居节点未被访问，则递归访问该邻居节点。
3. 重复步骤2，直到所有节点都被访问。

邻接表存储方式：

1. 从起点开始，将其标记为已访问，并将其加入栈中。
2. 从栈中取出一个节点，遍历该节点的所有邻居节点，如果邻居节点未被访问，则将其标记为已访问，并将其加入栈中。
3. 重复步骤2，直到栈为空。

广度优先搜索遍历算法：

邻接矩阵存储方式：

1. 从起点开始，将其标记为已访问，并将其加入队列中。
2. 从队列中取出一个节点，遍历该节点的所有邻居节点，如果邻居节点未被访问，则将其标记为已访问，并将其加入队列中。
3. 重复步骤2，直到队列为空。

邻接表存储方式：

1. 从起点开始，将其标记为已访问，并将其加入队列中。
2. 从队列中取出一个节点，遍历该节点的所有邻居节点，如果邻居节点未被访问，则将其标记为已访问，并将其加入队列中。
3. 重复步骤2，直到队列为空。

相关问题

.分别采用邻接表实现图的深度优先与广度优先遍历算法。 2.采用邻接矩阵实现图的广度优先遍历和深度优先遍历算法。（1）用简单示例结合所设计算法采用的数据逻辑结构图、存储结构图说明算法思想。

1. **采用邻接表实现图的深度优先遍历(Depth-First Search, DFS)与广度优先遍历(Breadth-First Search, BFS)**:

- **深度优先遍历**:
邻接表非常适合DFS，因为我们可以从每个顶点出发直接访问其相邻顶点。基本思路是选择一个未访问的顶点，并标记为已访问，然后递归地访问其邻居。对于DFS，通常会使用栈来模拟递归过程：
- 初始化：将起点加入队列并标记为已访问。
- 循环：取出队首节点，访问它并将其所有未访问的邻居压入栈中。
- 结束：直到队列为空，表示所有路径都已探索。

- **广度优先遍历**:
邻接表同样能支持BFS，但由于BFS需要按层次顺序访问，我们会用到队列而不是栈。步骤如下：
- 初始化：将起点加入队列，同时创建一个记录每个顶点被访问时间的集合。
- 循环：每次从队列头部取出一个顶点，访问并标记为已访问。然后将该顶点的所有未访问邻居加入队列。
- 结束：直到队列为空，所有节点都被访问过。

2. **采用邻接矩阵实现图的广度优先遍历与深度优先遍历**:
- **广度优先遍历（BFS）**:
使用邻接矩阵，我们可以在常数时间内检查两个顶点是否相连。BFS从起点开始，逐层扩展，每次都先访问当前层的所有节点。矩阵存储了节点间的直接连接，用二维数组或邻接矩阵中的值判断是否放入队列。
- **深度优先遍历（DFS）**:
在邻接矩阵中，由于需要查找邻居，虽然不是O(1)，但比邻接表稍慢。尽管如此，仍可通过邻接矩阵实现，只是访问路径不会像邻接表那样形成自然的“深度”结构，而是需要借助额外的数据结构（如递归堆栈或递归函数）。

举例说明：
数据逻辑结构图（无向图）可以看作是节点（数字）之间的联系，而邻接矩阵就是每个节点对的连线状态；存储结构图则是如何在矩阵中组织这些信息。
- 对于DFS，假设矩阵是这样的：

0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0

从节点1开始，我们用栈来跟踪路径：1 -> 2 -> 4 (或3)。

- 对于BFS，初始时，起点1入队，然后依次出队处理，记录节点及其层级，例如：

1 (0)
2 (1)
3 (1)
4 (1)

继续添加邻居，直到队列为空，所有节点都被访问过。

对给定图，实现图的深度优先遍历和广度优先遍历。以邻接表或邻接矩阵为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列，并调试算法。

在图论中，深度优先遍历（Depth-First Search，DFS）和广度优先遍历（Breadth-First Search，BFS）是非常常见的两种搜索算法。以下是基于邻接表和邻接矩阵这两种常见数据结构的实现：

**邻接表存储结构：**

class Graph:
    def __init__(self):
        self.vertices = {}
    
    # DFS实现
    def dfs(self, start_node):
        visited = set()
        stack = [start_node]
        
        while stack:
            node = stack.pop()
            if node not in visited:
                print(node, end=" -> ")
                visited.add(node)
                
                for neighbor in self.vertices[node]:
                    if neighbor not in visited:
                        stack.append(neighbor)
            
    # BFS实现
    def bfs(self, start_node):
        visited = set()
        queue = [start_node]
        
        while queue:
            node = queue.pop(0)
            if node not in visited:
                print(node, end=" -> ")
                visited.add(node)
                
                for neighbor in self.vertices[node]:
                    if neighbor not in visited:
                        queue.append(neighbor)

**邻接矩阵存储结构：**

class AdjacencyMatrixGraph:
    def __init__(self, num_vertices):
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
        
    # DFS和BFS实现与邻接表版本类似，只是获取邻居的方式不同
    def dfs_matrix(self, start_node):
        # ... (同上，但通过索引来查找邻居)

    def bfs_matrix(self, start_node):
        # ... (同上，但通过索引来查找邻居)

为了调试算法，可以添加一些边界条件检查和异常处理，例如检查输入节点是否存在、循环检测等。运行遍历时，观察输出的结点访问序列是否符合预期，并记录每次遍历的时间性能。