当前位置: 首页 > 图灵资讯 > 技术篇> 表示图

表示图

来源:图灵教育
时间:2024-08-14 11:08:13

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

表示顶点

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

表示图

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));

表示图

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