015图.md

实现图数据结构

什么是图

图是类似树这样的数据结构，与树不同的是它可以没有根节点，而且根据类型不同可分为有向图和无向图等。

在现实中可能存在这样的图，满足以下条件。

A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C

这样的图用Python可以使用字典来表达这样的数据结构，如{A: [B, C], B: [C, D], C: [D], D: [C], E: [F], F: [C]}。

如何实现图

要实现图的遍历等功能，以上面的图为例，我们首先要定义数据结构和函数。因为要递归实现，我们需要把start、end传进去，而且还要给历史走过的path。

def find_path(graph, start, end, path=[]):
  pass

def find_all_paths(graph, start, end, path=[]):
  pass

def find_shortest_path(graph, start, end, path=[]):
  pass

graph = {'a':['b', 'c'], 'b': ['c', 'd'], 'c': ['d'], 'd': ['c'], 'e': ['f'], 'f': ['c']}

首先我们来实现find_path函数，用到了回溯法，从起点开始，如果起点就是终点那先返回，然后遍历每个子节点，注意要确保不是环路而且找了非空的路径才返回。

def find_path(graph, start, end, path=[]):
  path = path + [start]

  if start == end:
    return [path]

  for node in graph[start]:
    if node not in path:
      new_path = find_path(graph, node, end, path)
      if new_path:
        return new_path

graph = {'a':['b', 'c'], 'b': ['c', 'd'], 'c': ['d'], 'd': ['c'], 'e': ['f'], 'f': ['c']}
print(find_path(graph, 'a', 'd'))
# Print [['a', 'b', 'c', 'd']]

然后我们来实现find_all_paths函数，

def find_all_paths(graph, start, end, path=[]):
  path = path + [start]

  if start == end:
    return [path]

  all_paths = []
  for node in graph[start]:
    if node not in path:
      new_paths = find_all_paths(graph, node, end, path)
      for new_path in new_paths:
        all_paths.append(new_path)

  return all_paths

graph = {'a':['b', 'c'], 'b': ['c', 'd'], 'c': ['d'], 'd': ['c'], 'e': ['f'], 'f': ['c']}
print(find_all_paths(graph, 'a', 'd'))
# Print [['a', 'b', 'c', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd']]

最后来实现获取最短路径。

def find_shortest_path(graph, start, end, path=[]):
  path = path + [start]

  if start == end:
    return path

  result_path = None
  for node in graph[start]:
    if node not in path:
      new_path = find_shortest_path(graph, node, end, path)
      if result_path == None:
        result_path = new_path
      elif len(result_path) > len(new_path):
        result_path = new_path

  return result_path

graph = {'a':['b', 'c'], 'b': ['c', 'd'], 'c': ['d'], 'd': ['c'], 'e': ['f'], 'f': ['c']}
print(find_shortest_path(graph, 'a', 'd'))
# Print ['a', 'b', 'd']

这是本章内容，希望对你有所帮助。进入下一章