盲目搜索验证性实验实操

一、实验目的

1. 掌握 广度优先搜索（BFS） 和 深度优先搜索（DFS） 的基本原理。
2. 编程实现 BFS、递归 DFS、非递归 DFS 三种搜索算法。
3. 在固定无权图上验证算法执行结果，对比路径差异。
4. 理解 BFS 能找到最短路径、DFS 不保证最短路径的原因。

---

二、实验环境

• 操作系统：Windows 10/11
• 编程语言：Python 3.8 及以上
• 开发工具：PyCharm / VS Code / IDLE
• 数据结构：图的邻接表表示

---

三、实验原理

1. BFS（广度优先搜索）

   • 使用 队列（FIFO）
   • 按层次遍历，先访问邻居，再下一层
   • 一定能找到无权图的最短路径

2. DFS（深度优先搜索）

   • 使用 栈（LIFO） 或递归
   • 一条路走到头再回溯
   • 不保证最短路径

---

四、实验用图结构

测试图：无权无向图（新增冗余路径，制造非最短路径场景）

节点：A、B、C、D、E、F、G、H
边：(A,B)、(A,D)、(B,C)、(B,E)、(C,G)、(G,H)、(H,F)、(D,E)、(E,F)

Markdown 图解

         A
        / \
       B   D
      / \ / 
     C   E — F
    /      /
   /      /
  G ——— H

邻接表（参考）

节点	相邻节点
A	B, D
B	A, C, E
C	B, G
D	A, E
E	B, D, F
F	E, H
G	C, H
H	G, F

---

五、实验步骤

步骤 1：搭建图结构

1. 新建 Python 文件
2. 输入图类代码，实现邻接表与加边功能
3. 构建本次实验修改后的测试图（新增 G、H 节点和冗余路径）

步骤 2：实现 BFS 算法

1. 使用队列 deque
2. 记录已访问节点
3. 输出从起点到目标点的路径

步骤 3：实现 DFS 算法

1. 实现递归 DFS
2. 实现非递归 DFS（栈实现）

步骤 4：运行测试（起点 A，终点 F）

步骤 5：填写实验结果表格 （学生完成）

步骤 6：分析实验结果（学生完成）

步骤 7：完成实验总结（学生完成）

---

六、完整实验代码（提供截图粘贴，代码可参考，重点是后续问题的回答）

from collections import deque

# 图类
class Graph:
    def __init__(self):
        self.adj = {}

    def add_edge(self, u, v):
        if u not in self.adj:
            self.adj[u] = []
        if v not in self.adj:
            self.adj[v] = []
        self.adj[u].append(v)
        self.adj[v].append(u)

# ---------------- BFS ----------------
def bfs(graph, start, goal):
    visited = set()
    q = deque()
    q.append((start, [start]))
    visited.add(start)

    while q:
        node, path = q.popleft()
        for neighbor in graph.adj[node]:
            if neighbor == goal:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                q.append((neighbor, path + [neighbor]))
    return None

# ---------------- 递归 DFS ----------------
def dfs_recursive(graph, start, goal):
    visited = set()

    def dfs(node, path):
        if node == goal:
            return path
        visited.add(node)
        # 不逆序，保持自然遍历顺序，确保深度优先走长路径
        for neighbor in graph.adj[node]:
            if neighbor not in visited:
                res = dfs(neighbor, path + [neighbor])
                if res:
                    return res
        return None

    return dfs(start, [start])

# ---------------- 非递归 DFS ----------------
def dfs_iterative(graph, start, goal):
    stack = [(start, [start])]
    visited = set()

    while stack:
        node, path = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        if node == goal:
            return path
        # 不逆序，放大栈"后进先出"特性，制造不同路径
        for neighbor in graph.adj[node]:
            if neighbor not in visited:
                stack.append((neighbor, path + [neighbor]))
    return None

# ================== 测试主程序 ==================
if __name__ == "__main__":
    g = Graph()
    # 修改后的边集合，新增G、H节点和冗余路径
    edges = [
        ('A','B'), ('A','D'),
        ('B','C'), ('B','E'),
        ('C','G'), ('G','H'), ('H','F'),  # 新增的长路径
        ('D','E'), ('E','F')              # 最短路径
    ]
    for u, v in edges:
        g.add_edge(u, v)

    print("===== 搜索结果 A → F =====")
    print("BFS 路径：", bfs(g, 'A', 'F'))
    print("递归 DFS 路径：", dfs_recursive(g, 'A', 'F'))
    print("非递归 DFS 路径：", dfs_iterative(g, 'A', 'F'))

---

七、实验结果记录表

表 1：A → F 搜索结果 ❓

算法	搜索路径	路径节点数	是否最短路径
BFS
递归 DFS
非递归 DFS

表 2：A → E 搜索结果 ❓

算法	搜索路径	路径节点数	是否最短路径
BFS
递归 DFS
非递归 DFS

---

八、实验结果分析

1. BFS 为什么一定是最短路径？❓

2. DFS 为什么不一定是最短路径？❓

3. 递归 DFS 和非递归 DFS 路径为什么不一样？❓

4. 本次实验中 BFS 和 DFS 的区别总结：❓

---

九、实验总结

1. 实验收获：❓

2. 遇到的问题：❓

3. 解决方法：❓