无向图的深度优先遍历和广度优先遍历

以下是无向图的深度优先遍历和广度优先遍历的介绍和演示：

1.深度优先遍历（DFS）：
深度优先遍历是一种用于遍历或搜索树或图的算法。在这种搜索方法中，从根结点开始，尽可能深地搜索每个分支，直到找到目标值或无法继续为止。然后回溯到前一个结点，尝试另一条分支，直到所有结点都被访问为止。

以下是一个无向图的深度优先遍历的Python代码示例：

# 无向图的深度优先遍历
def DFS(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next in graph[start] - visited:
        DFS(graph, next, 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'])}

# 从顶点A开始遍历
print("深度优先遍历结果：")
DFS(graph, 'A')

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

2.广度优先遍历（BFS）：
广度优先遍历是一种用于遍历或搜索树或图的算法。在这种搜索方法中，从根结点开始，逐层遍历每个分支，直到找到目标值或无法继续为止。

以下是一个无向图的广度优先遍历的Python代码示例：

# 无向图的广度优先遍历
def BFS(graph, start):
    visited, queue = set(), [start]
    visited.add(start)
    while queue:
        vertex = queue.pop(0)
        print(vertex, end=' ')
        for next in graph[vertex] - visited:
            visited.add(next)
            queue.append(next)

# 无向图的邻接表表示
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'])}

# 从顶点A开始遍历
print("广度优先遍历结果：")
BFS(graph, 'A')

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