数据结构—图

图的基本概念

图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为:G(V,E),其中,G 表示一个图,V 表示顶点的集合,E 表示边的集合。

顶点

图中的数据元素,我们称之为顶点,图至少有一个顶点(非空有穷集合)

对应到好友关系图,每一个用户就代表一个顶点。

顶点之间的关系用边表示。

对应到好友关系图,两个用户是好友的话,那两者之间就存在一条边。

度表示一个顶点包含多少条边,在有向图中,还分为出度和入度,出度表示从该顶点出去的边的条数,入度表示进入该顶点的边的条数。

对应到好友关系图,度就代表了某个人的好友数量。

无向图和有向图

边表示的是顶点之间的关系,有的关系是双向的,比如同学关系,A 是 B 的同学,那么 B 也肯定是 A 的同学,那么在表示 A 和 B 的关系时,就不用关注方向,用不带箭头的边表示,这样的图就是无向图。

有的关系是有方向的,比如父子关系,师生关系,微博的关注关系,A 是 B 的爸爸,但 B 肯定不是 A 的爸爸,A 关注 B,B 不一定关注 A。在这种情况下,我们就用带箭头的边表示二者的关系,这样的图就是有向图。

无权图和带权图

对于一个关系,如果我们只关心关系的有无,而不关心关系有多强,那么就可以用无权图表示二者的关系。

对于一个关系,如果我们既关心关系的有无,也关心关系的强度,比如描述地图上两个城市的关系,需要用到距离,那么就用带权图来表示,带权图中的每一条边一个数值表示权值,代表关系的强度。

下图就是一个带权有向图。

图的存储

邻接矩阵存储

邻接矩阵将图用二维矩阵存储,是一种较为直观的表示方式。

如果第 i 个顶点和第 j 个顶点之间有关系,且关系权值为 n,则 A[i][j]=n 。

在无向图中,我们只关心关系的有无,所以当顶点 i 和顶点 j 有关系时,A[i][j]=1,当顶点 i 和顶点 j 没有关系时,A[i][j]=0。如下图所示:

值得注意的是:无向图的邻接矩阵是一个对称矩阵,因为在无向图中,顶点 i 和顶点 j 有关系,则顶点 j 和顶点 i 必有关系。

邻接矩阵存储的方式优点是简单直接(直接使用一个二维数组即可),并且,在获取两个定点之间的关系的时候也非常高效(直接获取指定位置的数组元素的值即可)。但是,这种存储方式的缺点也比较明显,那就是比较浪费空间,

邻接表存储

针对上面邻接矩阵比较浪费内存空间的问题,诞生了图的另外一种存储方法—邻接表

邻接链表使用一个链表来存储某个顶点的所有后继相邻顶点。对于图中每个顶点 Vi,把所有邻接于 Vi 的顶点 Vj 链成一个单链表,这个单链表称为顶点 Vi 的 邻接表。如下图所示:

无向图的邻接表存储

有向图的邻接表存储

大家可以数一数邻接表中所存储的元素的个数以及图中边的条数,你会发现:

  • 在无向图中,邻接表元素个数等于边的条数的两倍,如左图所示的无向图中,边的条数为 7,邻接表存储的元素个数为 14。
  • 在有向图中,邻接表元素个数等于边的条数,如右图所示的有向图中,边的条数为 8,邻接表存储的元素个数为 8。

图的搜索

广度优先搜索

广度优先搜索就像水面上的波纹一样一层一层向外扩展,如下图所示:

广度优先搜索的具体实现方式用到了之前所学过的线性数据结构——队列 。具体过程如下图所示:

第 1 步:

第 2 步:

第 3 步:

第 4 步:

第 5 步:

第 6 步:

深度优先搜素

深度优先搜索就是“一条路走到黑”,从源顶点开始,一直走到没有后继节点,才回溯到上一顶点,然后继续“一条路走到黑”,如下图所示:

和广度优先搜索类似,深度优先搜索的具体实现用到了另一种线性数据结构——栈 。具体过程如下图所示:

第 1 步:

第 2 步:

第 3 步:

第 4 步:

第 5 步:

第 6 步:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520183.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

常见现代卷积神经网络(Pytorch 09)

本章将介绍现代的 卷积神经网络架构,许多现代卷积神经网络的研究都是建立在这一章的基础上的。在本章中的每一个模型都曾一度占据主导地位,其中许多模型都是 ImageNet竞赛 的优胜者。ImageNet竞赛自2010年以来,一直是计算机视觉中监督学习进展…

面试题——JVM老年代空间担保机制(我的想法)

这里借用一下人家的图,来说一下我的想法,嘻嘻。。。。 原文链接:一道面试题:JVM老年代空间担保机制-CSDN博客? 嗯,我觉得老年代担保机制的主要作用就是避免频繁触发FULL GC,这其实也是因为年轻代Minor GC…

Java项目:基于Springboot+vue社区医院管理系统设计与实现(源码+数据库+毕业论文)

一、项目简介 本项目是一套基于Springbootvue社区医院管理系统 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,eclipse或者idea 确保可以运行! 该系统功能完善、界面美观、操作简单、功能…

数据结构之顺序表的相关知识点及应用

个人主页(找往期文章包括但不限于本期文章中不懂的知识点):我要学编程(ಥ_ಥ)-CSDN博客 目录 顺序表的概念及结构 顺序表的分类 顺序表的实现 在顺序表中增加数据 在顺序表中删除数据 在顺序表中查找数据 顺序表源码 顺序表的概念…

浮动辊位移测量功能块(CODESYS ST代码)

1、张力测量+标定(ST代码) 张力测量+标定(ST代码)_动态舞轮控制张力-CSDN博客文章浏览阅读804次。跳舞轮对应张力调节范围,我们可以通过改变气缸的气压方式间接改变,张力跳舞轮在收放卷闭环控制上的详细应用,可以参看下面的文章链接,这里我们主要讨论精密可调气阀的模拟量…

Java | Leetcode Java题解之第6题Z字形变换

题目: 题解: class Solution {public String convert(String s, int numRows) {int n s.length(), r numRows;if (r 1 || r > n) {return s;}int t r * 2 - 2;int c (n t - 1) / t * (r - 1);char[][] mat new char[r][c];for (int i 0, x …

[Spring Cloud] gateway全局异常捕捉统一返回值

文章目录 处理转发失败的情况全局参数同一返回格式操作消息对象AjaxResult返回值状态描述对象AjaxStatus返回值枚举接口层StatusCode 全局异常处理器自定义通用异常定一个自定义异常覆盖默认的异常处理自定义异常处理工具 在上一篇章时我们有了一个简单的gateway网关 [Spring C…

比selenium体验更好的ui自动化测试工具: cypress介绍

话说 Cypress is a next generation front end testing tool built for the modern web. And Cypress can test anything that runs in a browser.Cypress consists of a free, open source, locally installed Test Runner and a Dashboard Service for recording your tests.…

leetcode077——排序链表

题目: 给定链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 示例 1: 输入:head [4,2,1,3] 输出:[1,2,3,4] 思路: 1.找链表中点【使用快慢指针 慢指针每次移动一步,快指针每…

基于单片机12864的出租车计价器设计

**单片机设计介绍,基于单片机12864的出租车计价器设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机和12864液晶显示屏的出租车计价器设计,主要是利用单片机的强大控制能力和液晶显示屏的直观显示特性&…

牛客网BC-125 序列中整数去重复(难题讲解)

题目如下 --------------------------------------------------------------------------------------------------------------------------------- 题目讲解(思路) -------------------------------------------------------------------------------…

单一职责原则

1.1 阅读干吗不直接用手机? 电子阅读器比较专注,而手机功能比较多,影响专注。 1.2 手机不纯粹 手机确实很方便。但是现在的手机就是一台小型智能电脑。它不仅能打电话,还能听音乐、看电影电视、与个人交流、与一群人群聊&#…

基于java+SpringBoot+Vue的大学生入学审核系统设计与实现

基于javaSpringBootVue的大学生入学审核系统设计与实现 开发语言: Java 数据库: MySQL技术: SpringBoot VUE工具: IDEA/Eclipse、Navicat、Maven 系统展示 前台展示 入学办理模块:学生可以提交入学申请并跟踪入学办理进度。 后台展示 学生管理模块&#xff1…

【Docker系列】在 Linux 上安装 Docker Compose 的简明步骤

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

前端学习之DOM编程案例:抽奖案例

代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>抽奖案例</title><style>*{margin: 0;padding: 0;}</style> </head> <body><div id"container"&g…

【放假第3天】幻兽帕鲁 雾锁王国 我的世界 游戏云服务器选购指南 附最新价格对比表 新手、小白秒懂

更新日期&#xff1a;4月6日&#xff08;半年档 价格回调&#xff0c;京东云采购季持续进行&#xff09; 本文纯原创&#xff0c;侵权必究 【云服务器推荐】价格对比&#xff01;阿里云 京东云 腾讯云 选购指南视频截图 《最新对比表》已更新在文章头部—腾讯云文档&#xf…

LeetCode 1483.树节点的第 K 个祖先:树上倍增

【LetMeFly】1483.树节点的第 K 个祖先&#xff1a;树上倍增 力扣题目链接&#xff1a;https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/ 给你一棵树&#xff0c;树上有 n 个节点&#xff0c;按从 0 到 n-1 编号。树以父节点数组的形式给出&#xff0c;其中 paren…

redis主从复制与哨兵模式

redis主从复制 Redis主从复制&#xff08;Redis replication&#xff09;是Redis提供的一种数据备份和故障转移机制。通过主从复制&#xff0c;可以将一个Redis服务器&#xff08;主节点&#xff09;的数据复制到一个或多个Redis服务器&#xff08;从节点&#xff09;。这样做…

【面经】interrupt()、interrupted()和isInterrupted()的区别与使用

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;面经 ⛺️稳中求进&#xff0c;晒太阳 interrupt方法 如果打断线程正在sleep&#xff0c;wait&#xff0c;join会导致被打断的线程抛出InterruptedException&#xff0c;并清除打断标记。如…

FebHost:什么是土耳其.TR域名?

当前互联网高速发展,一个国家的顶级域名已成为其网络形象的重要标识。近期,土耳其国家顶级域名”.TR”引起了广泛关注,成为业界热议的话题。 作为代表土耳其共和国的国家顶级域名(ccTLD),.TR域名于1991年首次引入,由土耳其科技和信息技术部负责管理。除了常见的”.com.tr”、”…