数据结构不再难懂：带你轻松搞定图

数据结构入门学习（全是干货）——图

1 图

1.1 什么是图

图是一种用于表示多对多关系的数学模型。它由一组顶点和一组边构成，用于描述事物之间的复杂关联。

  • 顶点：通常用 V (Vertex) 表示，代表事物或对象。
  • 边：通常用 E (Edge) 表示，代表顶点之间的连接。边可以是无向的（双向）或有向的（单向）。
    • 无向边：(v, w)，表示顶点 v 和 w 之间相互连接，没有方向性。
    • 有向边：<v, w>，表示从 v 到 w 有方向的连接。
图的抽象数据类型 (ADT)

  • 类型名称：图 (Graph)

  • 数据对象：G(V, E) 表示图由顶点集合 V 和边集合 E 构成。顶点集合不能为空，但边可以为空。

  • 操作：

    • 添加顶点和边。
    • 遍历图的所有顶点和边。
    • 查询图的属性，如顶点的度数、两顶点之间是否存在边等。
    
1. Graph Create()：建立并返回空图
2. Graph InsertVertex(Graph G, Vertex v)：将v插入G
3. Graph InsertEdge(Graph G, Edge e)：将e插入G;
4. void DFS(Graph G,Vertex v)：从顶点v出发深度优先遍历图G;
5. void BFS(Graph G,Vertex v)：从顶点v出发宽度优先遍历图G;
6. void ShortestPath(Graph G,Vertex v,int Dist[])：计算图G中顶点v到任意其他顶点的最短距离
7. void MST(Graph G)：计算图G的最小生成树
常见术语
  1. 无向图：没有方向的边连接顶点。
  2. 有向图：每条边都有方向，如箭头从一个顶点指向另一个顶点。
  3. 权重：边上标记的数字，通常表示该连接的成本、距离或权值。
  4. 网络：带权重的图称为网络。

1.2 图的表示法——邻接矩阵

邻接矩阵是一种常用的表示图的方法，使用二维数组表示顶点之间的连接关系。

  • 无向图：邻接矩阵是对称的。matrix[i][j] 表示顶点 i 和顶点 j 之间是否有边。
  • 有向图：矩阵的行和列代表了方向关系，matrix[i][j] 表示从顶点 i 到顶点 j 是否有边。

怎么在程序中表示一个图

邻接矩阵的优缺点

  • 优点：

    • 直观、简单，易于理解和实现。
    • 检查任意两个顶点间是否有边十分方便。
    • 快速找到某一顶点的邻接点和计算顶点的度（有向图中分为出度和入度）。

  • 缺点：

    • 对于稀疏图（顶点多而边少），邻接矩阵会浪费大量存储空间。
    • 对稀疏图，统计边的数量会比较耗时。

1.3 图的表示法——邻接表

邻接表是另一种表示图的方法，适用于稀疏图。

  • 每个顶点对应一个链表，链表中的节点存储的是该顶点的所有邻接点。
  • 无向图：每条边 (v, w) 会在 v 和 w 的链表中各自存储一次。
  • 有向图：每条有向边 <v, w> 只会在 v 的链表中存储。

邻接表的优缺点

  • 优点：

    • 更适合存储稀疏图，节省空间。
    • 找出一个顶点的所有邻接点非常高效。
    • 适合计算顶点的度。

  • 缺点：

    • 检查任意两个顶点是否相邻需要遍历链表，效率不如邻接矩阵。
    • 不能快速统计边的数量。

2 图的遍历

图的遍历就是访问图中每个顶点一次，遍历过程中要确保每个顶点只访问一次。图的遍历通常有两种主要方法：深度优先搜索 (DFS) 和广度优先搜索 (BFS)。

2.1 图的遍历——深度优先搜索 (DFS)

深度优先搜索是一种递归的遍历方法，沿着图中的一条路径一直走到底，再回溯到上一层节点，继续沿另一条路径遍历，直至遍历所有顶点。

DFS 算法步骤：
  1. 从某个顶点开始，标记为已访问。
  2. 递归访问该顶点的未访问邻接点，直到所有邻接点都被访问。
  3. 回溯到上一个顶点，重复上述过程，直到遍历完所有顶点。

DFS 的实现可以用递归或显示栈来管理回溯过程。

void DFS(Vertex V)//从迷宫的节点出来
{visited[V] = true;//给每个节点一个变量，true相当于灯亮了，false则是熄灭状态for(V的每个邻接点W)//视野看得到的灯if(!visited[W])//检测是否还有没点亮的DFS(W);//递归调用
}//类似树的先序遍历
若有N个顶点、E条边，时间复杂度是用邻接表存储图，有O(N+E)//对每个点访问了一次，每条边也访问了一次用邻接矩阵存储图，有O(N²)//V对应的每个邻接点W都要访问一遍
DFS 的时间复杂度：
  • 对于使用邻接表存储的图，时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。
  • 对于使用邻接矩阵存储的图，时间复杂度为 O(V^2)。

2.2 图的遍历——广度优先搜索 (BFS)

广度优先搜索是一种层次遍历方法，从某个顶点出发，依次访问所有距离该顶点为一层的节点，然后再访问下一层节点，直到所有节点都被访问。

BFS 算法步骤：

void BFS(Vertex V)
{visited[V] = true;Enqueue(V,Q);//压到队列里while(!IsEmpty(Q)){V = Dequeue(Q);//每次循环弹出一个节点for(V的每个邻接点W)if(!visited[W]){//没有访问过的去访问将其压入队列中visited[W] = true;Enqueue(W,Q);}}
}
  1. 从某个顶点开始，标记为已访问并将其加入队列。
  2. 从队列中取出顶点，访问它的所有未访问的邻接点，并将这些邻接点加入队列。
  3. 重复上述过程，直到队列为空，表示所有顶点都已访问。
BFS 的时间复杂度：
  • 对于使用邻接表存储的图，时间复杂度为 O(V + E)。
  • 对于使用邻接矩阵存储的图，时间复杂度为 O(V^2)。

2.3 为什么需要两种遍历方法？

  • DFS：适用于需要尽可能深入遍历的情况，特别是当需要探索路径时，比如解决迷宫问题。
  • BFS：适用于需要层次遍历的情况，如寻找最短路径等。

2.4 图不连通怎么办？

在遍历图时，如果图不连通，意味着某些顶点无法通过一条路径到达其他顶点。此时，需要对每个连通分量分别进行遍历。

连通的相关概念：
  • 连通图：在无向图中，任意两个顶点之间都有路径。
  • 连通分量：无向图中的极大连通子图。
  • 回路：从一个顶点出发，经过若干条边回到起始顶点的路径。

在遍历非连通图时，可以使用 DFS 或 BFS 多次遍历，每次从未访问的顶点开始，直到遍历完所有连通分量。

3 应用实例：拯救 007

在这个应用实例中，可以通过图的遍历（DFS 或 BFS）来模拟 007 从一个顶点逃脱到另一个顶点的场景。目标是从起始顶点开始，找到一条通往安全点的路径。


void Save007(Graph G)
{for(each V in G){if(!visited[V] && FirstJump(V)){//这个FirstJump(V)是007第一跳有没有可能从孤岛跳到V上有没有可能，有且没踩过就跳上去answer = DFS(V);//or BFS(V)if(answer == YES) break;0}}if(answer == YES) output("Yes");else output("No");
}
DFS 解决方案：
  1. 以起点作为图中的一个顶点。
  2. 使用 DFS 递归地查找逃脱路径。
  3. 如果找到了逃脱路径，输出路径；如果没有找到，则输出“没有路径”。

void DFS(Vertex V)
{visited[V] = true;//表示鳄鱼头踩过了if(IOsSafe(V)) answer = YES;else{for(each W in G )if(!visited[W] && Jump(V,W)){//可以从V jump跳到这个w上面，作用是算V到W之间的距离是不是小于007可以跳跃最大距离answer = DFS(W);//递归 if(answer == YES) break;}}return answer;
}
BFS 解决方案：
  1. 从起点开始，使用队列存储每个可能的逃脱路径。
  2. 广度优先地寻找最短逃脱路径。
  3. 输出找到的路径，如果没有找到，输出“没有路径”。

4 应用实例：六度空间理论

六度空间理论 (Six Degrees of Separation) 表示在一个社交网络中，任意两个人之间通过不超过六个人的中间连接，就可以建立联系。

社交网络图：
  1. 将社交网络建模为一个无向图，顶点表示人，边表示两个人之间的社交联系。
  2. 通过图的遍历（如 BFS）计算每个人到其他人的最短路径，验证六度空间理论的正确性。
  3. 计算符合六度空间理论的顶点数量占总顶点数量的百分比。
算法思路
1.对每个节点进行广度优先搜索
2.搜索过程中累计访问的节点数
3.需要记录"层"数,仅计算6层以内的节点数void SDS()
{for(each V in G){count += BFS(V);Output = (count/N);}
}//结合最初的BFSvoid BFS(Vertex V)
{visited[V] = true;count = 1;Enqueue(V,Q);//压到队列里while(!IsEmpty(Q)){V = Dequeue(Q);//每次循环弹出一个节点for(V的每个邻接点W)if(!visited[W]){//没有访问过的去访问将其压入队列中visited[W] = true;Enqueue(W,Q);count++;}}return count;
}

5 小白专场：如何用 C 语言建立图

在 C 语言中，图的实现通常使用邻接矩阵或邻接表来存储顶点和边的关系。

5.1 邻接矩阵实现

邻接矩阵的结构：
typedef struct {int VertexNum;int EdgeNum;int Matrix[MAXV][MAXV]; // 邻接矩阵
} MGraph;
初始化图：
MGraph* CreateGraph(int VertexNum) {MGraph *Graph = (MGraph *)malloc(sizeof(MGraph));Graph->VertexNum = VertexNum;Graph->EdgeNum = 0;for (int i = 0; i < VertexNum; i++) {for (int j = 0; j < VertexNum; j++) {Graph->Matrix[i][j] = 0; // 初始化无边的图}}return Graph;
}
插入边：
void InsertEdge(MGraph *Graph, int v1, int v2, int weight) {Graph->Matrix[v1][v2] = weight; // 插入边 v1 -> v2Graph->EdgeNum++;
}

5.2 邻接表实现

邻接表的结构：
typedef struct AdjVNode {int AdjV;struct AdjVNode *Next;
} AdjVNode;typedef struct VNode {AdjVNode *FirstEdge;
} VNode, AdjList[MAXV];typedef struct {AdjList G;int VertexNum;int EdgeNum;
} LGraph;
初始化邻接表：
LGraph* CreateGraph(int VertexNum) {LGraph *Graph = (LGraph *)malloc(sizeof(LGraph));Graph->VertexNum = VertexNum;Graph->EdgeNum = 0;for (int i = 0; i < VertexNum; i++) {Graph->G[i].FirstEdge = NULL;}return Graph;
}
插入边：
void InsertEdge(LGraph *Graph, int v1, int v2) {AdjVNode *NewNode = (AdjVNode *)malloc(sizeof(AdjVNode));NewNode->AdjV = v2;NewNode->Next = Graph->G[v1].FirstEdge;Graph->G[v1].FirstEdge = NewNode;Graph->EdgeNum++;
}

通过邻接矩阵和邻接表两种方式，可以高效地存储和操作图结构，并进一步应用到图的遍历和各种图算法的实现中。

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

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

相关文章

uniapp+renderJS+google map开发安卓版APP非小程序

uniapp+renderJS+google map开发安卓版APP非小程序

背景需求 需要在uniapp中接入google地图，研究了一番，都没有找到合适的，现在说一下教程。 效果图 前期工作 这两点缺一不可，否则你啥也看不到。 1、电脑安装L-O-U梯 用于访问G-OO-G-LE的API或者创建google map key。 2、手机安装L-O-U梯 用于显示google地图。我就是手…
阅读更多...
Linux中的进程入门

Linux中的进程入门

冯诺依曼体系结构 操作系统(Operator System) 进程控制块&#xff08;PCB&#xff09; struct task_struct{//该进程的所有属性//该进程对应的代码和属性地址struct task_struct* next; }; struct task_struct 内核结构体——>创建内核结构体对象(task_struct&#xff09;…
阅读更多...
LinuxC高级作业2

LinuxC高级作业2

1.整理思维导图 2.做一套笔试题 一&#xff1a; 1.cd .. mkdir dir1 cd dir1 touch file1 2.cp ~/mnt/dir1/ -r * ~/home/dir2/ 3.pwd 4.ls -l 5.ifconfig 6.top 10.find /usr -type f -name "*name*" 11.:wq 13.df -h 14.tar -xzvf tmp.tar.gz 15.sudo c…
阅读更多...
登录校验(令牌，过滤器，拦截器使用详解)

登录校验(令牌，过滤器，拦截器使用详解)

文章目录 前言一、会话技术1. Cookie2. Session3. 令牌 二、JWT令牌1. 简介 二、过滤器Filter1. 简介2. 快速入门3. 执行流程4. 使用示例5. 为什么自定义的Filter类不需要使用Component 四、拦截器Interceptor1. 介绍2. 入门程序3. Interceptor详解 前言 该篇详细对SpringBoot…
阅读更多...
串口助手的qt实现思路

串口助手的qt实现思路

要求实现如下功能&#xff1a; 获取串口号&#xff1a; foreach (const QSerialPortInfo &serialPortInfo, QSerialPortInfo::availablePorts()) {qDebug() << "Port: " << serialPortInfo.portName(); // e.g. "COM1"qDebug() <<…
阅读更多...
GeoPandas在地理空间数据分析中的应用

GeoPandas在地理空间数据分析中的应用

GeoPandas是一个开源的Python库&#xff0c;专门用于处理和分析地理空间数据。它建立在Pandas库的基础上&#xff0c;扩展了Pandas的数据类型&#xff0c;使得用户能够在Python中方便地进行GIS操作。GeoPandas的核心数据结构是GeoDataFrame&#xff0c;它是Pandas的DataFrame的…
阅读更多...
射击靶标检测系统源码分享

射击靶标检测系统源码分享

射击靶标检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vis…
阅读更多...
VScode开发GD32移植(标准库通用)，保姆级！！！！！！！

VScode开发GD32移植(标准库通用)，保姆级！！！！！！！

VScode开发GD32移植(标准库通用)&#xff0c;保姆级&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 文章目录 VScode开发GD32移植(标准库通用)&#xff0c;保姆级&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#…
阅读更多...
哪个牌子的麦克风好用？无线麦克风避坑指南：五大常见问题

哪个牌子的麦克风好用？无线麦克风避坑指南：五大常见问题

随着短视频行业的兴起&#xff0c;和视频拍摄有关的外设也被推到了风口浪尖上&#xff0c;而麦克风作为视频拍摄或者现场直播使用的主要拾音工具&#xff0c;自然成为了大家非常关注的一个摄影外设工具&#xff0c;毕竟一款好的拾音工具能够给视频创作者或者直播博主带来更好的…
阅读更多...
基于PHP的CRM管理系统源码/客户关系管理CRM系统源码/php源码/附安装教程

基于PHP的CRM管理系统源码/客户关系管理CRM系统源码/php源码/附安装教程

源码简介&#xff1a; 这是一款基于PHP开发的CRM管理系统源码&#xff0c;全称客户关系管理CRM系统源码&#xff0c;它是由php源码开发的&#xff0c;还附带了一整套详细的安装教程哦&#xff01; 功能亮点&#xff1a; 1、公海管理神器&#xff1a;不仅能搞定公海类型&…
阅读更多...
OpenCV特征检测(6)对初步检测到的角点位置进行亚像素级别的精炼函数cornerSubPix()的使用

OpenCV特征检测(6)对初步检测到的角点位置进行亚像素级别的精炼函数cornerSubPix()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 细化角点的位置。 该函数迭代以找到角点或径向鞍点的亚像素级准确位置&#xff0c;如 93中所述&#xff0c;并如下图所示。 亚像素级准确的角点…
阅读更多...
Linux：虚拟文件系统/proc和self进程

Linux：虚拟文件系统/proc和self进程

相关阅读 Linuxhttps://blog.csdn.net/weixin_45791458/category_12234591.html?spm1001.2014.3001.5482 /proc目录 在Linux操作系统中&#xff0c;目录/proc是一个虚拟文件系统&#xff0c;称为procfc&#xff0c;用于访问内核和系统的实时状态信息。这个文件系统不同于常规…
阅读更多...
SpringMVC1~~~

SpringMVC1~~~

快速入门 spring容器文件 在src下就是applicationContext-mvc.xml&#xff0c;需要在web.xml指定<init-param>&#xff0c;给DispatcherServlet指定要去操作的spring容器文件 在WEB-INF下就是xxx-servlet.xml&#xff0c;不需要在web.xml指定<init-param>,如果我们…
阅读更多...
Qt：智能指针QScopedPointer 的使用(以及如何写一个QScopedPointer )

Qt：智能指针QScopedPointer 的使用(以及如何写一个QScopedPointer )

前言 本文讲述QScopedPointer 的使用&#xff0c;以及自己如何写一个QScopedPointer . 正文 QScopedPointer 的常用方法 以下是 QScopedPointer 的一些常用方法及其详细说明&#xff1a; 构造函数&#xff1a; QScopedPointer<T> ptr(new T);用于创建一个 QScopedPoi…
阅读更多...
使用 Elasticsearch Reindex API 迁移数据

使用 Elasticsearch Reindex API 迁移数据

使用 Elasticsearch Reindex API 迁移数据 在 Elasticsearch 中&#xff0c;随着需求的变化&#xff0c;可能需要对索引进行重建或更新。这通常涉及创建新索引、迁移数据等步骤。本文介绍如何使用 Reindex API 将旧索引中的数据迁移到新索引中 一、步骤概述 创建新索引&#…
阅读更多...
R18 NES 之SSB-less SCell operation for inter-band CA

R18 NES 之SSB-less SCell operation for inter-band CA

在TR 21.918 Summary of Rel-18 Work Items 中可以看到SSB-less SCell operation for inter-band CA 是Network energy savings for NR 的一部分，其中还包括cell DTX/DRX 等等其他内容。 网络节能是 5G/NR 成功的关键，可以减少对环境的影响（温室气体排放）并节省运营成本。R…
阅读更多...
『功能项目』伤害数字UI显示【53】

『功能项目』伤害数字UI显示【53】

我们打开上一篇52眩晕图标显示的项目&#xff0c; 本章要做的事情是在Boss受到伤害时显示伤害数字 首先打开Boss01预制体空间在Canvas下创建一个Text文本 设置Text文本 重命名为DamageUI 设置为隐藏 编写脚本&#xff1a;PlayerCtrl.cs 运行项目 本章做了怪物受伤血量的显示UI…
阅读更多...
详细分析Java中的ObjectMapper基本知识（附Demo）

详细分析Java中的ObjectMapper基本知识（附Demo）

目录 1. 基本知识2. 基本操作2.1 转换Java对象为JSON2.2 转换JSON为Java对象 3. 拓展 1. 基本知识 ObjectMapper 是 Jackson 数据处理库中的核心类之一&#xff0c;主要用于将 Java 对象转换为 JSON 和将 JSON 转换为 Java 对象 Jackson 是当前最流行的 JSON 处理库之一&…
阅读更多...
DOCKER 数据库管理软件自己开发--———未来之窗行业应用跨平台架构

DOCKER 数据库管理软件自己开发--———未来之窗行业应用跨平台架构

- 数据异地容灾服务--未来之窗智慧数据服务 DATA REMOTE DISASTER RECOVERY SERVICE -CyberWin Future Docker-数据查看 CyberWin DATA Viewer 1.docker 样式 mysqli://root:密码172.17.0.2:端口/数据库 阿雪技术观 拥抱开源与共享&#xff0c;见证科技进步奇迹&#xff0c;…
阅读更多...
mat （Eclipse Memory Analyzer Tool）使用以及详解

mat （Eclipse Memory Analyzer Tool）使用以及详解

前言 在Java开发中&#xff0c;内存问题往往不易被发现&#xff0c;但它们可能导致应用性能下降甚至崩溃。Eclipse Memory Analyzer Tool&#xff08;MAT&#xff09;是一个强大的开源工具&#xff0c;专门用于分析Java堆转储&#xff08;heap dumps&#xff09;文件&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023