图论基础和表示(Java 实例代码)
目录
图论基础和表示
一、概念及其介绍
二、适用说明
三、图的表达形式
Java 实例代码
src/runoob/graph/DenseGraph.java 文件代码:
src/runoob/graph/SparseGraph.java 文件代码:
图论基础和表示
一、概念及其介绍
图论(Graph Theory)是离散数学的一个分支,是一门研究图(Graph)的学问。
图是用来对对象之间的成对关系建模的数学结构,由"节点"或"顶点"(Vertex)以及连接这些顶点的"边"(Edge)组成。
值得注意的是,图的顶点集合不能为空,但边的集合可以为空。图可能是无向的,这意味着图中的边在连接顶点时无需区分方向。否则,称图是有向的。下面左图是一个典型的无向图结构,右图则属于有向图。本章节介绍的图都是无向图。

图的分类:无权图和有权图,连接节点与节点的边是否有数值与之对应,有的话就是有权图,否则就是无权图。
图的连通性:在图论中,连通图基于连通的概念。在一个无向图 G 中,若从顶点 i 到顶点 j 有路径相连(当然从j到i也一定有路径),则称 i 和 j 是连通的。如果 G 是有向图,那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。
完全图:完全是一个简单的无向图,其中每对不同的顶点之间都恰连有一条边相连。
自环边:一条边的起点终点是一个点。
平行边:两个顶点之间存在多条边相连接。
二、适用说明
图可用于在物理、生物、社会和信息系统中建模许多类型的关系和过程,许多实际问题可以用图来表示。因此,图论成为运筹学、控制论、信息论、网络理论、博弈论、物理学、化学、生物学、社会科学、语言学、计算机科学等众多学科强有力的数学工具。在强调其应用于现实世界的系统时,网络有时被定义为一个图,其中属性(例如名称)之间的关系以节点和或边的形式关联起来。
三、图的表达形式
邻接矩阵:1 表示相连接,0 表示不相连。

邻接表:只表达和顶点相连接的顶点信息

邻接表适合表示稀疏图 (Sparse Graph)
邻接矩阵适合表示稠密图 (Dense Graph)
Java 实例代码
源码包下载:Download
(1) 邻接矩阵
src/runoob/graph/DenseGraph.java 文件代码:
package runoob.graph;
/**
* 邻接矩阵
*/
public class DenseGraph {
// 节点数
private int n;
// 边数
private int m;
// 是否为有向图
private boolean directed;
// 图的具体数据
private boolean[][] g;
// 构造函数
public DenseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
// false为boolean型变量的默认值
g = new boolean[n][n];
}
// 返回节点个数
public int V(){ return n;}
// 返回边的个数
public int E(){ return m;}
// 向图中添加一个边
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) )
return;
g[v][w] = true;
if( !directed )
g[w][v] = true;
m ++;
}
// 验证图中是否有从v到w的边
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
}
(2)邻接表
src/runoob/graph/SparseGraph.java 文件代码:
package runoob.graph;
import java.util.Vector;
/**
* 邻接表
*/
public class SparseGraph {
// 节点数
private int n;
// 边数
private int m;
// 是否为有向图
private boolean directed;
// 图的具体数据
private Vector<Integer>[] g;
// 构造函数
public SparseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g = (Vector<Integer>[])new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
// 返回节点个数
public int V(){ return n;}
// 返回边的个数
public int E(){ return m;}
// 向图中添加一个边
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].add(w);
if( v != w && !directed )
g[w].add(v);
m ++;
}
// 验证图中是否有从v到w的边
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
}
相关文章:
图论基础和表示(Java 实例代码)
目录 图论基础和表示 一、概念及其介绍 二、适用说明 三、图的表达形式 Java 实例代码 src/runoob/graph/DenseGraph.java 文件代码: src/runoob/graph/SparseGraph.java 文件代码: 图论基础和表示 一、概念及其介绍 图论(Graph Theory)是离散数…...
各种数据库查询报错问题
文章目录 前言一、约束条件是自增,不能直接添加数据二、使用步骤1.引入库2.读入数据 总结 前言 记录常见的数据库使用问题,以及对应解决思路 一、约束条件是自增,不能直接添加数据 消息 8101,级别 16,状态 1…...
人效九宫格城市沙龙暨《人效九宫格白皮书》发布会 —上海站,圆满结束
8月11日,在上海龙之梦万丽酒店,由盖雅工场主办的人效九宫格城市沙龙暨《人效九宫格白皮书》发布会 —上海站,圆满结束。 近百位来自多个行业的企业管理者及人力资源从业者汇聚一堂,共同探讨企业如何将盈利模式从数量增长转为质量增…...
【C语言】文件操作 -- 详解
一、什么是文件 磁盘上的文件是文件。 1、为什么要使用文件 举个例子,当我们想实现一个 “通讯录” 程序时,在通讯录中新建联系人、删除联系人等一系列操作,此时的数据存储于内存中,程序退出后所有数据都会随之消失。为了让通讯录…...
飞天使-k8s基础组件分析-持久化存储
文章目录 emptyDirhostpathpv和pvc介绍nfs作为静态pv案例nfs作为动态pv案例使用本地文件夹作为pv改变默认存储类及回收策略参考文档 emptyDir 重启文件还有,但是如果杀了进程,则会丢失文件 创建pod # kubectl apply –f redis.yaml校验pod是否处于运行&…...
python连接PostgreSQL 数据库
执行如下命令安装 pip3 install psycopg2 python代码 Author: tkhywang 2810248865qq.com Date: 2023-08-21 11:42:17 LastEditors: tkhywang 2810248865qq.com LastEditTime: 2023-08-21 11:51:56 FilePath: \PythonProject02\PostgreSQL 数据库.py Description: 这是默认设置…...
数字图像处理—— Lab、YCbCr、HSV、RGB之间互转
Lab “Lab” 图像格式通常指的是 CIELAB 色彩空间,也称为 Lab 色彩空间。它是一种用于描述人类视觉感知的颜色的设备无关色彩空间,与常见的 RGB 和 CMYK 色彩空间不同。CIELAB 由国际照明委员会(CIE)于1976年定义,用于…...
自动驾驶SLAM技术第四章习题2
在g2o的基础上改成ceres优化,高博都写好了其他的部分, 后面改ceres就很简单了. 这块我用的是ceres的自动求导,很方便,就是转化为模板仿函数的时候有点麻烦, 代码部分如下 ceres_type.h : ceres优化核心库的头文件 这个文件写的内…...
vue拖拽div盒子实现上下拖动互换
vue拖拽div盒子实现上下拖动互换 <div v-for"(item, index) in formList" :key"index" draggable"true"dragstart"handleDragStart($event, item)"dragenter"handleDragEnter($event, item)"dragover.prevent"han…...
Visual Studio 2022 右键单击项目没有出现View | View Class Diagram(Visual Studio 无法使用类设计器)
文章目录 问题描述原因.NET Core项目.NET Framework项目 问题描述 当我们在Solution Explorer窗口右键单击项目时,快捷菜单中没有出现“查看”,或者出现了“查看”,但是“查看”里没有View Class Diagram。 原因 首先你要确保你安装了类设…...
EFCore常见用法
EFCore官方文档置顶,看这个就行。下面的内容只是总结,算是备忘录。 一、创建和删除 //1、创建数据库和表 db.Database.EnsureCreated();//将创建数据库(如果不存在)并初始化数据库架构。 如果存在任何表 (包括另一 DbContext 类)…...
概率论与数理统计:第六章:数理统计
文章目录 Ch6. 数理统计(一) 总体与样本(二) 统计量 (5个)2.5个常用统计量3.矩的概念 (三) 抽样分布 (3个)0.上α分位点1.χ分布2.t分布3.F分布 (四) 抽样分布定理1.单个正态总体2.两个正态总体 Ch6. 数理统计 (一) 总体与样本 1.概念: (1)总体 (2)样本 简单随机…...
拥塞控制(TCP限制窗口大小的机制)
拥塞控制机制可以使滑动窗口在保证可靠性的前提下,提高传输效率 关于滑动窗口的属性以及部分机制推荐看TCP中窗口和滑动窗口的含义以及流量控制 拥塞控制出现的原因 看了上面推荐的博客我们已经知道了,由于接收方接收数据的能力有限,所以要通…...
校园供水系统智能管理
import pandas as pd data1pd.read_excel("C://Users//JJH//Desktop//E//附件_一季度.xlsx") data2pd.read_excel("C://Users//JJH//Desktop//E//附件_二季度.xlsx") data3pd.read_excel("C://Users//JJH//Desktop//E//附件_三季度.xlsx") data4…...
Flask-SocketIO和Flask-Login联合开发socketio权限系统
设置 Flask, Flask-SocketIO, Flask-Login: 首先,确保安装了必要的库: pip install Flask Flask-SocketIO Flask-Login基础设置: from flask import Flask, render_template, redirect, url_for, request from flask_socketio import SocketIO, emit from flask_…...
航空电子设备中的TSN通讯架构—直升机
前言 以太网正在迅速取代传统网络,成为航空电子设备和任务系统的核心高速网络。本文提出了以太网时间敏感网络(TSN)在航空电子设备上应用的技术优势问题。在实际应用中,TSN已成为一个具有丰富的机制和协议的工具箱,可满足与时间和可靠性相关…...
elment-ui中使用el-steps案例
el-steps案例 样式 代码 <div class"active-box"><div class"active-title">请完善</div><el-steps :active"active" finish-status"success" align-center><el-step title"第一步" /><…...
FPGA解析串口指令控制spi flash完成连续写、读、擦除数据
前言 最近在收拾抽屉时找到一个某宝的spi flash模块,如下图所示,我就想用能不能串口来读写flash,大致过程就是,串口向fpga发送一条指令,fpga解析出指令控制flah,这个指令协议目前就是: 55 AA …...
msvcp120.dll丢失的解决方法,分享三种快速修复的方法
今天,我将和大家分享一个关于电脑问题的解决方法——msvcp120.dll丢失的解决方法。希望对大家有所帮助。 首先,让我们来了解一下msvcp120.dll文件。msvcp120.dll是Microsoft Visual C 2010 Redistributable Package的一个组件,它包含了一些运…...
mysql 8.0 窗口函数 之 序号函数 与 sql server 序号函数 一样
sql server 序号函数 序号函数 ROW_NUMBER() 顺序排序RANK() 并列排序,会跳过重复的序号,比如序号为1,1,3DENSE_RANK() 并列排序,不会跳过重复的序号,比如 序号为 1,1,2 语法结构…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...
