python dfs bfs

在Python中，DFS（深度优先搜索）和BFS（广度优先搜索）可以通过使用列表和字典来实现。在DFS中，我们使用栈来保存遍历的节点，而在BFS中，我们使用队列来保存节点。下面是一些Python代码示例：

1. BFS的实现：

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}

def BFS(graph, s):
    queue = []
    queue.append(s)
    seen = []
    seen.append(s)
    while len(queue) > 0:
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for node in nodes:
            if node not in seen:
                queue.append(node)
                seen.append(node)
        print(vertex)

BFS(graph, "A")

2. DFS的实现：

def DFS(graph, s):
    stack = []
    stack.append(s)
    seen = []
    seen.append(s)
    while len(stack) > 0:
        vertex = stack.pop()
        nodes = graph[vertex]
        for node in nodes:
            if node not in seen:
                stack.append(node)
                seen.append(node)
        print(vertex)

DFS(graph, "A")

对于BFS，我们还可以通过添加一个映射表（字典）来记录从起始点到其他所有点的路径。下面是一个对BFS的扩展，使用字典来记录父节点的信息，从而实现找到最短路径的功能：

def BFS(graph, s):
    queue = []
    queue.append(s)
    seen = []
    seen.append(s)
    parent = {s: None}
    while len(queue) > 0:
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for node in nodes:
            if node not in seen:
                queue.append(node)
                seen.append(node)
                parent[node = vertex
        print(vertex)
    return parent

parent = BFS(graph, "A")
v = "E"
while v != None:
    print(v)
    v = parent[v]

希望这些代码能够帮助你理解Python中的DFS和BFS算法。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [Python BFS和DFS算法](https://blog.csdn.net/qq_43540763/article/details/115144191)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]