当前位置: 首页 > news >正文

数据结构--5.1图的存储结构(十字链表、邻接多重表、边集数组)

目录

一、十字链表(Orthogonal List)

二、邻接多重表

三、边集数组

四、深度优先遍历


 

一、十字链表(Orthogonal List)

重新定义顶点表结点结构: 

datafirstInfirstOut

重新定义边表结构结点:

tailVexheadVexheadLinktailLink

       十字链表的好处就是因为把邻接表和逆邻接表整合在了一起,这样既容易找到Vi为尾的弧,也容易找到以Vi为头的弧,因而容易求得顶点的出度和入度。

        十字链表除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字链表也是非常好的数据结构模型。

二、邻接多重表

        我们可以仿照十字链表的方式,对边表结构进行改装,重新定义的边表结构如下:

iVexiLinkjVexjLink

        其中iVex和jVex是与某条边依附的两个顶点在顶点表中的下标。iLink指向依附顶点iVex的下一条边,jLink指向依附顶点jVex的下一条边。

        也就是说在邻接多重表里边,边表存放的是一条边,而不是一个顶点。 

三、边集数组

        边集数组是由两个一维数组构成的,一个是存储顶点的信息,另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin),终点下标(end)和权(weight)组成。

四、深度优先遍历

        深度优先遍历(DepthFirstSearch),也有称为深度优先搜索,简称为DFS。

http://www.lryc.cn/news/148581.html

相关文章:

  • mac上 Kratos 配置 protoc
  • 【c++5道练习题】①
  • 最佳实践:TiDB 业务读变慢分析处理
  • 【ES6】Getter和Setter
  • 3DS Max中绘制圆锥箭头
  • 虚拟机Ubuntu20.04 网络连接器图标开机不显示怎么办
  • 你真的知道什么是USB Server吗?一分钟了解
  • Node.js 中间件是怎样工作的?
  • Spring MVC: 请求参数的获取
  • 别再头疼反弹Shell失败了,这篇文章带你找到问题根源
  • 第五章 树与二叉树 四、线索树(手算与代码实现)
  • 服务器前后端学习理解
  • python-数据分析-numpy、pandas、matplotlib的常用方法
  • ChatGPT⼊门到精通(5):ChatGPT 和Claude区别
  • ChatGPT 总结数据分析的所有知识点
  • hadoop-HDFS
  • 0202hdfs的shell操作-hadoop-大数据学习
  • 生活小记-挂号信
  • 3D点云处理:基于PCA的计算点云位姿(占位待整理)
  • 本地私有仓库、harbor私有仓库部署与管理
  • 尚硅谷SpringMVC (5-8)
  • jupyter notebook中查看python版本的解决方案
  • 动态字符串 String (完整源码)
  • 【深度学习】实验05 构造神经网络示例
  • 用了这么久SpringBoot却还不知道的一个小技巧
  • Websocket、SessionCookie、前端基础知识
  • 【云原生进阶之PaaS中间件】第一章Redis-2.4缓存更新机制
  • Qt——事件处理详解
  • 基于位置管理的企业员工考勤打卡系统设计 微信小程序
  • adb 查找应用包名,应用 Activity 等信息