深度优先搜索与广度优先搜索

深度优先搜索（DFS）和广度优先搜索（BFS）都是图搜索算法，用于在图中查找特定节点或路径。两者的主要区别在于搜索的方式不同。

深度优先搜索从起点开始，沿着一条路径一直向下搜索，直到无法继续为止，然后回溯到前一个节点，继续搜索下一条路径，直到找到目标节点或遍历完整个图。深度优先搜索通常使用栈或递归实现。

广度优先搜索从起点开始，先访问起点的所有邻居节点，然后访问邻居节点的邻居节点，以此类推，直到找到目标节点或遍历完整个图。广度优先搜索通常使用队列实现。

下面是两个Python实现的例子：

1.深度优先搜索

def dfs(graph, start, end):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node == end:
            return True
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node] - visited)
    return False

# 示例
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

print(dfs(graph, 'A', 'F')) # 输出：True

2.广度优先搜索

from collections import deque

def bfs(graph, start, end):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == end:
            return True
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node] - visited)
    return False

# 示例
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

print(bfs(graph, 'A', 'F')) # 输出：True