Java数据结构之图的基础概念和数据模型详解
作者:JAVA旭阳 发布时间:2022-03-25 11:27:04
图的实际应用
在现实生活中,有许多应用场景会包含很多点以及点点之间的连接,而这些应用场景我们都可以用即将要学习的图这种数据结构去解决。
地图:
我们生活中经常使用的地图,基本上是由城市以及连接城市的道路组成,如果我们把城市看做是一个一个的点,把道路看做是一条一条的连接,那么地图就是我们将要学习的图这种数据结构。
图的定义及分类
定义: 图是由一组顶点和一组能够将两个顶点相连的边组成的。
特殊的图:
自环:即一条连接一个顶点和其自身的边;
平行边:连接同一对顶点的两条边;
图的分类:
按照连接两个顶点的边的不同,可以把图分为以下两种:
无向图:边仅仅连接两个顶点,没有其他含义;
有向图:边不仅连接两个顶点,并且具有方向;
图的相关术语
相邻顶点:
当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这条边依附于这两个顶点。
度:
某个顶点的度就是依附于该顶点的边的个数
子图:
是一幅图的所有边的子集(包含这些边依附的顶点)组成的图;
路径:
是由边顺序连接的一系列的顶点组成
环:
是一条至少含有一条边且终点和起点相同的路径
连通图:
如果图中任意一个顶点都存在一条路径到达另外一个顶点,那么这幅图就称之为连通图
连通子图:
一个非连通图由若干连通的部分组成,每一个连通的部分都可以称为该图的连通子图
图的存储结构
要表示一幅图,只需要表示清楚以下两部分内容即可:
图中所有的顶点;
所有连接顶点的边;
常见的图的存储结构有两种:邻接矩阵和邻接表。
邻接矩阵
使用一个V*V的二维数组int[V][V] adj,把索引的值看做是顶点;
如果顶点v和顶点w相连,我们只需要将adj[v][w]和adj[w][v]的值设置为1,否则设置为0即可。
很明显,邻接矩阵这种存储方式的空间复杂度是V^2的,如果我们处理的问题规模比较大的话,内存空间极有可能不够用。
邻接表
1.使用一个大小为V的数组 Queue[V] adj,把索引看做是顶点;
2.每个索引处adj[v]存储了一个队列,该队列中存储的是所有与该顶点相邻的其他顶点。
很明显,邻接表的空间并不是是线性级别的,所以后面我们一直采用邻接表这种存储形式来表示图。
图的实现
下面通过代码实现一个无向图。
图的API设计
类名 | Graph |
---|---|
成员变量 | 1.private final int V: 记录顶点数量2.private int E: 记录边数量3.private Queue[] adj: 邻接表 |
构造方法 | Graph(int V):创建一个包含V个顶点但不包含边的图 |
成员方法 | 1.public int V():获取图中顶点的数量2.public int E():获取图中边的数量3.public void addEdge(int v,int w):向图中添加一条边 v-w4.public Queue adj(int v):获取和顶点v相邻的所有顶点 |
代码实现
/**
* 无向图的表示
*
* @author alvin
* @date 2022/10/30
* @since 1.0
**/
public class Graph {
//顶点数目
private final int V;
//边的数目
private int E;
//邻接表,队列的形式
private Queue<Integer>[] adj;
public Graph(int V) {
// 初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Queue[V];
//初始化邻接表中的空队列
for (int i = 0; i < adj.length; i++) {
adj[i] = new ArrayDeque<>();
}
}
public void addEdge(int v, int w) {
//把w添加到v的链表中,这样顶点v就多了一个相邻点w
adj[v].add(w);
//把v添加到w的链表中,这样顶点w就多了一个相邻点v
adj[w].add(v);
//边的数目自增1
E++;
}
//获取顶点数目
public int V() {
return V;
}
//获取边的数目
public int E(){
return E;
}
//获取和顶点v相邻的所有顶点
public Queue<Integer> adj(int v) {
return adj[v];
}
}
数组adj的索引表示顶点。
来源:https://juejin.cn/post/7160296427694850079
猜你喜欢
- 本文实例为大家分享了Java实现颜色渐变效果的具体代码,供大家参考,具体内容如下RGB色彩,在自然界中肉眼所能看到的任何色彩都可以由红(R)
- 背景最近引入了 Nacos Config 配置管理能力,说起来用法很简单,还是踩了三个坑。Nacos Config 的 nacos 的帐号密
- 本文实例讲述了C#实现的xml操作类,分享给大家供大家参考,具体如下:using System;using System.Data;usin
- 目录什么是Spring的占位符?Spring什么时候去解析并占位符什么是Spring的占位符?在以前的Spring Xml配置中我们可能会有
- 一、简介SpringBoot 最强大的功能就是把我们常用的场景抽取成了一个个starter(场景启动器),我们通过引入SpringBoot
- namespace ConsoleTest{ class Program  
- 一,FileWritter写入文件FileWritter, 字符流写入字符到文件。默认情况下,它会使用新的内容取代所有现有的内容,然而,当指
- 1.方法概述什么是方法方法(method)是将具有独立功能的代码块组织成为一个整体,使其具有图书功能的代码集注意:方法必须先创建才可以使用,
- 前言在windows平台下实现高性能网络服务器,iocp(完成端口)是唯一选择。编写网络服务器面临的问题有:1 快速接收客户端的连接。2 快
- 本文实例讲述了Spring实战之方法级别缓存用法。分享给大家供大家参考,具体如下:一 配置文件<?xml version="
- 查询返回Map<String,Object>类型mybatis 查询返回Map<String,Object> 类型,
- 本文实例讲述了Java二叉搜索树基础原理与实现方法。分享给大家供大家参考,具体如下:前言:本文通过先通过了解一些二叉树基础知识,然后在转向学
- 前言:2022年Java将有什么新的特性和改进,我相信很多Java开发者都想知道。结合Java语言架构师布莱恩·格茨(
- 本文核心为分层领域模型(VO , PO , BO, DAO ,POJO等)概念的个人理解。1.为什么出现分层领域模型这个东西?(1)解决MV
- 对于初学java的同学来说,第一件事不是写hello world,而是搭建好java开发环境,下载jdk,安装,配置环境变量。这些操作在xp
- 1.创建简单的XML文件为了便于测试,我们首先创建控制台应用程序,项目命名为CreateXml,Program.cs代码如下:using S
- 访问控制:private 私有的protected 受保护的public 公共的类、方法和变量修饰符abstract 声明抽象class 类
- 本文实例讲述了java实现将结果集封装到List中的方法。分享给大家供大家参考,具体如下:import java.sql.Connectio
- 一、注解(annotations)列表@SpringBootApplication:包含了@ComponentScan、@Configura
- 找不同给定两个字符串 s 和 t ,它们只包含小写字母。字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。