数据结构与算法07-图

介绍

图是一种善于处理关系型数据的数据结构，使用它可以很轻松地表示数据之间是如何关联的。

图的实现形式有很多，最简单的方法之一就是用散列表。

friends = {
"Alice" => ["Bob", "Diana", "Fred"],
"Bob" => ["Alice", "Cynthia", "Diana"],
"Cynthia" => ["Bob"],
"Diana" => ["Alice", "Bob", "Fred"],
"Elise" => ["Fred"],
"Fred" => ["Alice", "Diana", "Elise"]
}

因为从散列表里查找一个键所对应的值只需要 1 步，所以查找 Alice 的朋友能以 O(1)的时间复杂度完成，如下所示。
friends[“Alice”]

实现方式

尽管只用散列表也可以实现一个图，但是以面向对象的方法来写会更加健壮。

广度优先搜索

如图所示，Alice 能直接联系到 Bob，Bob 能直接联系到 Cynthia。但 Alice 无法直接联系到
Cynthia。由于她们之间的联系要经过 Bob，因此 Cynthia 是 Alice 的二度联系人。

图有两种经典的遍历方式：广度优先搜索和深度优先搜索。

这里主要介绍下前者：

加权图

还有一种图叫作加权图。它跟普通的图类似，但边上带有信息。
以下这个包含了美国几个主要城市的简陋地图，就是一个加权图。

此图中，每条边上都有一个数字，它表示那条边所连接的两个城市相距多少英里。例如，Chicago和 New York City 之间的距离为 714 英里。

加权图可以是有方向的。以下图为例，尽管从 Dallas 飞到 Toronto 只要 138 美元，但从 Toronto飞到 Dallas 要 216 美元。

Dijkstra 算法

解决最短路径问题的算法有好几种，其中一种有趣的算法是由 Edsger Dijkstra（念为“dike’struh”）于 1959 年发现的。该算法也很自然地被称为 Dijkstra 算法。

例如：用python实现一个图结构，实现广度优先搜索，找出从任意城市A出发到B城市最便宜的飞机票价格

from collections import dequedef cheapest_flight(graph, start_city, end_city):"""使用广度优先搜索找到从start_city到end_city的最便宜机票价格。:param graph: 一个字典，表示城市间的航班图，格式如{'城市A': [(城市B, 价格), (城市C, 价格)]}:param start_city: 起始城市名称:param end_city: 目标城市名称:return: 最便宜的机票价格，如果不存在这样的路径则返回None"""if start_city not in graph or end_city not in graph:return None  # 起始或结束城市不存在于图中queue = deque([(start_city, 0)])  # 初始化队列，存放当前城市及到该城市的路径价格visited = set()  # 记录已访问的城市，避免循环访问while queue:current_city, current_cost = queue.popleft()if current_city == end_city:return current_cost  # 找到目标城市，返回最低价格if current_city not in visited:visited.add(current_city)for neighbor, price in graph[current_city]:if neighbor not in visited:queue.append((neighbor, current_cost + price))  # 将邻居加入队列并更新路径价格return None  # 没有路径到达目标城市# 示例图结构
graph_example = {'A': [('B', 100), ('C', 200)],'B': [('C', 50), ('D', 150)],'C': [('D', 100)],'D': []
}# 查找从城市A到城市D的最便宜机票价格
print(cheapest_flight(graph_example, 'A', 'D'))  # 应输出250，因为A->B->D的总价格是100+150=250，是最便宜的路径