程序世界里,有很多的数据结构,比如:堆、栈、链表等等,今天要讲的就是图数据结构啦。
相信大家都使用过或者听说过图数据库吧,我们就来看看最简单的图数据结构算法。
首先先来看一下图长什么样
从上图能看出,比如节点A可以到达C、D、B,节点B只能到达E。
ok,这就是最基本的了,接下来来了解下游戏规则,我们需要列出所有可能的路径,比如:列出A到E的所有路径。
而在代码里,我们可能需要首先通过 字典+列表 的方式给出路径的设计,比如:
Graph = {'A': ['B', 'C', 'D'],
'B': ['E'],
'C': ['D', 'F'],
'D': ['B', 'E', 'G'],
'E': [],
'F': ['D', 'G'],
'G': ['E']}
在接下来,我们需要告诉程序,我们需要从哪里开始,走到哪里去,也就是常说的起始点和终点。
search_graph(Graph, 'A', 'E')
让我们来看下完整的代码吧:def search_graph(graph: dict, start, end):
_ret = []
generate_path(graph, [start], end, _ret)
# 这一步的排序可有可无,只不过为了显示好看
_ret.sort(key=lambda x: len(x))
return _ret
def generate_path(graph: dict, path, end, ret: list):
_state = path[-1]
# 如果起始点和终点是同一个位置,则结束
if _state == end:
ret.append(path)
else:
for _item in graph[_state]:
if _item not in path:
# path + [_item] 就是递归调用的关键参数,path的组成
generate_path(graph, path + [_item], end, ret)
if __name__ == '__main__':
_GRAPH = {'A': ['B', 'C', 'D'],
'B': ['E'],
'C': ['D', 'F'],
'D': ['B', 'E', 'G'],
'E': [],
'F': ['D', 'G'],
'G': ['E']}
_ret = search_graph(_GRAPH, 'A', 'E')
print("******************")
print(' path A to E')
print("******************")
for i in _ret:
print(i)
结果如下图:
主要的逻辑,大家可以拿张纸出来画画。
好啦,今天的内容就到这了,感兴趣的你,可以试试能不能走出来~
所有的代码都已上传至我的github:https://github.com/MiracleYoung/exercises
领取专属 10元无门槛券
私享最新 技术干货