加权图
介绍
加权图(Weighted Graph)是图论中的一种重要图类型,特点是每条边都有一个与之关联的数值,称为权重(Weight)或成本(Cost)。这些权重可以表示各种现实世界中的量化关系,如距离、时间、费用、容量等。加权图广泛应用于网络分析、路径规划、资源分配等领域,是解决许多优化问题的基础数据结构。
加权图中的关键概念包括:
- 顶点(Vertex):图中的节点,通常用数字或字母标识。
- 带权边(Weighted Edge):连接两个顶点的边,附带一个表示某种度量的权重值。例如在表示交通网络的图中,边的权重可能代表路径长度或通行时间。
- 权重(Weight):分配给边的数值,根据应用场景可以是正数、负数或零。
- 路径权重(Path Weight):路径上所有边的权重总和,也称为路径长度或路径成本。
- 最短路径(Shortest Path):两个顶点之间权重总和最小的路径。
- 最小生成树(Minimum Spanning Tree):连接图中所有顶点且总权重最小的子图。
核心特性
- 边权重:每条边都有一个关联的数值,表示某种度量或成本
- 路径评估:可以根据边的权重计算路径的总成本或效率
- 最优路径选择:支持寻找最短路径、最小生成树等优化问题
- 类型多样性:可以是有向的或无向的,根据关系的性质决定
- 权重特性:权重可以是正数、负数或零,表示不同的约束条件
- 算法基础:是Dijkstra算法、Bellman-Ford算法、Kruskal算法、Prim算法等经典算法的应用对象
...