当前位置： 首页 > news >正文

数据结构-图的基本概念

news 来源：原创 2024/9/29 19:29:41

图的定义

        图时由非空的顶点集合和一个描述顶点之间关系的集合组成。可以定义为：

                                        ​​​​​​​        ​​​​​​​        ​​​​​​​        G=(V,E)

         G表示一个图，V表示点集，E表示边集。集合E的每一个二元组都包含两个值v_{i}和v_{j}，表示为一条边的两个顶点。

图的相关术语

        （1）无向图

        在一个图中顶点之间的连线没有指定方向。

        （2）有向图

        在一个图中顶点之间的连线有指定方向

        （3）顶点、边

        在无向图中，两个顶点之间的连线称为边，边用顶点的无序偶对(v,w)表示，称顶点v和顶点w互为邻接点。

        （4）弧、弧头、弧尾

        在有向图中，两个顶点之间的连线称为弧，弧用顶点的有序偶对<v_{i},v_{j}>表示，有序偶对的第一个结点v_{i}称为弧尾（图中没有箭头的一端），第二个结点v_{j}称为弧头（图中有结点的一端）。若<v,w>是一条弧，则称顶点v邻接到w。

        （5）无向完全图

        在一个无向图中，如果任意两点都有一条直接边相连接，则称为无向完全图。

        在一个n个顶点的无向完全图中有n(n-1)/2条边。

        （6）有向完全图

        在一个有向图中，如果任意两点都有方向互为相反的两条弧相连接，则称为有向完全图。

        在一个n个顶点的有向完全图中有n(n-1)条边。

        （7）稠密图、稀疏图

        若一个图接近完全图，称为稠密图

        边数很少的图(e<<n(n-1))为稀疏图

        （8）度

        顶点的度是与顶点相连接的边数，记为D(v)

        在有向图中有入度和出度的区分。

        入度指的是以顶点v为终点的弧的数目，记为ID(v)

        出度指的是以顶点v为起点的弧的数目，记为OD(v)

        对于具有n个顶点、e条边的图，顶点v_{i}的度D(v_{i})与顶点的个数以及边的数目的关系为：

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        e=\frac{1}{2}\sum_{i=1}^{n}D(v_{i})

         （9）边权、网图

        当图的边带有数值信息时，这种数值称为权。

        每条边或弧都带权的图称为带权图或网。

        （10）路径、路径长度

        在无向图中，顶点v_{p}到顶点v_{q}之间的路径指序列v_{p},v_{i1},v_{i2}...v_{q}，路径上边的数目称为路径长度。有向图中路径也是有向的。

        （11）回路，简单回路

        起点和终点相同的路径称为回路或环。除了第一个顶点与最后一个顶点之外其他顶点不重复出现的回路称为简单回路。

        （12）连通图

        在无向图中，任意两个顶点都相互连通，称为连通图。

        （13）强连通图

        在有向图中，如果从一个顶点v_{i}到另一个顶点v_{j}均有一条有向路径，则该图为强连通图

相关文章：

  • 小程序项目业务逻辑回忆4
  • huggingface连不上的解决方案
  • oracle发送http请求
  • C++ 反转一个二进制串
  • cd 命令特殊路径符 mkdir命令
  • Android | 性能优化 之 TraceView工具的使用
  • 基于SSM+Jsp的体育竞赛成绩管理系统
  • 45、基于深度学习的螃蟹性别分类(matlab)
  • 网络编程（TCP协议，UDP协议）
  • tron-passwd写入提权
  • 音视频开发—FFmpeg 打开摄像头进行RTMP推流
  • SSLyze：一款快速高效的SSLTLS扫描工具
  • 2024年全球架构师峰会(ArchSummit深圳站)
  • 大型语言模型在AMD GPU上的推理优化
  • 使用阿里开源的Spring Cloud Alibaba AI开发第一个大模型应用
  • (ckeditor+ckfinder用法)Jquery,js获取ckeditor值
  • [译]CSS 居中（Center）方法大合集
  • [译]如何构建服务器端web组件，为何要构建？
  • 【MySQL经典案例分析】 Waiting for table metadata lock
  • Android开源项目规范总结
  • CSS居中完全指南——构建CSS居中决策树
  • iOS | NSProxy
  • node-sass 安装卡在 node scripts/install.js 解决办法
  • Spring Cloud(3) - 服务治理: Spring Cloud Eureka
  • use Google search engine
  • 动态规划入门（以爬楼梯为例）
  • 缓存与缓冲
  • 让你成为前端，后端或全栈开发程序员的进阶指南，一门学到老的技术
  • 山寨一个 Promise
  • 使用 @font-face
  • 数组大概知多少
  • 学习ES6 变量的解构赋值
  • 用jquery写贪吃蛇
  • 找一份好的前端工作，起点很重要
  • HanLP分词命名实体提取详解
  • # 飞书APP集成平台-数字化落地
  • #QT 笔记一
  • $(selector).each()和$.each()的区别
  • $HTTP_POST_VARS['']和$_POST['']的区别
  • (01)ORB-SLAM2源码无死角解析-(56) 闭环线程→计算Sim3:理论推导(1)求解s,t
  • (20)docke容器
  • （2024，Flag-DiT，文本引导的多模态生成，SR，统一的标记化，RoPE、RMSNorm 和流匹配）Lumina-T2X
  • (C++20) consteval立即函数
  • （C语言）fgets与fputs函数详解
  • （day 2）JavaScript学习笔记（基础之变量、常量和注释）
  • （Redis使用系列） Springboot 实现Redis 同数据源动态切换db 八
  • （第二周）效能测试
  • （附源码）ssm跨平台教学系统 毕业设计 280843
  • （论文阅读笔记）Network planning with deep reinforcement learning
  • （四）事件系统
  • （四）图像的%2线性拉伸
  • （学习日记）2024.04.10：UCOSIII第三十八节：事件实验
  • (转)VC++中ondraw在什么时候调用的
  • （状压dp）uva 10817 Headmaster's Headache
  • .[hudsonL@cock.li].mkp勒索加密数据库完美恢复---惜分飞