BFS

1.PNG

  1. //BFS
  2. graph = {
  3.     "A": ["B", "C"],
  4.     "B": ["A", "C", "D"],
  5.     "C": ["A", "B", "D", "E"],
  6.     "D": ["B", "C", "E", "F"],
  7.     "E": ["C", "D"],
  8.     "F": ["D"]
  9. }
  11. def BFS(graph, s):
  12.     queue = []
  13.     queue.append(s)
  14.     seen = set()
  15.     seen.add(s)
  16.     while (len(queue) > 0):
  17.         vertex = queue.pop(0)
  18.         nodes = graph[vertex]
  19.         for w in nodes:
  20.             if w not in seen:
  21.                 queue.append(w)
  22.                 seen.add(w)
  23.         print(vertex)

111.png

DFS

  1. //DFS
  2. graph = {
  3.     "A": ["B", "C"],
  4.     "B": ["A", "C", "D"],
  5.     "C": ["A", "B", "D", "E"],
  6.     "D": ["B", "C", "E", "F"],
  7.     "E": ["C", "D"],
  8.     "F": ["D"]
  9. }
  11. def DFS(graph, s):
  12.     stack = []
  13.     stack.append(s)
  14.     seen = set()
  15.     seen.add(s)
  16.     while (len(stack) > 0):
  17.         vertex = stack.pop()
  18.         nodes = graph[vertex]
  19.         for w in nodes:
  20.             if w not in seen:
  21.                 stack.append(w)
  22.                 seen.add(w)
  23.         print(vertex)
  25. DFS(graph, "A")

111.png

最短路径

  1. graph = {
  2.     "A": ["B", "C"],
  3.     "B": ["A", "C", "D"],
  4.     "C": ["A", "B", "D", "E"],
  5.     "D": ["B", "C", "E", "F"],
  6.     "E": ["C", "D"],
  7.     "F": ["D"]
  8. }
  10. def BFS(graph, s):
  11.     queue = []
  12.     queue.append(s)
  13.     seen = set()
  14.     seen.add(s)
  15.     parent = {s : None}
  16.     while (len(queue) > 0):
  17.         vertex = queue.pop(0)
  18.         nodes = graph[vertex]
  19.         for w in nodes:
  20.             if w not in seen:
  21.                 queue.append(w)
  22.                 seen.add(w)
  23.                 parent[w] = vertex
  24.         print(vertex)
  25.     return parent
  27. parent = BFS(graph, "E")
  28. //打印出路径映射表
  29. for key in parent:
  30.     print(key, parent[key])
  32. //如何从B走到E 
  33. v = "B"
  34. while v != None:
  35.     print(v)
  36.     v = parent[v]

111.png

Dijkstra算法

  1. import heapq
  2. import math
  4. graph = {
  5.     "A": {"B": 5, "C": 1},
  6.     "B": {"A": 5, "C": 2, "D": 1},
  7.     "C": {"A": 1, "B": 2, "D": 4, "E": 8},
  8.     "D": {"B": 1, "C": 4, "E": 3, "F": 6},
  9.     "E": {"C": 8, "D": 3},
  10.     "F": {"D": 6},
  11. }
  13. def init_distance(graph, s):
  14.     distance = {s: 0}
  15.     for vertex in graph:
  16.         if vertex != s:
  17.             distance[vertex] = math.inf
  18.     return distance
  20. def dijkstra(graph, s):
  21.     pqueue = []
  22.     heapq.heappush(pqueue, (0, s))
  23.     seen = set()
  24.     parent = {s : None}
  25.     distance = init_distance(graph, s)
  27.     while (len(pqueue) > 0):
  28.         pair = heapq.heappop(pqueue)
  29.         dist = pair[0]
  30.         vertex = pair[1]
  31.         seen.add(vertex)
  32.         nodes = graph[vertex].keys()
  33.         for w in nodes:
  34.             if w not in seen:
  35.                 if dist + graph[vertex][w] < distance[w]:
  36.                     heapq.heappush(pqueue, (dist + graph[vertex][w], w))
  37.                     parent[w] = vertex
  38.                     distance[w] = dist + graph[vertex][w]
  39.                 parent[w] = vertex
  40.     return parent, distance
  42. parent, distance = dijkstra(graph, "A")
  43. print(parent)
  44. print(distance)

111.png

参考：

https://www.bilibili.com/video/BV1Ks411575U/?spm_id_from=333.788.recommend_more_video.-1