表示图

表示图是在程序中存储其顶点和边缘。存储图的数据结构是数组或列表。为了编写处理和操作图形的程序，您必须在计算机中存储或表示图形的数据。

表示顶点

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

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以此类推，代表“旧金山”，如下图所示

以更方便为准，您可以通过顶点的名称或索引来引用顶点。显然，在程序中很容易通过索引访问顶点。

表示边：边数组

二维数组可以用来表示边缘。例如，您可以使用以下数组存储图 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.在araylist中。 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));

以上是图的详细内容，请关注图灵教育的其他相关文章！