深度优先和广度优算法

深度优先搜索（DFS）和广度先搜索（BFS）是图论中的两个基本算法，用于遍历或搜索图的节点。下面是它们的介绍和演示：

1. 深度优先搜索（DFS）：从图的某个顶点开始遍历，沿着一条路径遍历到底，直到不能再继续为止，然后回溯到前一个节点，沿着另一条路径继续遍历，直到所有节点都被访问为止。DFS通常使用递归实现。

下面是一个简单的DFS实现，以邻接表形式存储图：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next_node in graph[start] - visited:
        dfs(graph, next_node, visited)
    return visited

# 示例
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'])}
dfs(graph, 'A')

输出结果为：A B D E F C

2. 广度优先搜索（BFS）：从图的某个顶点开始遍历，先访问它的所有邻居节点，然后依次访问它们的邻居节点，直到所有节点都被访问为止。BFS通常使用队列实现。

下面是一个简单的BFS实现，以邻接表形式存储图：

from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        for next_node in graph[vertex] - visited:
            visited.add(next_node)
            queue.append(next_node)

# 示例
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'])}
bfs(graph, 'A')

输出结果为：A B C D E F