表示圖

表示一個圖就是將它的頂點和邊儲存在程式中。用於儲存圖的資料結構是數組或列表。要編寫處理和操作圖形的程序，您必須在電腦中儲存或表示圖形的資料。

表示頂點

頂點可以儲存在陣列或清單中。例如，您可以使用下列陣列儲存下圖中圖表中的所有城市名稱：

String[] vertices = {"西雅圖", "舊金山", "洛杉磯", "丹佛", "堪薩斯城", "芝加哥", "波士頓", "紐約", "亞特蘭大", "邁阿密」、 「達拉斯」、「休士頓」}；

頂點可以是任何類型的物件。例如，您可以將城市視為包含名稱、人口和市長等資訊的物件。因此，您可以如下定義頂點：

城市 city0 = new City("西雅圖", 608660, "Mike McGinn");
...
城市 city11 = new City("休士頓", 2099451, "安妮絲帕克");
City[] 頂點 = {city0, city1, ... , city11};

公開課城市{
private String 城市名稱;
私人 int 人口；
私人字符串市長；

public City(String cityName, int population, String mayor) {
this.cityName = cityName;
this.population = population;
this.mayor = mayor;
 }

public String getCityName() {
return cityName;
 }

public int getPopulation() {
return population;
 }

public String getMayor() {
return mayor;
 }

public void setMayor(String mayor) {
this.mayor = mayor;
 }

public void setPopulation(int population) {
this.population = population;
 }
}

對於 n 個頂點的圖，可以使用自然數 0、1、2、...、n - 1 方便地標記頂點。因此，頂點[0]代表「西雅圖」，頂點[1]代表「舊金山」，依此類推，如下圖所示。

您可以透過頂點的名稱或索引來引用頂點，以更方便的為準。顯然，在程式中透過索引存取頂點是很容易的。

表示邊：邊數組

邊緣可以使用二維數組來表示。例如，您可以使用下列陣列儲存圖 28.1 中圖形中的所有邊：

int[][] 邊緣 = {
{0, 1}, {0, 3}, {0, 5},
{1, 0}, {1, 2}, {1, 3},
{2, 1}, {2, 3}, {2, 4}, {2, 10},
{3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
{4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
{5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
{6, 5}, {6, 7},
{7, 4}, {7, 5}, {7, 6}, {7, 8},
{8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
{9, 8}, {9, 11},
{10, 2}, {10, 4}, {10, 8}, {10, 11},
{11, 8}, {11, 9}, {11, 10}
};

這種表示法稱為邊數組。下圖(a)的頂點和邊可以表示如下：

String[] 名稱 = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
int[][] 邊 = {{0, 2}, {1, 2}, {2, 4}, {3, 4}};

表示邊緣：邊緣對象

表示邊的另一種方法是將邊定義為物件並將邊儲存在 java.util.ArrayList 中。 Edge 類別可以定義如下：

公開課邊緣{
int你；
int v;
公共邊（int u，int v）{
這個.u = u;
this.v = v;
}
公共布爾等於（對象o）{
返回 u == ((Edge)o).u && v == ((Edge)o).v;
}
}

例如，您可以使用下列清單儲存下圖中圖形中的所有邊：

java.util.ArrayList; list = new java.util.ArrayList();
list.add(new Edge(0, 1));
list.add(new Edge(0, 3));
list.add(new Edge(0, 5));
...

如果您事先不知道邊緣，則將 Edge 物件儲存在 ArrayList 中非常有用。

雖然在前一節（表示邊：邊數組）和本節前面的部分中使用邊數組或Edge 物件表示邊對於輸入來說可能很直觀，但對於輸入來說效率不高內部處理。接下來的兩節介紹使用鄰接矩陣和鄰接列表來表示圖。這兩種資料結構對於處理圖形非常有效。

表示邊：鄰接矩陣

假設圖有 n 個頂點。您可以使用二維 n * n 矩陣，例如 adjacencyMatrix 來表示邊緣。陣列中的每個元素都是 0 或 1。如果從頂點i 到頂點j 有一條邊，adjacencyMatrix[i][j] 為1；否則， adjacencyMatrix[i][j] 為0。如果圖是無向的，則矩陣是對稱的，因為 adjacencyMatrix[i][j] 與 adjacencyMatrix[j][i] 相同。例如，下圖的邊可以使用鄰接矩陣表示，如下所示：

int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // 西雅圖
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // 舊金山
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // 洛杉磯
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // 丹佛
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // 堪薩斯市
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // 芝加哥
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // 波士頓
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // 紐約
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // 亞特蘭大
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // 邁阿密
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // 達拉斯
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // 休士頓
};

由於無向圖的矩陣是對稱的，為了節省儲存空間，您可以使用不規則數組。

下圖(a)中的有向圖的鄰接矩陣可以表示如下：

int[][] a = {{0, 0, 1, 0, 0}, // 彼得
{0, 0, 1, 0, 0}, // 簡
{0, 0, 0, 0, 1}, // 標記
{0, 0, 0, 0, 1}, // 辛蒂
{0, 0, 0, 0, 0} // 溫迪
};

表示邊：鄰接表

您可以使用鄰接頂點列表或鄰接邊列表來表示邊。頂點 i 的鄰接頂點清單包含與 i 相鄰的頂點，頂點 i 的鄰接邊清單包含與 i 相鄰的邊。您可以定義一個清單數組。
數組有 n 個條目，每個條目都是列表。頂點 i 的鄰接頂點清單包含所有頂點 j，使得存在從頂點 i 到頂點 j 的邊。例如，要表示下圖中圖形中的邊，您可以建立一個清單數組，如下所示：

java.util.List[] Neighbors = new java.util.List[12];

neighbors[0] 包含與頂點0 相鄰的所有頂點（即西雅圖），neighbors[1] 包含與頂點1（即舊金山），以此類推，如下圖。

要表示下圖中圖形的鄰接邊列表，您可以建立一個列表數組，如下所示：

java.util.List[] Neighbors = new java.util.List[12];

neighbors[0] 包含與頂點0 相鄰的所有邊（即西雅圖），neighbors[1] 包含與頂點1（即舊金山），以此類推，如下圖。

您可以使用鄰接矩陣或鄰接清單來表示圖。哪一個比較好？如果圖很密集（即有很多邊），則首選使用鄰接矩陣。如果圖非常稀疏（即邊很少），則使用鄰接列表會更好，因為使用鄰接矩陣會浪費大量空間。

鄰接矩陣和鄰接表都可以在程式中使用，以使演算法更有效率。例如，使用鄰接矩陣檢查兩個頂點是否連接需要 O(1) 常數時間，使用鄰接列表列印圖中的所有邊需要線性時間 O(m)，其中 m 是邊數.

鄰接頂點清單對於表示未加權圖來說更簡單。然而，鄰接邊列表對於各種圖形應用來說更加靈活。使用鄰接邊清單可以輕鬆地在邊上新增額外的約束。因此，本書將使用鄰接邊列表來表示圖。

可以使用陣列、陣列清單或鍊錶來儲存鄰接表。我們將使用列表而不是數組，因為列表可以輕鬆擴展以允許您添加新頂點。此外，我們將使用陣列列表而不是鍊錶，因為我們的演算法只需要搜尋列表中的相鄰頂點。使用數組列表對於我們的演算法來說更有效。使用數組列表，可以如下建立下圖中的鄰接邊列表：

List>>鄰居 = new ArrayList();
Neighbors.add(new ArrayList());
Neighbors.get(0).add(new Edge(0, 1));
Neighbors.get(0).add(new Edge(0, 3));
Neighbors.get(0).add(new Edge(0, 5));
Neighbors.add(new ArrayList());
Neighbors.get(1).add(new Edge(1, 0));
Neighbors.get(1).add(new Edge(1, 2));
Neighbors.get(1).add(new Edge(1, 3));
...
...
Neighbors.get(11).add(new Edge(11, 8));
Neighbors.get(11).add(new Edge(11, 9));
Neighbors.get(11).add(new Edge(11, 10));

以上是表示圖的詳細內容。更多資訊請關注PHP中文網其他相關文章！