python对图进行深度优先搜索遍历

Python具有内置的深度优先搜索算法，可以使用其递归实现。以下是一个简单的示例：

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'])
         }

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

dfs(graph, 'A')

上面的代码实现了从顶点'A'开始的深度优先遍历。输出顺序为：A, B, D, E, F, C。

请注意，此代码仅适用于无权图。如果图具有权重，则需要使用Dijkstra或A *等算法。

相关问题

数据结构对图进行深度优先遍历的代码

深度优先遍历（Depth First Search, DFS）是一种用于遍历或搜索树形数据结构和图的算法。在Python中，可以使用递归或栈来实现DFS。这里是一个基本的使用邻接列表表示无向图的DFS例子：

from collections import defaultdict

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    # 标记当前节点为已访问
    visited.add(start)
    print(f"Visiting {start}")

    # 遍历所有相邻的节点
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 使用邻接列表示图
graph = defaultdict(list)  # 例如: graph['A'] = ['B', 'C']
graph['B'] = ['D', 'E']
graph['C'] = ['F']
graph['D'] = []
graph['E'] = ['F']
graph['F'] = []

# 开始从'A'节点进行深度优先遍历
dfs(graph, 'A')

这个代码会按照“深”然后“广”的顺序访问图中的节点。如果你想要返回遍历的路径，而不是简单的打印，你可以稍微修改一下代码。

对图进行深度优先搜索和广度优先搜索遍历，并分别输出其遍历序列。用代码实现

假设我们的图用邻接表表示，其中节点编号从0开始，每个节点的相邻节点用列表存储。例如，对于如下的图:

0----1
|\  / |
| \/  |
| /\  |
|/  \ |
2----3

其邻接表表示为:

adj = [[1, 2],
       [0, 2, 3],
       [0, 1, 3],
       [1, 2]]

深度优先搜索遍历的思路是从起始节点开始，依次遍历其相邻节点，并递归地遍历这些相邻节点的相邻节点，直到找到所有可达节点。广度优先搜索遍历的思路是从起始节点开始，依次遍历其相邻节点，并将这些相邻节点加入一个队列中，然后从队列中取出下一个节点继续遍历其相邻节点，直到找到所有可达节点。

下面是实现深度优先搜索遍历和广度优先搜索遍历的Python代码：

def dfs(adj, visited, node, traversal):
    visited[node] = True
    traversal.append(node)
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs(adj, visited, neighbor, traversal)

def bfs(adj, start):
    visited = [False] * len(adj)
    queue = [start]
    visited[start] = True
    traversal = []
    while queue:
        node = queue.pop(0)
        traversal.append(node)
        for neighbor in adj[node]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True
    return traversal

# 测试
adj = [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
visited = [False] * len(adj)
traversal = []
dfs(adj, visited, 0, traversal)
print(traversal)  # 输出: [0, 1, 2, 3]

traversal = bfs(adj, 0)
print(traversal)  # 输出: [0, 1, 2, 3]

其中，`dfs`函数实现了深度优先搜索遍历，`bfs`函数实现了广度优先搜索遍历。`visited`数组用于记录每个节点是否已经被访问过，`traversal`数组用于存储遍历序列。在`dfs`函数中，我们首先将当前节点标记为已访问，并加入遍历序列中。然后递归地遍历该节点的相邻节点，如果某个相邻节点未被访问，则继续递归遍历该节点。在`bfs`函数中，我们使用队列来存储待访问的节点。首先将起始节点加入队列中，并标记为已访问。然后从队列中取出下一个节点，将其加入遍历序列中，并遍历该节点的相邻节点，将未访问的相邻节点加入队列中。重复该过程，直到队列为空。

以上代码中，我们以节点0为起始节点进行遍历，输出了深度优先搜索遍历和广度优先搜索遍历的结果。