【脚踢数据结构】图(纯享版)

  • (꒪ꇴ꒪ ),Hello我是祐言QAQ
  • 我的博客主页:C/C++语言,Linux基础,ARM开发板,软件配置等领域博主🌍
  • 快上🚘,一起学习,让我们成为一个强大的攻城狮!
  • 送给自己和读者的一句鸡汤🤔:集中起来的意志可以击穿顽石!
  • 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏

一、什么是图

         图是一种由节点(顶点)和连接这些节点的边构成的非线性数据结构。每个节点可以表示一个实体,而边则表示节点之间的关系。图的设计可以用于模拟现实世界中的各种复杂关系和连接,从社交网络到通信网络,都可以通过图来更好地理解和分析。

二、图的分类

        图可以根据多个维度进行分类:

  • 有向图(Directed Graph)和无向图(Undirected Graph): 有向图中的边具有方向,表示从一个节点指向另一个节点的关系;而无向图中的边没有方向,表示两个节点之间的对等关系。

  • 有权图(Weighted Graph)和无权图(Unweighted Graph): 在有权图中,每条边都有一个权重,可以表示节点之间的某种度量,如距离、成本等;而在无权图中,边没有权重,只表示连接关系。

  • 简单图和多重图(Multigraph): 简单图中不存在自环和重复的边;而多重图允许自环和可能具有相同的边。

三、图的边

        图的边是连接节点的实体,它可以包含以下信息:

  • 权重(Weight): 如果是有权图,每条边都有一个权重,代表节点之间的某种度量。
  • 方向: 在有向图中,边从一个节点指向另一个节点,有方向性;在无向图中,边没有方向,表示双向关系。
  • 标签(Label): 可以为边添加标签,表示连接的类型或特性。

        有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权,表示从一个顶点到另一个顶点的距离或花费或时间。我们称这种带权的图为网。如下图所示,即为网。

 

四、图的表达方式

        图可以使用不同的数据结构来表示:

  • 邻接矩阵(Adjacency Matrix): 使用二维数组表示图的顶点之间的连接关系。矩阵的行和列分别代表顶点,矩阵元素表示边的存在与否或权重。

                                                        图中 1 表示相连接,0 表示不相连

  • 邻接表(Adjacency List): 使用链表或数组表示图的顶点以及与其相邻的顶点。每个顶点对应一个列表,包含与之相连的顶点。

 

五、图的遍历

        图遍历是访问图中所有节点的方法,有两种主要方法:

  • 深度优先搜索(DFS): 从起始节点开始,沿着一条路径尽可能深入,直到无法继续为止,然后回溯到之前的节点,继续探索其他路径。

1.遍历思路

  • 访问顶点v;
  • 从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;
  • 重复上述两步,直至图中所有和v有路径相通的顶点都被访问到。

2.列举

        按深度优先遍历就是:A B C D E F G H(此时这条线路已经走到尽头,可是还有一个I顶点没有遍历,所以回到G,发现G的邻接点都遍历过了,再回到F,发现F的邻接点也都遍历过了,直到D顶点,发现I这个顶点没有遍历,所以把I再遍历,继续回溯,最终回到起点A。

      

  • 广度优先搜索(BFS): 从起始节点开始,先访问所有与其直接相邻的节点,然后逐层向外扩展,确保先访问离起始节点近的节点。

1.遍历思路

  • 从图中某个顶点V0出发,并访问此顶点;
  • 从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点;
  • 重复步骤2,直到全部顶点都被访问为止。

2.列举 

六、图的算法

        图的算法是一个重要的主题,包括最短路径、连通性、最大流、最小生成树等问题。比如Dijkstra算法可以用于寻找图中的最短路径,Kruskal算法和Prim算法可以用于求解最小生成树问题。这些算法的选择和应用取决于图的特性和问题的需求。

七、适用说明

        图的应用范围广泛,包括但不限于:

  • 社交网络分析: 用于分析人际关系、社区发现、信息传播等。
  • 路线规划: 帮助找到最短路径、最优路线,应用于导航和交通规划。
  • 计算机网络: 描述计算机之间的连接、拓扑结构,用于网络设计和分析。
  • 编译器: 用于构建控制流图、数据依赖图,进行代码优化和分析。

        图还可以用于生物信息学(比如在蛋白质相互作用网中寻找功能模块)、物联网(比如在设备间建立最优的通信路径)等领域。

        总之,图是一个强大的数据结构,能够捕捉和表示各种实体之间的关系,为解决各种复杂问题提供了有效的工具。不同类型的图和图遍历算法可以根据问题的性质和需求来选择使用。

        更多C语言Linux系统ARM板实战数据结构相关文章,关注专栏:

   手撕C语言

            玩转linux

                    脚踢数据结构

                            6818(ARM)开发板实战

📢写在最后

  • 今天的分享就到这啦~
  • 觉得博主写的还不错的烦劳 一键三连喔~
  • 🎉感谢关注🎉

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vellum (Discovering Houdini VellumⅡ柔体系统)学习笔记

视频地址: https://www.bilibili.com/video/BV1ve411u7nE?p3&spm_id_frompageDriver&vd_source044ee2998086c02fedb124921a28c963(搬运) 个人笔记如有错误欢迎指正;希望可以节省你的学习时间 ~享受艺术 干杯&#x1f37b…

STP知识点总结

目录 一.什么是STP协议 二.STP生成树协议产生的原因 三. STP生成树协议涉及的算法 一.802.1D 二.PVST 三.PVST 四. 快速生成树 五.MSTP 一.什么是STP协议 在一个二层交换网络中,生成一棵树型结构,逻辑的阻塞部分接口,使得从根到所有的…

深度学习入门(三):卷积神经网络(CNN)

引入 给定一张图片,计算机需要模型判断图里的东西是什么? (car、truck、airplane、ship、horse) 一、卷积神经网络整体架构 CONV:卷积计算层,线性乘积求和RELU:激励层,激活函数P…

【欧拉计划】偶数斐波那契数

题目链接:偶数斐波那契数 解法一:暴力枚举 看见题目,第一反应就是先找到小于400万的所有斐波那契数,再从这些斐波那契数中筛选出偶数进行求和。 由于递归方法求斐波那契数的时间复杂度较高,故这里采用迭代的方法。 先…

谈谈对 GMP 的简单认识

犹记得最开始学习 golang 的时候,大佬们分享 GMP 模型的时候,总感觉云里雾里,听了半天,并没有一个很清晰的概念,不知 xmd 是否会有这样的体会 虽然 golang 入门很简单,但是对于理解 golang 的设计思想和原…

python、numpy、pytorch中的浅拷贝和深拷贝

1、Python中的浅拷贝和深拷贝 import copya [1, 2, 3, 4, [11, 22, 33, [111, 222]]] b a c a.copy() d copy.deepcopy(a)print(before modify\r\n a\r\n, a, \r\n,b a\r\n, b, \r\n,c a.copy()\r\n, c, \r\n,d copy.deepcopy(a)\r\n, d, \r\n)before modify a [1, 2…

从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值

目录 1. 列表初始化initializer_list 2. 前面提到的一些知识点 2.1 小语法 2.2 STL中的一些变化 3. 右值和右值引用 3.1 右值和右值引用概念 3.2 右值引用类型的左值属性 3.3 左值引用与右值引用比较 3.4 右值引用的使用场景 3.4.1 左值引用的功能和短板 3.4.2 移动…

static相关知识点详解

文章目录 一. 修饰成员变量二. 修饰成员方法三. 修饰代码块四. 修饰类 一. 修饰成员变量 static 修饰的成员变量,称为静态成员变量,该变量不属于某个具体的对象,是所有对象所共享的。 public class Student {private String name;private sta…

【C++杂货铺】探索string的底层实现

文章目录 一、成员变量二、成员函数2.1 默认构造函数2.2 拷贝构造函数2.3 operator2.4 c_str()2.5 size()2.6 operator[ ]2.7 iterator2.8 reserve2.9 resize2.10 push_back2.11 append2.12 operator2.13 insert2.14 erase2.15 find2.16 substr2.17 operator<<2.18 opera…

【路由协议】使用按需路由协议和数据包注入的即时网络模拟传递率(PDR)、总消耗能量和节点消耗能量以及延迟研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

Windows使用MobaXterm远程访问ubuntu20.04桌面

参考ubuntu 2020.4 安装vnc 一、脚本文件 remote_setup.sh脚本文件内容&#xff1a; #! /bin/bash #参考链接&#xff1a;https://blog.csdn.net/hailangdeyingzi/article/details/124507304 sudo apt update sudo apt install x11vnc -y sudo x11vnc -storepasswd telpo.12…

二、11.系统交互

fork 函数原型是 pid_t fork(void&#xff09;&#xff0c;返回值是数字&#xff0c;该数字有可能是子进程的 pid &#xff0c;有可能是 0&#xff0c;也有可能是-1 。 1个函数有 3 种返回值&#xff0c;这是为什么呢&#xff1f;可能的原因是 Linux 中没有获取子进程 pid 的方…

主程技术分享: 游戏项目帧同步,状态同步如何选

网络游戏开发项目中帧同步,状态同步如何选&#xff1f; 网络游戏的核心技术之一就是玩家的网络同步,主流的网络同步有”帧同步”与”状态同步”。今天我们来分析一下这两种同步模式。同时教大家如何在自己的项目中采用最合适的同步方式。接下来从以下3个方面来阐述: 对啦&…

如何拉取Gitee / GitHub上的Unity项目并成功运行

前言 由于目前大部分人使用的仓库都是Gitee或者是GitHub&#xff0c;包括小编的公司所使用的项目仓库也包括了Gitee&#xff1b;我们需要学习技术栈时都会去百度或者是去GitHub上看看别人的项目观摩学习&#xff0c;可能很多小白在遇到拉取代码时出现各种问题&#xff0c;或者…

外包干了2年,彻底废了...

先说一下自己的情况。大专生&#xff0c;17年通过校招进入湖南某软件公司&#xff0c;干了接近2年的点点点&#xff0c;今年年上旬&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01;而我已经在一个企业干了五年的功能测试…

mongodb集群

端口192.168.115.3 192.168.115.4 1192.168.115.5 下载MongoDB软件包版本为4.2.14并安装 rpm -ih --force --nodeps *.rpm 2创建文件夹mkdir -p /opt/local/mongo-cluster/conf 3.在目录里创建配置文件cd /opt/local/mongo-cluster/conf …

线性数据结构:数组与链表的探索与应用

文章目录 1. 数组&#xff1a;连续存储的有序元素集合1.1 创建和访问数组1.2 数组的搜索与排序 2. 链表&#xff1a;非连续存储的动态数据结构2.1 单链表与双链表2.2 链表的操作与应用 3. 数组与链表的比较与应用3.1 数组与链表的比较3.2 数组与链表的应用 4. 总结与展望 &…

leetcode414. 第三大的数

题目&#xff1a; 给你一个非空数组&#xff0c;返回此数组中 第三大的数 。如果不存在&#xff0c;则返回数组中最大的数。 示例 1&#xff1a; 输入&#xff1a;[3, 2, 1] 输出&#xff1a;1 解释&#xff1a;第三大的数是 1 。 示例 2&#xff1a; 输入&#xff1a;[1, …

字符设备驱动实例(ADC驱动)

四、ADC驱动 ADC是将模拟信号转换为数字信号的转换器&#xff0c;在 Exynos4412 上有一个ADC&#xff0c;其主要的特性如下。 (1)量程为0~1.8V。 (2)精度有 10bit 和 12bit 可选。 (3)采样时钟最高为5MHz&#xff0c;转换速率最高为1MSPS (4)具有四路模拟输入&#xff0c;同一时…

【LVS集群】

目录 一、集群概述 1.负载均衡技术类型 2.负载均衡实现方式 二、LVS结构 1.三层结构 2.架构对象 三、LVS工作模式 四、LVS负载均衡算法 1.静态负载均衡 2.动态负载均衡 五、ipvsadm命令详解 1. -A 2. -D 3. -L 4. -a 5. -d 6. -l 7. -t 8. -s 9. -r 10. -…