数据结构—图的存储结构

news/2024/12/28 17:50:24/

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>的权值置为wG.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;//生成一个新的边结点*p1p1->adjvex=j;//邻接点序号为jpi->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


http://www.ppmy.cn/news/1007641.html

相关文章

Python查找子字符串A在字符串B出现的位置

Python查找子字符串A在字符串B出现的位置

目录 前言 find&#xff08;&#xff09;函数 index&#xff08;&#xff09; 总结 前言 在Python中&#xff0c;查找字符串A在字符串B出现的位置&#xff0c;常用find&#xff08;&#xff09;与inde&#xff08;&#xff09;函数。 find&#xff08;&#xff09;函数 …
阅读更多...
【数据结构刷题】数组oj

【数据结构刷题】数组oj

前言:本文章是关于在力扣上面的数组相关面试题的讲解&#xff0c;包括:1.原地移除数组中所有的元素val&#xff0c;要求时间复杂度为O(N)&#xff0c;空间复杂度为O(1),2.删除排序数组中的重复项。3. 合并两个有序数组。一.原地移除数组中所有的元素val 题目: https://leetcod…
阅读更多...
配置Linux的goland环境

配置Linux的goland环境

下载go版本All releases - The Go Programming Language (google.cn) 我这里下的是https://golang.google.cn/dl/go1.20.7.linux-amd64.tar.gz 命令行进入root权限 su 进入压缩包所在文件路径后 cd /.../ 删除旧版如果有的话&#xff0c;没有也没有关系也可以删&#xff0…
阅读更多...
高级web前端开发工程师岗位的具体内容概述（合集）

高级web前端开发工程师岗位的具体内容概述（合集）

高级web前端开发工程师岗位的具体内容概述1 职责&#xff1a; 1、负责前端页面开发和维护&#xff0c;并根据需求优化产品性能、用户体验、交互效果及各种主流浏览器以及各类型移动客户端的兼容适配工作; 2、配合产品经理和UI设计师&#xff0c;通过各种前端技术手段&#xf…
阅读更多...
运输层---UDP协议

运输层---UDP协议

目录 一. 无连接运输&#xff1a;UDP1.1 定义1.2 特点1.3 应用 二. UDP报文段结构三. UDP检验和3.1 定义3.2 检验和计算实例3.2 UDP检验和的局限 一. 无连接运输&#xff1a;UDP 1.1 定义 UDP&#xff08;User Datagram Protocol&#xff09;用户数据报协议&#xff1a;由 [RF…
阅读更多...
时间复杂度、空间复杂度实践练习（力扣OJ）

时间复杂度、空间复杂度实践练习（力扣OJ）

目录 文章目录 前言 题目一&#xff1a;轮转数组 思路一&#xff1a; 思路二&#xff1a; 思路三&#xff1a; 题目二&#xff1a;消失的数字 思路一&#xff1a; 思路二&#xff1a; 思路三&#xff1a; 题目三&#xff1a;移除元素 思路&#xff1a; 总结 前言 想要编写高效的…
阅读更多...
Spring源码分析

Spring源码分析

一、基本注解 1.注解总览 2.重点注解描述 ① Bean、Import 初学时&#xff0c;一般使用xml配置文件将Bean注册到Spring容器当中&#xff0c;在实际开发中&#xff0c;使用注解将Bean注册到Spring容器当中也是很常见的。 使用xml方式将bean注册到spring容器当中 获取bean信息…
阅读更多...
java中javamail发送带附件的邮件实现方法

java中javamail发送带附件的邮件实现方法

java中javamail发送带附件的邮件实现方法 本文实例讲述了java中javamail发送带附件的邮件实现方法。分享给大家供大家参考。具体分析如下&#xff1a; JavaMail&#xff0c;顾名思义&#xff0c;提供给开发者处理电子邮件相关的编程接口。它是Sun发布的用来处理email的API。它…
阅读更多...
最新文章

Copyright @ 2022~2023