BFS和DFS相关知识汇总

对于深度优先搜索(DFS)、广度优先搜索(BFS)的代码实现一直都有困惑，今天看了相关算法的讲解，用python来实现一下BFS和DFS，并进行扩展，包括使用BFS对无权无向图求解最短路径，以及对带权无向图求解最短路径的Dijkstra算法（BFS的扩展）进行解读。

BFS与DFS基础

重点：对于BFS，使用队列queue来存储待访问的节点；对于DFS，使用栈stack来存储待访问的节点；

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

# graph 表示图的结构
# s 表示起始节点
def BFS(graph,s):
   queue = [] # 使用队列表示待访问的节点
   seen = set() # 使用集合来存储访问过的节点
   queue.append(s)
   seen.add(s)
   while len(queue)>0:
      vertex = queue.pop(0) # 对当前队列head的节点进行访问
      # 取当前队头节点的所有邻接点，对所有节点进行判断，如果之前没有访问过，则放入队列中等待下次访问
      nodes = graph[vertex] 
      for w in nodes:
         if w not in seen:
            queue.append(w)
            seen.add(w)
      print(vertex)

# graph 表示图的结构
# s 表示起始节点
def DFS(graph,s):
   stack = [] # 使用队列表示待访问的节点
   seen = set() # 使用集合来存储访问过的节点
   stack.append(s)
   seen.add(s)
   while len(stack)>0:
      vertex = stack.pop() # 对当前栈顶的节点进行访问
      # 取当前栈顶节点的所有邻接点，对所有节点进行判断，如果之前没有访问过，则放入栈中等待下次访问
      nodes = graph[vertex] 
      for w in nodes:
         if w not in seen:
            stack.append(w)
            seen.add(w)
      print(vertex)

BFS(graph,"A")
print('\n')
DFS(graph,"A")

无权无向图求解最短路径

使用BFS的思想，求每个节点的上一个节点所构成的parent字典，然后从终点往前搜索，直到起点位置，从而得到最终的最短路径。

分析：为什么基于BFS可以求解这个问题？因为当前图为无权图，所以要求起点到终点的最短路径，即起点到终点每走一步则跨过一层。因此我们的目标是去判断每个节点属于第几层。而BFS的思想就是一层一层的遍历图。而且每个节点都与上面一层的一个和几个节点连接，在BFS中访问过的节点就不重新访问，所以最终遍历时每个节点只有一个上层直接相连的节点，因此我们可以用dict来存储每个节点的上层节点，保存为parent，如果终点为“E”，则其上一个节点即为上一层，以此往上推，则可以达到起点，这种方式能够保证每次走一层，而不会在同一层走多次导致最终的结果不是最短路径。这就是BFS所隐含的效果。

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

# graph 表示图的结构
# s 表示起始节点
# 使用BFS的思想，来求解不带权边图的最短路径
def shortest_path(graph,s):
   queue = [] # 使用队列表示待访问的节点
   seen = set() # 使用集合来存储访问过的节点
   queue.append(s)
   seen.add(s)
   parent = {s:None}  # parent这个dict用来保存每个节点对应的上一个节点
   while len(queue)>0:
      vertex = queue.pop(0) # 对当前队列head的节点进行访问
      # 取当前队头节点的所有邻接点，对所有节点进行判断，如果之前没有访问过，则放入队列中等待下次访问
      nodes = graph[vertex]
      for w in nodes:
         if w not in seen:
            queue.append(w)
            seen.add(w)
            parent[w] = vertex
   return parent

parent = shortest_path(graph,"A")
for w in parent.keys():
   print(w,parent[w])
print('\n')

w = "E"
while w!=None:
   print(w)
   w = parent[w]

带权无向图求解最短路径（Dijkstra）

import heapq
import math

graph = {
    "A": {"B": 5, "C": 1},
    "B": {"A": 5, "C": 2, "D": 1},
    "C": {"A": 1, "B": 2, "D": 4, "E": 8},
    "D": {"B": 1, "C": 4, "E": 3, "F": 6},
    "E": {"C": 8, "D": 3},
    "F": {"D": 6}
}

def init_distance(graph, s):
    distance = {s: 0}
    for vertex in graph:
        if vertex != s:
            distance[vertex] = math.inf
    return distance

# 根据BFS的思想，当前图为带边权的无向图
# 使用priority queue，，每一层先选权重最小边进行访问
def Dijkstra(graph, s):
    # do something like BFS
    # 每次加入相邻点时，需要将边权定义为起始点到该点所经过边的权重和
    pqueue = []
    seen = set()
    heapq.heappush(pqueue, (0, s))
    parent = {s: None}
    distance = init_distance(graph, s)

    while len(pqueue) > 0:
        pair = heapq.heappop(pqueue)
        dist = pair[0]
        vertex = pair[1]
        # 由于优先队列中存在重复项，所以seen得在节点被拿出来之后才能加入seen中
        seen.add(vertex)
        nodes = graph[vertex].keys()
        for w in nodes:
            if w not in seen:
                if dist + graph[vertex][w] < distance[w]:
                    heapq.heappush(pqueue, (dist + graph[vertex][w], w))
                    parent[w] = vertex
                    distance[w] = dist + graph[vertex][w]
    return parent, distance

parent, distance = Dijkstra(graph, "A")
print(parent)
print(distance)