表示图

表示一个图就是将它的顶点和边存储在程序中。用于存储图的数据结构是数组或列表。要编写处理和操作图形的程序，您必须在计算机中存储或表示图形的数据。

表示顶点

顶点可以存储在数组或列表中。例如，您可以使用以下数组存储下图中图表中的所有城市名称：

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中文网其他相关文章！