表示图是在程序中存储其顶点和边缘。存储图的数据结构是数组或列表。为了编写处理和操作图形的程序,您必须在计算机中存储或表示图形的数据。
表示顶点顶点可以存储在数组或列表中。例如,您可以使用下面的数组来存储下图中所有的城市名称:
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
如果你事先不知道边缘,你会的 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[0] 包含与顶点 0(即西雅图)相邻的所有顶点,neighbors[1] 包含与顶点 1(即旧金山)相邻的所有顶点,以此类推,如下图所示。
您可以创建一个列表数组,以表示下图中图形的邻接边列表,如下所示:
java.util.list
neighbors[0] 包含与顶点 0(即西雅图)相邻的所有边缘,neighbors[1] 包含与顶点 1(即旧金山)相邻的所有边缘,按此类推,如下图所示。
您可以使用相邻矩阵或相邻列表来表示图表。哪个更好?如果图表非常密集(即有许多边缘),则首选使用相邻矩阵。如果图表非常稀疏(即边缘很少),最好使用相邻列表,因为使用相邻矩阵会浪费大量空间。
为了使算法更高效,可以在程序中使用邻接矩阵和邻接表。例如,使用邻接矩阵检查两个顶点是否需要连接 o(1) 使用相邻列表打印图中的所有边缘需要线性时间 o(m),其中 m 是边数.
相邻的顶点列表更容易表示未加权图。然而,相邻的边缘列表对各种图形应用程序更加灵活。使用相邻的边缘列表可以很容易地在边缘添加额外的限制。因此,这本书将使用相邻的边缘列表来表示图表。
您可以使用数组、数组列表或链表来存储相邻的表。我们将使用列表而不是数组,因为列表可以很容易地扩展,以允许您添加新的顶点。此外,我们将使用数组列表而不是链表,因为我们的算法只需要搜索列表中的相邻顶点。使用数组列表对我们的算法更有效。使用数组列表,可以构建下图中的相邻边缘列表:
list> 邻居 = new arraylist();
neighbors.add(new arraylist
以上是图的详细内容,请关注图灵教育的其他相关文章!