图算法系列之无向图的数据层次
发布时间：2021-06-03 16:18:28 所属栏目：大数据 来源：互联网
导读：图的定义 图：是有一组顶点和一组能够将两个订单相连组成的。连接两个顶点的边没有方向，这种图称之为无向图。 图的术语 通过同一条边相连的两个顶点我们称这两个顶点相邻; 某个顶点的度数即表示连接这个顶点的边的总数;如上图：顶点1的度数是3 一条边连接了
|
图的定义
图：是有一组顶点和一组能够将两个订单相连组成的。连接两个顶点的边没有方向，这种图称之为无向图。
图的术语
通过同一条边相连的两个顶点我们称这两个顶点相邻;
某个顶点的度数即表示连接这个顶点的边的总数;如上图：顶点1的度数是3
一条边连接了一个顶点与其自身，我们称为自环
连接同一对顶点的边称为平行边
术语还有很多，暂时这里只列出本篇我们需要使用到的术语，后面有在使用到其他的术语再做解释，太多也不太容易记得住
如何表示出图
图用什么数据结构来表示主要参考两个要求：
在开发图的相关算法时，图的表示的数据结构是基础，所以这种数据结构效率的高
在实际的过程中图的大小不确定，可能会很大，所以需要预留出足够的空间
考虑了这两个要求之后大佬们提出以下三个方法来供选择：
邻接矩阵 键入有v个顶点的图，我们可以使用v乘以v的矩阵来表示，如果顶点v与w相连，那么把v行w列设置为true，这样就可以表示两个顶点相连，但是这个方式有个问题，如果遇到图很大，会造成空间的浪费。不满足第二点。其次这种方式没办法表示平行边
边的数组 可以定义一个表示的边对象，包含两个int属性表示顶点，但是如果需要找到某个顶点的相连顶点有哪些，我们就需要遍历一遍全部的边。这种数据结构的效率较差
邻接表数组 定义一个数组，数组的大小为顶点的个数，数据下标表示顶点，数组中每个元素都是一个链表对象(LinkedListQueue),链表中存放的值就是与该顶点相连的顶点。(LinkedListQueue我们已经在之前的文章中实现，可以参考文章《https://juejin.cn/post/6926685994347397127》)
无向图的API定义
public class Graph {
public Graph(int V); //创建含有v个顶点不含边的图
public int V(); //返回顶点的个数
public int E(); //返回图中边的总数
public void addEdge(int v, int w); //向图中添加一条边 v-W
public Iterable<Integer> adj(int v); //返回与v相邻的所有顶点
public String toString(); //使用字符串打印出图的关系
}
无向图API的实现
要实现上面定义的API，我们需要三个成员变量，v表示图中顶点的个数，e表示图总共边的数据，LinkedListQueue的数组用来存储顶点v的相邻节点;
 （编辑：威海站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
