表示加權圖

加權邊可以儲存在鄰接清單中。

加權圖有兩種：頂點加權和邊加權。在頂點加權圖中，每個頂點都被分配一個權重。在邊加權圖中，每條邊都被分配一個權重。在這兩種類型中，邊加權圖有更多的應用。本章討論邊加權圖。

加權圖可以用與未加權圖相同的方式表示，只不過您必須表示邊上的權重。與未加權圖一樣，加權圖中的頂點可以儲存在陣列中。本節介紹加權圖中邊的三種表示法。

表示加權邊：邊數組

加權邊可以使用二維陣列來表示。例如，您可以使用下圖(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中文網其他相關文章！