本文转载自微信公众号《内测学习JAVA》，作者Silently9527。转载本文请联系贝塔学习JAVA公众号。前言从这篇文章开始，我们将一起学习图相关的算法。图计算的实用算法有很多，例如：垃圾收集器的标记清除算法、地图上路径的最短距离、拓扑排序等。在我们开始学习这些算法之前，我们需要了解基本的下图的定义以及用于表示图的数据结构。在本文中，我们从无向图开始。图的定义：图由一组顶点和一组可以连接两个订单的集合组成。连接两个顶点的边没有方向，这样的图称为无向图。图的项是由同一条边连接的两个顶点。我们称这两个顶点相邻；某个顶点的度表示连接该顶点的边的总数；如上图所示：顶点1的度数为3。一条边连接一个A顶点和它自己，我们称之为自环，连接同一对顶点的边称为平行边。还有很多其他术语。此处暂且只列出本文中需要用到的术语，其他术语后面会用到解释。太多了不容易记住怎么表示图形。用什么数据结构来表示图主要是指两个需求：在开发图的相关算法时，图表示的数据结构是基础，所以这种数据结构的效率高在实际过程中，图的大小不确定，可能很大，需要预留足够的空间。考虑到这两个需求后，大佬们提出了以下三种方法可以选择：邻接矩阵key有v个顶点，我们可以用v乘以v的矩阵来表示，如果顶点v与w相连，则设将v行w列设置为true，这样就可以表示两个顶点是相连的，但是这种方法有个问题，如果遇到图片很大的话，会造成空间的浪费。第二点不满足。其次，这种方法无法表示平行边。一个边数组可以定义一个表示的边对象，它包含两个int属性来表示顶点，但是如果我们需要找出哪些顶点连接到某个顶点，我们需要遍历所有的边。这种数据结构的效率很差。邻接表数组定义了一个数组。数组的大小是顶点的数量。数据下标表示顶点。数组中的每个元素都是一个链表对象（LinkedListQueue），链表中存储的值是与这个顶点相连的Vertices。（LinkedListQueue在上一篇文章中已经实现，请参考文章《https://juejin.cn/post/6926685994347397127》）无向图的API定义publicclassGraph{publicGraph(intV);//创建一个包含v个顶点无边的图publicintV();//返回顶点数publicintE();//返回图中边的总数publicvoidaddEdge(intv,intw);//向图中添加一条边v-WpublicIterable
