表示加权图

加权边可以存储在邻接列表中。

加权图有两种类型：顶点加权和边加权。在顶点加权图中，每个顶点都被分配一个权重。在边加权图中，每条边都被分配一个权重。在这两种类型中，边加权图有更多的应用。本章讨论边加权图。

加权图可以用与未加权图相同的方式表示，只不过您必须表示边上的权重。与未加权图一样，加权图中的顶点可以存储在数组中。本节介绍加权图中边的三种表示形式。

表示加权边：边数组

加权边可以使用二维数组来表示。例如，您可以使用下图(b)中的数组来存储下图(a)图中的所有边。

权重可以是任何类型：Integer、Double、BigDecimal等。您可以使用 Object 类型的二维数组来表示加权边，如下所示：

对象[][]边缘= {
{new Integer(0), new Integer(1), new SomeTypeForWeight(2)},
{new Integer(0), new Integer(3), new SomeTypeForWeight(8)},
...
};

加权邻接矩阵

假设图有 n 个顶点。您可以使用二维 n * n 矩阵，例如 weights 来表示边上的权重。 weights[i][j] 表示边上的权重 (i, j)。如果顶点 i 和 j 未连接，则 weights[i][j] 为 null。例如，上图(a)中的权重可以使用邻接矩阵表示如下：

邻接表

表示边缘的另一种方法是将边缘定义为对象。 AbstractGraph.Edge 类被定义为表示 AbstractGraph.java 中的未加权边。对于加权边，我们定义 WeightedEdge 类，如下面的代码所示。

AbstractGraph.Edge 是 AbstractGraph 类中定义的内部类。它表示从顶点 u 到 v 的边。 WeightedEdge 使用新属性 weight 扩展了 AbstractGraph.Edge。

要创建 WeightedEdge 对象，请使用 new WeightedEdge(i, j, w)，其中 w 是边上的权重 (i ，j）。通常您需要比较边的权重。因此，WeightedEdge 类实现了 Comparable 接口。

对于未加权图，我们使用邻接表来表示边。对于带权图，我们仍然使用邻接表，下图a中的图中顶点的邻接表可以表示为：

java.util.List[] list = new java.util.List[5];

list[i] 存储与顶点 i.

相邻的所有边

为了灵活性，我们将使用数组列表而不是固定大小的数组来表示 list，如下所示：

列表> list = new java.util.ArrayList();

以上是表示加权图的详细内容。更多信息请关注PHP中文网其他相关文章！