设为首页
收藏本站
切换到宽版
登录
立即注册
找回密码
搜索
搜索
本版
帖子
用户
快捷导航
论坛
BBS
VIP用户组
官网群
无名商城论坛
»
论坛
›
资源分享区
›
学习资源专区
›
【LSP】数据结构——图—概念和存储(邻接矩阵,邻接表 ...
返回列表
发帖
查看:
234
|
回复:
0
[其他技术]
【LSP】数据结构——图—概念和存储(邻接矩阵,邻接表)
[复制链接]
无名
无名
当前离线
积分
32464
1万
主题
1万
帖子
3万
积分
管理员
积分
32464
发消息
发表于 2022-5-8 17:04:11
|
显示全部楼层
|
阅读模式
图的储存-邻接表
邻接表的基本概念
1.为什么要有邻接表
可以想象如果有一个图他的顶点特别多而边只有一个?那么是不是用邻接矩阵特别浪费内存呢?
所以需要邻接表(不同于邻接表主要以链表形式实现)
2.怎么理解邻接表呢?
首先看上面b图,最边上的表我们给他起名——顶点表;其他的我们给另外的变我们给他起名边表;
3.顶点表
顶点表用来开始储存图中的各个顶点,可以看到我们给顶点表开辟了两个域,第一个域存放了顶点了第二个域呢?
我们可以看出来顶点表的第二个域指向了边表,所以在顶点表的第二个域里面我们存放边表类型让他变成边表的头结点指向边表;
4.边表
上图中边表有两个域一个存放和顶点边中有关系的顶点,另外一个也就是他的NEXT域和链表一样在后面没有时他指向为空,其实还可以给他加第三个域比如权值等等这个很简单了
这样各个就形成了一个邻接表了
邻接表的实现
首先是定义这个结构体类型
/*
下面代码的总体意思就是先定义边表我们给了他3个域分别是顶点域 权值域和next域
在定义顶点表 他有两个域分别是顶点域和代表边表头结点的first_v域
最后我们定义一个顶点表的顺序表类型。类似于图b中最左边的那个顺序表
这样一个邻接表就定义好了
*/
typedef int VertexType;/*顶点类型有用户定义*/
typedef struct EdgeNode//定义边表
{
int adjvex;//邻接点域 里面放各个和顶点表对应节点有关的顶点
int weight;//权值
struct EdgeNode *next;
}EdgeNode;
typedef struct VertexNode /*定义顶点表*/
{
VertexType data;//顶点域,存储顶点信息
EdgeNode *first_v;//边表的头指针
}VertexNode;
typedef struct //邻接表
{
VertexNode adjlist[M]; //用于存放头结点和顶点的顺序表;
int n_v,n_e;
}LinkdeGraph;
创建邻接表
/*
下面代码的主要含义是
1.先获取到图中的顶点数和边数,然后以顶点数为最大创建顶点表数组并且初始化
2.然后定义一个边表类型,输入某个边上的两个顶点,并且用头插发插入
边的表示(vi vj)表示连接vi vj的边
3.函数解释
大概意思就是接收到边上的两个顶点后,把和i有边的j节点用头插发插在顶点表中有i顶点那一段之后;
顶点
,
邻接
,
定义
,
一个
,
我们
相关帖子
•
【LUR】入侵国外摄像头教程
•
【LUR】帅气炫迈在线教你如何搭建蔡徐坤打篮球网站
•
【LUR】添加网站本地背景音乐各种播放模式
•
【LUR】非常实用!使用BootStrap实现布局~
•
【解忧】深入理解Java反射
•
【解忧】最全的JAVA知识汇总(附讲解和思维导图)
•
【DMT】教你们修改器如何播放音乐教程
•
SMTP邮件群发软件,支持163邮箱,谷歌邮箱,126邮箱等等...,QQ邮箱,
回复
使用道具
举报
返回列表
发帖
高级模式
B
Color
Image
Link
Quote
Code
Smilies
您需要登录后才可以回帖
登录
|
立即注册
本版积分规则
发表回复
回帖后跳转到最后一页
快速回复
返回顶部
返回列表