08-权重的处理

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

4.4.1　权重的处理

要了解建造某条边所需的轨道数量，就需要知道这条边表示的距离。现在是再次引入权重概念的时候了。在超级高铁网络中，边的权重是两个所连MSA之间的距离。图4-5与图4-2几乎相同，差别只是每条边多了权重，表示边所连的两个顶点之间的距离（以英里为单位）。

图4-5　美国15个最大的MSA的加权图，权重代表两个MSA之间的距离，单位英里（1英里≈1.6093 km）

为了处理权重，需要建立 Edge 的子类 WeightedEdge 和 Graph 的子类 WeightedGraph 。每个 WeightedEdge 都带有一个与其关联的表示其权重的 float 类型数据。下面马上就会介绍Jarník算法，它能够比较两条边并确定哪条边权重较低。采用数值型的权重就很容易进行比较了。具体代码如代码清单4-6所示。

代码清单4-6　weighted_edge.py

from __future__ import annotations
from dataclasses import dataclass
from edge import Edge
@dataclass
class WeightedEdge(Edge):
    weight: float
    def reversed(self) -> WeightedEdge:
        return WeightedEdge(self.v, self.u, self.weight)
    # so that we can order edges by weight to find the minimum weight edge
    def __lt__(self, other: WeightedEdge) -> bool:
        return self.weight<other.weight
    def __str__(self) -> str:
        return f"{self.u} {self.weight}> {self.v}"

WeightedEdge 的实现代码与 Edge 的实现代码并没有太大的区别，只是添加了一个 weight 属性，并通过 __lt__() 实现了“<”操作符，这样两个 WeightedEdge 就可以相互比较了。“<”操作符只涉及权重（而不涉及继承而来的属性 u 和 v ），因为Jarník的算法只关注如何找到权重最小的边。

如代码清单4-7所示， WeightedGraph 从 Graph 继承了大部分功能，此外，它还包含了 __init__ 方法和添加 WeightedEdge 的便捷方法，并且实现了自己的 __str__() 方法。它还有一个新方法 neighbors_for_index_with_weights() ，这一方法不仅会返回每一位邻居，还会返回到达这位邻居的边的权重。这一方法对其 __str__() 十分有用。

代码清单4-7　weighted_graph.py

from typing import TypeVar, Generic, List, Tuple
from graph import Graph
from weighted_edge import WeightedEdge
V = TypeVar('V') # type of the vertices in the graph
class WeightedGraph(Generic[V], Graph[V]):
    def __init__(self, vertices: List[V] = []) -> None:
        self._vertices: List[V] = vertices
        self._edges: List[List[WeightedEdge]] = [[] for _ in vertices]
    def add_edge_by_indices(self, u: int, v: int, weight: float) -> None:
        edge: WeightedEdge = WeightedEdge(u, v, weight)
        self.add_edge(edge) # call superclass version
    def add_edge_by_vertices(self, first: V, second: V, weight: float) -> None:
        u: int = self._vertices.index(first)
        v: int = self._vertices.index(second)
        self.add_edge_by_indices(u, v, weight)
    def neighbors_for_index_with_weights(self, index: int) -> List[Tuple[V, float]]:
        distance_tuples: List[Tuple[V, float]] = []
        for edge in self.edges_for_index(index):
            distance_tuples.append((self.vertex_at(edge.v), edge.weight))
        return distance_tuples
    def __str__(self) -> str:
        desc: str = ""
        for i in range(self.vertex_count):
            desc += f"{self.vertex_at(i)} -> {self.neighbors_for_index_with_weights(i)}\n"
        return desc

现在可以实际定义加权图了。这里将会用到图4-5表示的加权图，名为 city_graph2 。具体代码如代码清单4-8所示。

代码清单4-8　weighted_graph.py（续）

if __name__ == "__main__":
    city_graph2: WeightedGraph[str] = WeightedGraph(["Seattle", "San Francisco", 
      "Los Angeles", "Riverside", "Phoenix", "Chicago", "Boston", "New York", "Atlanta",
      "Miami", "Dallas", "Houston", "Detroit", "Philadelphia", "Washington"])
    city_graph2.add_edge_by_vertices("Seattle", "Chicago", 1737)
    city_graph2.add_edge_by_vertices("Seattle", "San Francisco", 678)
    city_graph2.add_edge_by_vertices("San Francisco", "Riverside", 386)
    city_graph2.add_edge_by_vertices("San Francisco", "Los Angeles", 348)
    city_graph2.add_edge_by_vertices("Los Angeles", "Riverside", 50)
    city_graph2.add_edge_by_vertices("Los Angeles", "Phoenix", 357)
    city_graph2.add_edge_by_vertices("Riverside", "Phoenix", 307)
    city_graph2.add_edge_by_vertices("Riverside", "Chicago", 1704)
    city_graph2.add_edge_by_vertices("Phoenix", "Dallas", 887)
    city_graph2.add_edge_by_vertices("Phoenix", "Houston", 1015)
    city_graph2.add_edge_by_vertices("Dallas", "Chicago", 805)
    city_graph2.add_edge_by_vertices("Dallas", "Atlanta", 721)
    city_graph2.add_edge_by_vertices("Dallas", "Houston", 225)
    city_graph2.add_edge_by_vertices("Houston", "Atlanta", 702)
    city_graph2.add_edge_by_vertices("Houston", "Miami", 968)
    city_graph2.add_edge_by_vertices("Atlanta", "Chicago", 588)
    city_graph2.add_edge_by_vertices("Atlanta", "Washington", 543)
    city_graph2.add_edge_by_vertices("Atlanta", "Miami", 604)
    city_graph2.add_edge_by_vertices("Miami", "Washington", 923)
    city_graph2.add_edge_by_vertices("Chicago", "Detroit", 238)
    city_graph2.add_edge_by_vertices("Detroit", "Boston", 613)
    city_graph2.add_edge_by_vertices("Detroit", "Washington", 396)
    city_graph2.add_edge_by_vertices("Detroit", "New York", 482)
    city_graph2.add_edge_by_vertices("Boston", "New York", 190)
    city_graph2.add_edge_by_vertices("New York", "Philadelphia", 81)
    city_graph2.add_edge_by_vertices("Philadelphia", "Washington", 123)
    print(city_graph2)

因为 WeightedGraph 实现了 __str__() ，所以我们可以美观打印出 city_graph2 。在输出结果中会同时显示每个顶点连接的所有顶点及这些连接的权重。

Seattle -> [('Chicago', 1737), ('San Francisco', 678)]
San Francisco -> [('Seattle', 678), ('Riverside', 386), ('Los Angeles', 348)]
Los Angeles -> [('San Francisco', 348), ('Riverside', 50), ('Phoenix', 357)]
Riverside -> [('San Francisco', 386), ('Los Angeles', 50), ('Phoenix', 307), ('Chicago',
   1704)]
Phoenix -> [('Los Angeles', 357), ('Riverside', 307), ('Dallas', 887), ('Houston', 1015)]
Chicago -> [('Seattle', 1737), ('Riverside', 1704), ('Dallas', 805), ('Atlanta', 588), 
    ('Detroit', 238)]
Boston -> [('Detroit', 613), ('New York', 190)]
New York -> [('Detroit', 482), ('Boston', 190), ('Philadelphia', 81)] 
Atlanta -> [('Dallas', 721), ('Houston', 702), ('Chicago', 588), ('Washington', 543),
    ('Miami', 604)]
Miami -> [('Houston', 968), ('Atlanta', 604), ('Washington', 923)]
Dallas -> [('Phoenix', 887), ('Chicago', 805), ('Atlanta', 721), ('Houston', 225)]
Houston -> [('Phoenix', 1015), ('Dallas', 225), ('Atlanta', 702), ('Miami', 968)]
Detroit -> [('Chicago', 238), ('Boston', 613), ('Washington', 396), ('New York', 482)]
Philadelphia -> [('New York', 81), ('Washington', 123)]
Washington -> [('Atlanta', 543), ('Miami', 923), ('Detroit', 396), ('Philadelphia', 123)]

Previous 上一篇本节目录 Next 下一篇

08-权重的处理

4.4.1 权重的处理

4.4.1　权重的处理