数据结构—图的存储结构

6.图

回顾：数据的逻辑结构

集合——数据元素间除 “同属于一个集合” 外，无其他关系。

线性结构——一个对一个，如线性表、栈、队列

树形结构——一个对多个，如树

图形结构——多个对多个，如图

《数据结构C语言版》——绪论_计蒙不吃鱼的博客-CSDN博客_数据结构是带有结构的各数据项的集合

6.1图的定义和术语

图: G=(V,E)
    V:顶点（数据元素）的有穷非空集合； 
    E:边的有穷集合。

无向图：每条边都是无方向的；

有向图：每条边都是有方向的。

networkx画有向图和无向图_静静_jingjing的博客-CSDN博客_networkx画有向图

完全图：任意两个点都有一条边相连。

无向完全图：n 个顶点，n(n-1)/2条边

有向完全图：n 个顶点，n(n-1)条边

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NdIzTjfy-1691238142116)(https://ts1.cn.mm.bing.net/th/id/R-C.bf9aad94a55a06758f0d0d4a2aa083bf?rik=VscqICD0R7hR%2fA&riu=http%3a%2f%2fdata.biancheng.net%2fuploads%2fallimg%2f190103%2f2-1Z103210110O8.gif&ehk=Oi7hLl6AEIQ%2f1UfWj%2fAO6riRvAKN51BTFvzwxhq%2bGSE%3d&risl=&pid=ImgRaw&r=0)]

稀疏图：有很少边或弧的图（e<nlogn）。

稠密图：有较多边或弧的图。

网：边/弧带权的图。

邻接：有边/弧相连的两个顶点之间的关系。

​ 存在（vi,vj），则称vi和vj互为邻接点；

​ 存在 <vi,vj>，则称vi邻接到vj，vj邻接到vi

关联（依附）：边/弧与顶点之间的关系。

​ 存在（vi,vj）/ <vi,vj>，则称该边/弧关联于vi和vj

顶点的度：与该顶点相关联的边的数目，记为TD(v)

​ 在有向图中，顶点的度等于该顶点的入度与出度之和。

​ 顶点v的入度是以v为顶点的有向边的条数，记作ID(v)

​ 顶点v的出度是以v为始点的有向边的条数，记作OD(v)

查看源图像

问：当有向图中仅1个顶点的入度为0，其余顶点的入度均为1，此时是何形状？

答：是树！而且是一棵有向树！

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rztk0NIk-1691238142118)(https://ts1.cn.mm.bing.net/th/id/R-C.4f3bd2363f037cff739f8e388db9b321?rik=W0cQmZrsrYAcEA&riu=http%3a%2f%2fivr-ahnu.cn%2flectures%2fos%2fimages%2f24.jpg&ehk=rL%2blBOSUE1GCU30Sl09HWmQqTnbVhZDKEDVVUvJxi1U%3d&risl=&pid=ImgRaw&r=0)]

路径：接续的边构成的顶点序列。

路径长度：路径上边或弧的数目/权值之和。

回路（环）：第一个顶点和最后一个顶点相同的路径。

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。

简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径。

Graph(1)--图的基本概念_Nicholem的博客-CSDN博客_graph的定义

连通图（强连通图）

​ 在无（有）向图G=(V,{E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。

数据结构——图_若尘的博客-CSDN博客_narcnum

权与网

​ 图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。

​ 带权的图称为网。

子图

​ 设有两个图G=(V,{E})、G1=(V1,{E1})，若V1⊆V,E1⊆E，则称G1是G的子图。

​ 例：（b），（c）是（a）的子图

img

连通分量（强连通分量）

  • 无向图G的极大连通子图称为G的连通分量。

    极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。

    img

  • 有向图G的极大强连通子图称为G的强连通分量。

    极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。

    img

  • 极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。

  • 生成树：包含无向图G所有顶点的极小连通子图。

  • 生成森林：对非连通图，由各个连通分量的生成树的集合。

    img

6.2图的存储结构

图的逻辑结构：多对多

图没有顺序存储结构，但可以借助二维数组来表示元素间的关系。

6.2.1邻接矩阵

1、数组（邻接矩阵）表示法
  • 建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。
    • 设图A=(V,E)有 n 个顶点。
    • 图的邻接矩阵是一个二维数组。
无向图的邻接矩阵表示法

存在关系记为1，没有关系记为0

算法学习——图之无权图_Talk is cheap, show me the code!-CSDN博客_无权图

分析1：无向图的邻接矩阵是对称的。

分析2：顶点 i 的度 = 第 i 行（列）中1的个数。

特别：完全图的邻接矩阵中，对角元素为0，其余为1。

有向图的邻接矩阵表示方法

算法学习——图之无权图_Talk is cheap, show me the code!-CSDN博客_无权图

注：在有向图的邻接矩阵中，

​ 第 i 行含义：以结点vi为尾的弧（即出度边）；

​ 第 i 列含义：以结点vi为头的弧（即入度边）。

分析1：有向图的邻接矩阵可能是不对称的。

分析2：顶点的出度 = 第i行元素之和

​ 顶点的入度 = 第i列元素之和

​ 顶点的度 = 第i行元素之和 + 第i列元素之和

网（即有权图）的邻接矩阵表示法

邻接矩阵_diviner_s的博客-CSDN博客

邻接矩阵存储表示，用两个数组分别存储顶点表和邻接矩阵。

#define MaxInt 32767
#define MVNum 100  //最大顶点数
typedef char VerTexType;//设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
typedef struct{
  VerTexType vexs[MVNum];//顶点表
  ArcType arcs[MVNum][MVNum];//邻接矩阵
  int vexnum,arcnum;
}AMGraph;
2、采用邻接矩阵表示法创建无向网

算法思想：

  1. 输入总顶点数和总边数。
  2. 依次输入点的信息存入顶点表中。
  3. 初始化邻接矩阵，使每个权值初始化为最大值。
  4. 构造邻接矩阵。
Status CreateUDN(AMGraph &G){
  cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
  for(i=0;i<G.vexnum;++i)
    cin>>G.vexs[i];//依次输入点的信息
  for(i=0;i<G,vexnum;++i)
    for(j=0;j<G.vexnum;++j)
      G.arcs[i][j]=MaxInt;//边的权值均设置为极大值
  for(k=0;k<G.arcnum;++k){
    cin>>v1>>v2>>w;//输入一条边所依附的顶点及边的权值
    i=LocateVex(G,v1);
    j=LocateVex(G,v2);//确定v1和v2在G中的位置
    G.arcs[i][j]=w;//边<v1，v2>的权值置为w
    G.arcs[j][i]=G.arcs[i][j];//置<v1，v2>的对称边<v2,v1>的权值为w
  }
  return OK;
}

补充算法：在图中查找顶点

int LocateVex(AMGraph G,VertexType u){
  int i;
  for(i=0;i<G.vexnum;++i)
    if(u==G.vexs[i]) return i;
  return -1;
}
3、邻接矩阵的优缺点

邻接矩阵_diviner_ss的博客-CSDN博客_邻接矩阵

邻接矩阵有什么优点？

  • 直观、简单、好理解
  • 方便检查任意一对顶点间是否存在边
  • 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
  • 方便计算任一顶点的“度”（从该店发出的边数为“出度”，指向该点的边数为“入度”）
    • 无向图：对应行（或列）非0元素的个数
    • 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”。

邻接矩阵的缺点？

  • 不便于增加和删除顶点

  • 浪费空间——存稀疏图（点很多而边很少）有大量无效元素

    ​ ——对稠密图（特别是完全图）还是很合算的

  • 浪费时间——统计稀疏图中一共有多少条边。

6.2.2邻接表

1、邻接表表示法（链式）

img

  • 顶点：按编号顺序将顶点数据存储在一维数组中；
  • 关联同一顶点的边（以顶点为尾的弧）：用线性链表存储
无向图邻接表

特点：

  • 邻接表不唯一

  • 若无向图中有n个顶点，e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。

  • 无向图中顶点的度为第i个单链表中的结点数。

img

有向图邻接表

特点：找出度易，找入度难

  • 顶点的出度就是第i个单链表中的结点个数。
  • 顶点的入度为整个单链表中邻接点域值是i-1的结点个数。

数据结构——图的邻接表实现_舟浔川的博客-CSDN博客_数据结构有向图的邻接链表

图的邻接表存储表示

顶点的结点结构

typedef struct VNode{
  VerTexType data;//顶点信息
  ArcNode *firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];//AdjList表示邻接表类型

说明：例如，AdjList v; 相当于：VNode v[MVNum];

弧（边）的结点结构

#define MVNum 100
typedef struct ArcNode{//边结点
  int adjvex;//该边所指向的顶点的位置
  struct ArcNode *nextarc;//指向下一条边的指针
  OtherInfo info;//和边相关的信息
}ArcNode;

图的结构定义

typedef struct{
  AdjList vertices;
  int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
2、采用邻接表创建无向网

算法思想：

  1. 输入总顶点数和总边数

  2. 建立顶点表

    依次输入点的信息存入顶点表中

    使每个表头结点的指针域初始化为NULL

  3. 创建邻接表

    依次输入每条边依附的两个顶点

    确定两个顶点的序号i和j，建立边结点

    将此边结点分别插入到vi和vj对应的两个边链表的头部

Status CreateUDG(ALGraph &G){
  cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
  for(i=0;i<G.vexnum;++i){//输入各点，构造表头结点表
    cin>>G.vertices[i].data;//输入顶点值
    G.vertices[i].firstarc=NULL;//初始化表头结点的指针域
  }
  for(k=0;k<G.arcnum;++k){//输入各边，构造邻接表
    cin>>v1>>v2;//输入一条边依附的两个顶点
    i=LocateVex(G,v1);
    j=LocateVex(G.v2);
    p1=new ArcNode;//生成一个新的边结点*p1
    p1->adjvex=j;//邻接点序号为j
    pi->nextarc=G.vertices[i].firstarc;
    G.vertices[i].firstarc=p1;//将新结点*p1插入顶点vi的边表头部
    p2=new ArcNode;//生成另一个对称的新的边结点
    p2->adjvex=i;
    p2->nextarc=G.vertices[j].firstarc;
    G.vertices[j].firstarc=p2;//将新结点*p2插入顶点vj的边表头部
  }
  return OK;
}
3、邻接表特点

  • 方便找任一顶点的所有“邻接点”

  • 节约稀疏图的空间

    • 需要N个头指针 + 2E个结点（每个结点至少2个域）

  • 方便计算任一顶点的“度”

    • 对无向图：是的
    • 对有向图：只能计算“出度”；需要构造“逆邻接表”（纯指向自己的边）来方便计算“入度”

  • 不方便检查任意一对顶点间是否存在边

6.2.3邻接矩阵与邻接表的关系

图的存储与实现_贪婪的君子-CSDN博客

联系：邻接表中每个链表对应与邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。

区别：

  1. 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），当邻接表不唯一（链接次序与顶点编号无关）。
  2. 邻接矩阵的空间复杂度为O(n2)，而邻接表的空间复杂度为O(n+e)。

用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图。

6.2.4十字链表

​ 十字链表是有向图的另一种链式存储结构。我们也可以把她看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。

​ 有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

img

img

6.2.5邻接多重表

邻接表优点：容易求得顶点和边的信息。

​ 缺点：某些操作不方便（如：删除一条边需找表示此边的两个结点）。

邻接表中，任何一条边，都会出现两次

img

img

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

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

相关文章

QT - 建立页面

QT - 建立页面

一、生成页面 二、实现 1.LineEdit 是一个单行输入文本框&#xff0c;为用户提供了比较多的编辑功能&#xff0c;例如选择复制、粘贴。 修改echomode属性为password Push Button(常规按钮) 三、程序 声明全局变量&#xff0c;属于MainWindow private: // 定义了一个指向Ma…
阅读更多...
使用vite创建Vue/React前端项目，配置@别名和Sass样式，又快又方便

使用vite创建Vue/React前端项目，配置@别名和Sass样式，又快又方便

Vite官方网站&#xff1a;Vite | 下一代的前端工具链 Vite 并不是基于 Webpack 的&#xff0c;它有自己的开发服务器&#xff0c;利用浏览器中的原生 ES 模块。这种架构使得 Vite 比 Webpack 的开发服务器快了好几个数量级。Vite 采用 Rollup 进行构建&#xff0c;速度也更快…
阅读更多...
SAM 大模型Colab快速上手【Segment Anything Model】

SAM 大模型Colab快速上手【Segment Anything Model】

Google Colab 是一个基于云的 Jupyter 笔记本环境&#xff0c;允许您通过浏览器编写、运行和共享 Python 代码。 它就像 Google 文档&#xff0c;但用于代码。 通过免费版本的 Google Colab&#xff0c;你可以获得带有约 16GPU VRAM 的 Nvidia Tesla T4 GPU&#xff0c;这对于…
阅读更多...
SpringMVC的架构有什么优势？——表单和数据校验（四）

SpringMVC的架构有什么优势？——表单和数据校验（四）

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 「推荐专栏」&#xff1a; ★java一站式服务 ★ ★ React从入门到精通★ ★前端炫酷代码分享 ★ ★ 从0到英雄&#xff0c;vue成神之路★ ★ uniapp-从构建到提升★ ★ 从0到英雄&#xff…
阅读更多...
算法通关村——迭代实现二叉树的前中后序遍历

算法通关村——迭代实现二叉树的前中后序遍历

前言 递归就是每次执行方法调用都会先把当前的局部变量、参数值和返回地址等压入栈中&#xff0c;后面在递归返回的时候&#xff0c;从栈顶弹出上一层的各项参数继续执行&#xff0c;这就是递归为什么能够自动返回并执行上一层的方法的原因。因此&#xff0c;我们也可以模拟一个…
阅读更多...
路由器工作原理(第二十九课)

路由器工作原理(第二十九课)

路由器工作原理(第二十九课) 一图胜过千言 1） 路由：数据从一个网络到另外一个网络之间转发数据包的过程称为路由 2） 路由器：连接不同网络，实现不同网段之间的通信 3）路由表：路由器选择数据的传输路径的依据 原始的路由表 Destination/Mask Proto Pre Cost …
阅读更多...
1706. 球会落何处；875. 爱吃香蕉的珂珂；1914. 循环轮转矩阵

1706. 球会落何处；875. 爱吃香蕉的珂珂；1914. 循环轮转矩阵

1706. 球会落何处 核心思想&#xff1a;判断什么时候球会被卡住&#xff0c;1&#xff0c;当球在最左边的时候&#xff0c;挡板是向左的。2&#xff0c;当球在最右边的时候&#xff0c;挡板是向右的。3&#xff0c;当球当前的挡板是向左的&#xff0c;但是同一行的另一个挡板是…
阅读更多...
【王树森】深度强化学习(DRL)课程笔记：P1 基本概念（含gym安装）

【王树森】深度强化学习(DRL)课程笔记：P1 基本概念（含gym安装）

课程信息 课程主讲&#xff1a;王树森&#xff08;史蒂文斯理工学院计算机科学系的终身制助理教授&#xff09; 课程内容&#xff1a;基本概念、价值学习、策略学习、Actor-Critic方法、AlphaGo、Monte Carlo (蒙特卡洛) 课程资料&#xff1a;https://github.com/wangshusen/D…
阅读更多...
用spinal写《自己动手写cpu》中的代码--pc_reg模块

用spinal写《自己动手写cpu》中的代码--pc_reg模块

一 预期代码 二 spinal代码 package oriimport spinal.core._class pc_reg(width: Int) extends Component{val io = new Bundle {val pc = out UInt(width bits)val ce = out UInt (1 bits)val clk = in Bool()val rst = in Bool()}val ceClkDomain = ClockDomain(clock = i…
阅读更多...
html | 无js二级菜单

html | 无js二级菜单

1. 效果图 2. 代码 <meta charset"utf-8"><style> .hiddentitle{display:none;}nav ul{list-style-type: none;background-color: #001f3f;overflow:hidden; /* 父标签加这个&#xff0c;防止有浮动子元素时&#xff0c;该标签失去高度*/margin: 0;padd…
阅读更多...
小程序商品如何设置规格

小程序商品如何设置规格

商品规格是指商品在不同属性上的区分&#xff0c;比如颜色、尺寸、款式等。通过设置规格&#xff0c;商家可以更好地展示商品的多样性&#xff0c;并方便用户选择和购买。下面是怎么设置小程序产品规格的方法和步骤。 1. 添加/修改商品的时候&#xff0c;点击规格&#xff0c;会…
阅读更多...
2、简单上手+el挂载点+v-xx(v-text、v-html、v-on、v-show、v-if、v-bind、v-for)

2、简单上手+el挂载点+v-xx(v-text、v-html、v-on、v-show、v-if、v-bind、v-for)

官网&#xff1a; vue3&#xff1a;https://cn.vuejs.org/ vue2&#xff1a;https://v2.cn.vuejs.org/v2/guide/ 简单上手&#xff1a; 流程&#xff1a; 导入开发版本的Vue.js <!--开发环境版本&#xff0c;包含了有帮助的命令行警告--> <script src"https…
阅读更多...
Spring Boot整合ES的两种方式

Spring Boot整合ES的两种方式

使用Spring Data Elasticsearch Starter 在Spring Boot中整合Elasticsearch的方式之一是使用Elasticsearch的官方Spring Data Elasticsearch Starter。该Starter提供了对Elasticsearch的高级集成&#xff0c;简化了配置和管理Elasticsearch客户端。 下面是使用Spring Data E…
阅读更多...
OnlyOffice社区版破解最大连接限制部署

OnlyOffice社区版破解最大连接限制部署

onlyoffice社区版部署并且破解最大连接数 docker镜像 docker pull onlyoffice/documentserver:5.3.1.265.4或更高的版本已经解决了此方法的Bug 运行镜像 docker run -d --name onlyoffice --restartalways -p 暴露端口号:80 onlyoffice/documentserver:5.3.1.26进入容器内部…
阅读更多...
redis初级redis入门redis数据类型redis常用命令redis持久化机制

redis初级redis入门redis数据类型redis常用命令redis持久化机制

Redis 课程内容 Redis入门Redis数据类型Redis常用命令在Java中操作RedisRedis持久化机制 1. Redis入门 1.1 Redis简介 Redis是一个基于内存的key-value结构数据库。Redis 是互联网技术领域使用最为广泛的存储中间件。 **官网&#xff1a;**https://redis.io **中文网&…
阅读更多...
gradle 命令行单元测试执行问题

gradle 命令行单元测试执行问题

文章目录 问题&#xff1a;命令行 执行失败最终解决方案&#xff08;1&#xff09;ADB命令&#xff08;2&#xff09;Java 环境配置 问题&#xff1a;命令行 执行失败 命令行 执行测试命令 无法使用&#xff08;之前还能用的。没有任何改动&#xff0c;又不能用了&#xff09; …
阅读更多...
提速Rust编译器！

提速Rust编译器！

Nethercote是一位研究Rust编译器的软件工程师。最近&#xff0c;他正在探索如何提升Rust编译器的性能&#xff0c;在他的博客文章中介绍了Rust编译器是如何将代码分割成代码生成单元&#xff08;CGU&#xff09;的以及rustc的性能加速。 他解释了不同数量和大小的CGU之间的权衡…
阅读更多...
三种方式创建对象的几种方式及new实例化时做了什么？

三种方式创建对象的几种方式及new实例化时做了什么？

创建对象的几种方式 利用对象字面量创建对象 const obj {}2.利用 new Object创建对象 const obj new Object()3.使用 构造函数实例化对象 function Fn(name) {this.name name} const obj new Fn(张三) console.log(obj.name); //张三为什么要用构造函数的形式&#xff1…
阅读更多...
力扣279.完全平方数（动态规划）

力扣279.完全平方数（动态规划）

class Solution { public:int numSquares(int n) {vector<int> f(n 1);for (int i 1; i < n; i) {int minn INT_MAX;for (int j 1; j * j < i; j) {minn min(minn, f[i - j * j]); //上一次的 & 当前数可以找到一个新的更大的平方}f[i] minn 1; }…
阅读更多...
conda 环境 numpy 安装报错需要 Microsoft Visual C++ 14.0

conda 环境 numpy 安装报错需要 Microsoft Visual C++ 14.0

到公司装深度学校环境。项目较旧&#xff0c;安装依赖&#xff0c;一堆报错&#xff08;基于 conda 环境&#xff09;&#xff1a; numpy 安装报需要 C 14.0 No module named numpy.distutils._msvccompiler in numpy.distutils; trying from distutilserror: Microsoft Visu…
阅读更多...
最新文章

Copyright @ 2022~2023