Java中如何实现加权无向图的数据结构设计？

本文共计1436个文字，预计阅读时间需要6分钟。

目录前言边的表示API设计代码实现图的实现API设计代码实现前言权限无向图是一种为每条边关联一个权重或模型的结构，每个节点代表一个边，权重或模型决定了边的连接性质。这种图可以自然地展示多种应用场景。

在副航空空间图中，权限表示每条边的连接权重或模型。这种图能自然地展示多种应用场景。

目录

• 前言
• 边的表示
• API设计
• 代码实现
• 图的实现
• API设计
• 代码实现

前言

加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？
在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢？此时就要考虑，那条路径的成本最低。