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

【数据结构】6——图1,概念

数据结构6——图1,概念


文章目录

  • 数据结构6——图1,概念
    • 基本概念
    • 图的分类
    • 图的表示方法


基本概念

由 顶点(Vertex) 和 边(Edge) 组成的集合。顶点表示图中的点,而边表示顶点之间的连接。记为 G = (V, E)

基本组件包括:
顶点(Vertex):图中的节点或点。每个顶点代表一个对象。
边(Edge):连接两个顶点的线段,表示它们之间的关系。边可以是有向的或无向的。
权重(Weight):有些图的边附带权重,表示边的成本、距离或其他量度。

  • 邻接:有边连接的两个节点的关系
    (i,j)没有先后顺序
    <i,j>有先后顺序

  • 关联:边和相连的节点的关系

  • 顶点的度:关联边的数目

  • 路径(Path):图中从一个顶点到另一个顶点所经过的顶点序列。

  • 简单路径(Simple Path):路径中所有的顶点都不重复。

  • 环(Cycle):路径的起点和终点相同,并且至少经过一个其他顶点。若图中存在环,称为有环图;否则称为无环图。

  • 强连通图(Strongly Connected Graph):对于有向图,如果对于每一对顶点 u 和v,都存在从 u 到v 和从 v 到 u 的路径,则该图是强连通的。

  • 生成树(Spanning Tree):一个无环的子图,包含图中的所有顶点,且是连通的。

  • 生成森林(Spanning Forest):由多个生成树组成的集合,每个生成树包含图中一部分顶点。

  • 子图(Subgraph):图中的一部分顶点和边的集合,这些顶点和边也构成一个图。

图的分类

  • 无向图(Undirected Graph):图中的边没有方向,即如果顶点A与顶点B之间有一条边,那么它表示A和B之间是相互连接的。

  • 有向图(Directed Graph):图中的边有方向,称为弧(Arc)。如果顶点A与顶点B之间有一条有向边,它表示从一个顶点指向另一个顶点的单向连接。

  • 加权图(Weighted Graph):图中的边被赋予了权重(Weight),这些权重可以表示距离、成本、时间等。

  • 无权图(Unweighted Graph):图中的边没有权重,或者所有边的权重相同。

  • 简单图(Simple Graph):图中不包含重复的边,且不允许顶点与自己相连(自环)。

  • 多重图(Multigraph):图中可以有多条边连接相同的一对顶点。

  • 完全图(Complete Graph):图中的每对顶点之间都恰好有一条边。

  • 稀疏图(Sparse Graph):边的数量远小于顶点对的数量。边很少

  • 密集图(Dense Graph):边的数量接近顶点对的最大数量。

  • 连通图(Connected Graph):在无向图中,如果任意两个顶点之间都存在路径,则称该图为连通图。在有向图中,如果任意两个顶点之间都存在方向路径,则称该图为强连通图。

  • 网:边带权值的图

图的表示方法

  • 邻接矩阵(Adjacency Matrix)
    定义:一个二维数组 matrix[i][j] 表示顶点 i 和顶点 j 之间的边。如果 matrix[i][j] 非零,则存在边。
    优点:快速查询是否存在边,适用于稠密图。
    缺点:空间复杂度为 O(V^2),其中 V 是顶点数量,适用于大部分稠密图。

假设有一个无向图,包含 4 个顶点(A, B, C, D)和以下边:
A - B
A - C
B - C
C - D

    A  B  C  D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 1, 0 ]
C [ 1, 1, 0, 1 ]
D [ 0, 0, 1, 0 ]
  • 邻接表(Adjacency List),不唯一
    定义:每个顶点维护一个列表,列出与其相邻的所有顶点。l链表
    优点:节省空间,适用于稀疏图。
    缺点:查询边的操作较慢,空间复杂度为 O(V + E),其中 E 是边的数量。
A: B -> C
B: A -> C
C: A -> B -> D
D: C
  • . 边列表(Edge List)
    边列表使用一个列表存储图中的所有边。每个元素是一个元组,表示一条边及其两个端点。

[(A, B), (A, C), (B, C), (C, D)]


相关文章:

【数据结构】6——图1,概念

数据结构6——图1&#xff0c;概念 文章目录 数据结构6——图1&#xff0c;概念基本概念图的分类图的表示方法 基本概念 由 顶点&#xff08;Vertex&#xff09; 和 边&#xff08;Edge&#xff09; 组成的集合。顶点表示图中的点&#xff0c;而边表示顶点之间的连接。记为 G …...

技术周总结 09.09~09.15周日(C# WinForm WPF)

文章目录 一、09.09 周一1.1) 问题01: Windows桌面开发中&#xff0c;WPF和WinForm的区别和联系&#xff1f;联系&#xff1a;区别&#xff1a; 二、09.12 周四2.1&#xff09;问题01&#xff1a;visual studio的相关快捷键有哪些&#xff1f;通用快捷键编辑导航调试窗口管理 2…...

4K投影仪选购全攻略:全玻璃镜头的当贝F6,画面细节纤毫毕现

在当今的投影市场上&#xff0c;4K投影仪已经成了主流产品&#xff0c;越来越多家庭开始关注如何选择一款性价比高、口碑好的4K投影仪。4K投影仪其实指的是具备3840*2160像素分辨率投影仪&#xff0c;它能够提供更清晰、更细腻、更真实的画面效果。 那么4K投影仪该怎么选&…...

除了字符串前导的*号之外,将串中其它*号全部删除

要求 假定输入的字符串中只包含字母和*号。请编写函数fun&#xff0c;它的功能是:除了字符串前导的*号之外&#xff0c;将串中其它*号全部删除。在编写函数时&#xff0c;不得使用C语言提供的字符串函数。函数fun中给出的语句仅供参考。 例如&#xff0c;字符串中的内容为:-**…...

SpringBoot开发——使用@Slf4j注解实现日志输出

文章目录 1、Lombok简介2、SLF4J简介3、实现步骤3.1 创建SpringBoot项目3.2 添加依赖3.3 使用 Slf4j 注解3.4 输出日志信息 4、结论 在现代Java开发中&#xff0c;日志记录是至关重要的。它不仅帮助开发者调试代码&#xff0c;还便于监控系统运行状态和性能。 Lombok 和 SLF4J …...

VSCode拉取远程项目

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

【已解决】SpringBoot3项目整合Druid依赖:Druid监控页面404报错

文章标题 问题描述原因分析解决方案参考资料 问题描述 最近&#xff0c;笔者在SpringBoot3项目中整合Druid连接池时&#xff0c;偶然翻到一条介绍Druid监控的短视频&#xff0c;兴致盎然之下尝试设置了一下Druid监控。 But&#xff0c;按照视频中提供的yml参数对照设置&#x…...

【算法】滑动窗口—找所有字母异位词

“找到字符串中所有字母异位词”的难度为Medium&#xff0c;看一下题目&#xff1a; 给定一个字符串 S 和一个非空字符串 T&#xff0c;找到 S 中所有是 T 的字母异位词的子串&#xff0c;返回这些子串的起始索引。 所谓的字母异位词&#xff0c;其实就是全排列&#xff0c;原题…...

Vue安装及环境配置【图解版】

欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 Facts speak louder than words&#xff01; 目录 一.node.js的安装…...

绕过CDN查找真实IP方法

1、前言 在新型涉网案件中&#xff0c;我们在搜集到目标主站之后常常需要获取对方网站的真实IP去进一步的信息搜集&#xff0c;但是现在网站大多都部署了CDN&#xff0c;将资源部署分发到边缘服务器 实现均衡负载&#xff0c;降低网络堵塞&#xff0c;让用户能够更快地访问自己…...

Qt与MQTT交互通信

MQTT全称是&#xff08;Message Queuing Telemetry Transport&#xff09;&#xff0c;即消息队列遥测传输协议 是一种基于发布/订阅&#xff08;Publish/Subscribe&#xff09;模式的轻量级通讯协议&#xff0c;并且该协议构建于TCP/IP协议之上&#xff0c;常用于互联网中&am…...

dd 命令:复制和转换文件

一、dd 命令简介 ​dd​ 命令是一个在 Unix 和类 Unix 系统中用于复制文件和转换文件的命令行工具。它的功能非常强大&#xff0c;可以用于各种目的&#xff0c;例如创建镜像文件、备份和恢复数据、复制数据等。 ​dd​ 是一个用于读取、转换和写入数据的工具&#xff0c;通常…...

文件系统(磁盘 磁盘文件 inode)

文章目录 磁盘看看物理磁盘磁盘的存储结构 对磁盘的储存进行逻辑抽象inode号文件名 -> inode判断文件在哪个分区 磁盘 电脑中存在非常多的文件&#xff0c;被打开的文件只是少量的。 没有被打开的文件&#xff0c;在磁盘中放着&#xff0c;那么文件是如何存取&#xff1f; …...

ThreeJs创建圆环

ThreeJs除了创建基本的长方体&#xff0c;球形&#xff0c;圆柱等几何体&#xff0c;也可以创建一些特殊的几何体&#xff0c;比如圆环&#xff0c;多边体&#xff0c;这节就来讲怎么用Threejs绘制出圆环。首先依然是要创建出基础的组件&#xff0c;包括场景&#xff0c;相机&a…...

React实现类似Vue的路由监听Hook

React实现类似Vue的路由监听Hook 监听路由变化&#xff1b;React Hook封装&#xff0c;返回回调函数&#xff0c;新旧路由为函数参数&#xff1b; 代码 import { useEffect, useRef } from react; import { useHistory, useLocation } from react-router-dom;/*** 监听路由变…...

Visual Studio打开项目的一些小技巧

Visual Studio(VS)是一款功能强大的集成开发环境&#xff0c;许多刚入门C/C的小白也会使用这款软件进行写代码&#xff0c;然而它的操作并不简单&#xff0c;下面将讲解一下VS打开项目文件的一些小技巧。 目录 &#x1f381;创建空项目 ❤️①点击“创建新项目” ❤️②点击“…...

前端页面中使用 ppt 功能,并且可以随意插入关键帧

要在前端页面中实现类似 PowerPoint 的功能&#xff0c;并且能够随意插入和控制关键帧动画&#xff0c;你可以使用 HTML、CSS 和 JavaScript 结合的方式来创建一个互动幻灯片系统。以下是一个详细的实现方案&#xff0c;包括如何插入和控制关键帧动画&#xff1a; 1. 基础 HTM…...

机器学习:opencv--图像金字塔

目录 一、图像金字塔 1.图像金字塔是什么&#xff1f; 2.有哪些常见类型&#xff1f; 3.金字塔的构建过程 4.图像金字塔的作用 二、图像金字塔中的操作 1.向下采样 2.向上采样 3.注意--无法复原 三、代码实现 1.高斯金字塔向下采样 2.高斯金字塔向上采样 3.无法复…...

linux安全软件Hydra使用教程

Hydra 是一个强大的网络登录工具&#xff0c;常用于渗透测试&#xff0c;支持对多种服务和协议&#xff08;如 SSH、FTP、HTTP 等&#xff09;进行暴力crack攻击。它可以通过字典攻击来测试用户名和密码的有效性。以下是关于如何使用 Hydra 的基本步骤和示例&#xff1a; 1. 安…...

【ShuQiHere】从晶体管到逻辑门:数字电路的构建之旅

【ShuQiHere】 现代计算机和电子设备的基础是逻辑电路&#xff08;Logic Circuits&#xff09;&#xff0c;它们执行信息处理和运算任务。在这些电路的核心&#xff0c;是晶体管&#xff08;Transistors&#xff09; 和 逻辑门&#xff08;Logic Gates&#xff09;。通过理解这…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...

STM32 低功耗设计全攻略:PWR 模块原理 + 睡眠 / 停止 / 待机模式实战(串口 + 红外 + RTC 应用全解析)

文章目录 PWRPWR&#xff08;电源控制模块&#xff09;核心功能 电源框图上电复位和掉电复位可编程电压监测器低功耗模式模式选择睡眠模式停止模式待机模式 修改主频一、准备工作二、修改主频的核心步骤&#xff1a;宏定义配置三、程序流程&#xff1a;时钟配置函数解析四、注意…...

Heygem50系显卡合成的视频声音杂音模糊解决方案

如果你在使用50系显卡有杂音的情况&#xff0c;可能还是官方适配问题&#xff0c;可以使用以下方案进行解决&#xff1a; 方案一&#xff1a;剪映替换音色&#xff08;简单适合普通玩家&#xff09; 使用剪映换音色即可&#xff0c;口型还是对上的&#xff0c;没有剪映vip的&…...