数据结构--5.0.1图的存储结构

这篇具有很好参考价值的文章主要介绍了数据结构--5.0.1图的存储结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、邻接矩阵(无向图)

 二、邻接矩阵(有向图)

三、邻接矩阵(网)

四、邻接表(无向图)

五、邻接表(有向图)


 

——图的存储结构相比较线性表与树来说就复杂很多

——对于线性表来说,是一对一的关系,所以用数组或者链表均可简单存放。

        树结构是一对多的关系,所以我们要将数组和链表的特性结合在一起才能更好的存放。

——我们的图,是多对多的情况,另外图上的任何一个顶点都可以被看作第一个顶点,任一顶点的邻接点之间不存在次序关系。

——因为任意两个顶点之间都可能存在联系,因此无法以数据元素在内存中的物理位置来表示元素之间的关系(内存物理位置是线性的,图的元素关系是平面的)

一、邻接矩阵(无向图)

        考虑到图是由顶点和边或弧两部分组成,合在一起比较困难,那就是很自然地考虑到分为两个结构来分别存储。

        顶点因为不区分大小、主次,所以用一个一维数组来存储是很不错地选择。

        而边或弧由于是顶点与顶点之间的关系,一维数组肯定就搞不定了,那我们不妨考虑用一个二维数组来存储。

1、图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图的边或弧的信息。

        我们可以设置两个数组,顶点数组为vertex[4] = {V0,V1,V2,V3},边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)。

 二、邻接矩阵(有向图)

数据结构--5.0.1图的存储结构,数据结构

        可见顶点数组vertex[4]= {V0,V1,V2,V3},弧数组arc[4][4]也是一个矩阵,但因为是有向图,所以这个矩阵并不对称,例如由V1到V0有弧,得到arc[1][0] = 1,而V0到V1没有弧,因此arc[0][1]=0。

        另外有向图也是有讲究的,要考虑入度和出度,顶点V1的入度(横为出,竖为入)为1,正好是第V1列的个数之和,顶点V1的出度为2 ,正好是第V2行的个数之和。

三、邻接矩阵(网)

        在图的术语中,我们提到了网这个概念,事实上也就是每条边上带有权的图就叫网。 

数据结构--5.0.1图的存储结构,数据结构 这里  “∞”   表示一个计算机允许的,大于所有边上权值的值。

四、邻接表(无向图)

        把数组与链表结合一起来存储,这种方式在图结构也适用,我们称为邻接表(AdjacencyList)。

邻接表的处理方法是:

1、图中顶点用一个一维数组存储,当然顶点也可以用单链表来存储,不过数组可以较为容易的读取顶点信息,更加方便。 

2、图中每个顶点Vi的所有邻接点构成一个线性表,由于邻接点的个数不确定,所以我们选择用单链表来存储。

五、邻接表(有向图)

       邻接表结构类似无向图的。文章来源地址https://www.toymoban.com/news/detail-690819.html

到了这里,关于数据结构--5.0.1图的存储结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构(28)】6.4 图的存储结构

    由于图的结构比较复杂,任意连个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即 图没有顺序存储结构 ,但是可以借助二维数组来表示元素之间的关系,即 邻接矩阵表示法 。 另一方面,由于图的任意两个顶点减都可能存在

    2024年02月03日
    浏览(42)
  • 24考研数据结构-图的存储结构邻接矩阵

    【1】顶点的结点结构 ——————— | data | firstarc | ——————— data数据域:储存顶点vi firstarc链域:指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | —————————— adjvex邻接点域:与顶点vi邻接的点在图中的位置 info数据域

    2024年02月14日
    浏览(54)
  • 数据结构——图的基本定义以及图的存储结构,邻接矩阵,邻接表

    目录 图的定义和术语 图的存储结构 顺序存储结构—邻接矩阵 链式存储结构 邻接表 邻接多重表 十字链表 图的遍历 图的连通性问题 有向无环图及其应用 最短路径 图的定义:图是一种非线性的复杂的数据结构,图中的数据元素的关系是多对多的关系 ,在图中我们常常把数

    2024年02月04日
    浏览(55)
  • 【数据结构】图的存储与遍历

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E) 在有向图中,顶点对x, y是有序的,顶点对x,y称为顶点x到顶点y的一条边(弧),x, y和y, x是两条不同的边。 在无向图中,顶点对(x, y)是无序的,顶点对(x,y)称为顶点x和顶点y相关联的一条边,这条边没有特定方向,

    2024年02月22日
    浏览(45)
  • 【数据结构】图的定义,存储,遍历

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【Dream It Possible】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录 🍔前言 🎁图的定义   🏳️‍🌈有向完全图 🏳️‍🌈无向完全图 🎁存储结构 🏳️‍🌈邻接矩阵  🎈代码

    2024年02月06日
    浏览(77)
  • 数据结构--图的存储邻接表法

    邻接矩阵: 数组实现的顺序存储,空间复杂度高,不适合存储稀疏图 邻接表: 顺序+链式存储 无向图: 边结点的数量是 2|E|, 整体空间复杂度为 O(|V| + 2|E|) 有向图: 边结点的数量是 |E|, 整体空间复杂度为 O(|V| + |E|) 图的邻接表表示方式并不唯一 color{red}图的邻接表表示方

    2024年02月16日
    浏览(44)
  • 数据结构--5.1图的存储结构(十字链表、邻接多重表、边集数组)

    目录 一、十字链表(Orthogonal List) 二、邻接多重表 三、边集数组 四、深度优先遍历   重新定义顶点表结点结构:  data firstIn firstOut 重新定义边表结构结点: tailVex headVex headLink tailLink        十字链表的好处就是因为把邻接表和逆邻接表整合在了一起,这样既容易找到Vi为

    2024年02月10日
    浏览(42)
  • C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

    关键点: 1.构建二维数组 2.对应边的位置赋值为1 由于比较简单就直接上代码: 个人对邻接表实现无向图的理解如下,仅供参考:         由于无向图的组成是由多个顶点和多条无向边组成的,因此我们可以把它拆分成两个结构,分别是顶点和无向边,又由于我们是使用

    2024年02月05日
    浏览(51)
  • 数据结构实验6 :图的存储与遍历(邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS)

    利用邻接矩阵存储无向图,并从0号顶点开始进行深度优先遍历。 输入第一行是两个整数n1 n2,其中n1表示顶点数(则顶点编号为0至n1-1),n2表示图中的边数。 之后有n2行输入,每行输入表示一条边,格式是“顶点1 顶点2”,把边插入图中。 例如: 4 4 0 1 1 3 0 3 0 2 先输出存储

    2024年02月09日
    浏览(65)
  • 数据结构 | 图的遍历

    使用邻接矩阵法存储图的信息,其中 一维矩阵 Vexs[] 存储节点信息 二维矩阵 Edges[][] 存储边的信息 一维矩阵 visited[] 记录当前节点是否被访问过,用于后面的遍历 本文所使用的图的结构如下: 对应的 Vexs[] 为:A,B,C,D,E,F(对应的数组下标从0到5) 对应的 Edges[][] 如下: 图的

    2024年02月04日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包