表示图

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

表示顶点

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

string[] vertices = {“西雅图”, “旧金山”, “洛杉矶”, “丹佛”, “堪萨斯城”, “芝加哥”, “波士顿”, “纽约”, “亚特兰大”, “迈阿密” 、“达拉斯”、“休斯顿”}；

顶点可以是任何类型的对象。例如，您可以将城市视为包含名称、人口和市长等信息的对象。因此，您可以按如下方式定义顶点：

城市 city0 = new city(“西雅图”, 608660, “mike mcginn”);
…
城市 city11 = new city(“休斯顿”, 2099451, “安妮丝·帕克”);
city[] 顶点 = {city0, city1, … , city11};

公开课城市{
私有字符串城市名称；
私人人口；
私人字符串市长；

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 方便地标记顶点。因此，vertices[0]代表“西雅图”，vertices[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;
这个.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[][] 邻接矩阵 = {
{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));

以上就是表示图的详细内容，更多请关注叮当号网其它相关文章！