精华内容
下载资源
问答
  • 十字链表和邻接多重表,暂存。
    展开全文
  • 除此之外还有链式存储结构,包括邻接表、十字链表和邻接多重表。其中邻接矩阵和邻接表最常用。 十字链表 十字链表(Orthogonal List)是有向图的另一种链式存储结构,可以看作是有向图的...

    图的存储结构

    由于图的任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即图没有顺序存储结构,但我们可以用二维数组(矩阵)来表示元素之间的关系——邻接矩阵。除此之外还有链式存储结构,包括邻接表、十字链表和邻接多重表其中邻接矩阵和邻接表最常用。


     

    十字链表

    十字链表(Orthogonal List)是有向图的另一种链式存储结构,可以看作是有向图的邻接表(单链表的结点数-1为出度)逆邻接表(单链表的结点数-1为入度)结合起来的一种链表。

    在十字链表中容易找到以vi(vi∈G(V))为弧尾或弧头的弧,因而更容易求顶点的入度和出度。


     

    邻接多重表

    邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构。

    对无向图而言,邻接表的缺点:每一条边(va,vb)有两个结点,分别在第a和第b个单链表中,这可能会给边的搜索、删除等操作带来了不便。

    邻接多重表与邻接表的区别仅在于,同一条边,在邻接表中要用两个结点表示,而在邻接多重表中只需要一个结点

    此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。

     

    (点击传送门学习更多相关知识:https://blog.csdn.net/Ha1f_Awake/article/details/84383923

    展开全文
  • 在邻接表表示法中,对于有向图,...而邻接多重表就是为了克服这个缺点,即出现两次的边只存一次。 十字链表——有向图的一种存储结构 含义: 十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表...

    在邻接表表示法中,对于有向图,它的缺点就是求结点的度困难,因为有向图的邻接表很难求结点的入度,而逆邻接表很难求出度,所以可以把邻接表和逆邻接表结合起来——十字链表

    在邻接表表示法中,对于无向图,它的缺点是每条边都要存储两次。而邻接多重表就是为了克服这个缺点,即出现两次的边只存一次。



    十字链表——有向图的一种存储结构

    • 含义: 十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。
      有向图中的每一条弧对应十字链表中的一个弧结点,同时有向图中每个顶点在十字链表中对应一个结点,叫顶点结点

    • 具体操作

      • 顶点结点结构
        在这里插入图片描述
        在原来的基础上增设一个指针域,firstin表示第一条入弧,firstout表示第一条出弧。
      • 弧结点结构
        在这里插入图片描述
        tailvex表示弧尾位置,headvex表示弧头位置,hlink表示弧头相同的下一条弧,tlink表示弧尾相同的下一条弧。
    • 例子: 把下图结构改成十字链表
      在这里插入图片描述
      1.对结点a的操作如下,
      在这里插入图片描述
      2.十字链表如下,
      在这里插入图片描述



    邻接多重表——无向图的一种存储结构

    • 具体结构:

      • 顶点结点
        在这里插入图片描述
      • 边结点
        在这里插入图片描述
    • 例子:
      在这里插入图片描述

    展开全文
  • 图的存储结构-十字链表和邻接多重表

    万次阅读 多人点赞 2016-12-12 17:31:20
    有没有可能把邻接表和邻接表结合起来呢? 答案是肯定的,就是把它们整合在一起。这种存储有向图的方法是:十字(Orthogonal List). 我们重新定义顶点结点结构为: data firstin firstout

    1、十字链表

    对于有向图来说,邻接表是有缺陷的。关心了出度问题,想了解入度就必须要遍历整个图才能知道。反之,逆邻接表解决了入度

    却不了解出度的情况。有没有可能把邻接表和逆邻接表结合起来呢?

    答案是肯定的,就是把它们整合在一起。这种存储有向图的方法是:十字链表(Orthogonal List.

    我们重新定义顶点表结点结构为:

    data firstin firstout

    其中firstin表示入边表头指针,指向该顶点的入边表中第一个结点,firstout表示出边表头指针,指向该顶点的出边表中的第一个结点。

    重新定义的边表结点结构如下表:

    tailvex headvex headlink taillink

    其中tailvex是指弧起点在顶点表的下标,headvex是指弧终点在顶点表中的下标,headlink是指入边表指针域,指向终点(弧头)相同的

    下一条边,taillink是指出边表指针域,指向起点(弧尾)相同的下一条边。如果是网,还可以再增加一个weight域来存储权值。

    如下图表示的十字链表:

    顶点表依然是存入一个一维数组{v0,v1,v2,v3},以顶点v0来说,firstout指向的是出边表中的第一个结点v3。所以v0边表结点的headvex=3,

    而tailvex其实就是当前顶点v0的下标0,由于v0只有一个出边顶点,所以headlink和taillink都是空。

    这里虚线箭头的含义,其实就是逆邻接表的表示。对于v0来说,它有两条入边,分别来自顶点v1和v2。因此v0的firstin指向顶点v1的边表

    结点中headvex为0的结点,虚线(1),接着由入边结点的headlink指向下一个入边顶点v2,虚线(2)。

    对于顶点v1,它有一个入边顶点v2,2个出边顶点v0和v2,所以它的firstin指向顶点v2的边表结点中headvex为1的结点,虚线(3).

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

    顶点的出度和入度。除了结构复杂一点外,其实创建图算法的时间复杂度和邻接表是相同的,因此很好的应用在有向图中。

    2、邻接多重表

    十字链表主要是针对有向图的存储结构进行了优化,那么对于无向图的邻接表,有没有问题呢?如果我们在无向图的应用中,关注的重点是顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作。如下图,若要删除(v0,v2)这条边,需要对邻接表结构中右边表的两个结点进行删除,显然这是比较繁琐的。

    因此,我们也仿照十字链表的方式,对边表结点的结构进行一些改造,重新定义的边表结点结构如下表:

    ivex ilink jvex jlink

    其中ivex和jvex是指某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边,jlink指向依附顶点jvex的下一条边。

    这就是邻接多重表结构。如上图有4个顶点和5条边,先将边表结点画出来。由于是无向图,所以ivex,jvex正反过来都可以,为了绘图

    方便,都将ivex值设置的与一旁的顶点下标相同。

    下面开始连线,首先连线的(1)(2)(3)(4)是将顶点的firstedge指向一条边,顶点下标要与ivex的值相同。接着,由于顶点v0的(v0,v1)边的

    邻边有(v0,v3)和(v0,v2)。因此(5)(6)的连线就是满足指向下一条依附于顶点v0的边的目标,注意ilink指向的结点的jvex(ivex)一定要与它本身

    的ivex的值相同。同理,连线(7)就是指(v1,v0)这条边,它是相当于顶点v1指向(v1,v2)边后的下一条。v2有三条边依附,所以(3)之后就有

    了(8)(9)。连线(10)就是顶点v3在连线(4)之后的下一条边。左图一共有5条边,所以右图有10条连线,完全符合预期。

    邻接多重表与邻接表的差别,仅仅是在于同一条边在邻接表中用两个边表结点表示,而在邻接多重表中只有一个结点。这样对边的操作就方便

    多了,若要删除左图的(v0,v2)这条边,只需要将右图的(6)(9)的链接指向改为^即可。

     3、边集数组

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

    终点下标(end)和权(weight)组成。

    如上图所示,边集数组关注的是边的集合,在边集数组中要查找一个顶点的度需要扫描整个边数组,效率并不高。因此它更适合对边依次

    进行处理的操作,而不适合对顶点相关的操作。

    展开全文
  • 邻接表与逆邻接表结合起来,即有向图的一种存储方法十字链表(Orthogonal List)。 我们重新定义顶点结构 firstin表示入边表头指针,指向该顶点的入边中第一个结点; firstout表示出边表头指针,指向该...
  • 邻接矩阵:可以存储无向图,也可存储有向图。构造一个具有n个顶点e条边的无向图的时间复杂度O(n*n+e*n),其中对灵接矩阵的初始化消耗了O(n*n)的时间。   邻接表:图的一种链式...但是邻接表要确定ViVj...
  • 图的存储结构,对于邻接表在无向图有向图的存储结构的优化
  • 十字-用于有向图】 定点结点: data:数据内容 firstin:以该顶点为尾的第一个弧结点(A→B) firstout:以该顶点为头的第一个弧结点(A→B) 实际上对于选边没有一个特定的规则,所以firstin/out的结点...
  • 使用邻接表存储图时,对于图中的每一个顶点它相关的邻接点,都存储到一个链表中。每个链表都配有头结点,头结点的数据域不为NULL,而是用于存储顶点本身的数据;后续链表中的各个结点存储的是当前顶点的所有邻接点...
  • 上一节介绍了如何使用顺序存储...使用链式存储结构表示图的常用方法有 3 种:邻接表、邻接多重表和十字链表。 邻接的意思是顶点之间有边或者弧存在,通过当前顶点,可以直接找到下一个顶点。 邻接表 使用邻接表存...
  • 今天介绍十字链表和邻接多重表还有边集数组。 首先我们回想一下邻接表,对于有向图的邻接表,由于对于顶点出度的入度分别储存在邻接表和逆邻接表中,对于频繁访问出度的入度的算法很不方便,于是前辈们将邻接表和逆...
  • 具体实现十字链表和邻接多重表的代码 0x01.十字链表 由来: 邻接表只适合对某个顶点的出度相关信息进行判断,逆邻接表只适合对入度的相关信息进行判断,当同时需要判断的时候,就需要引入一种新的结构:十字链表...
  • 邻接多重表用于存放无向图,每个结点有两个指针两个标示位 特点:每一份数据是唯一的,删除的话直接删除即可,解决了邻接表删除不方便的问题 邻接矩阵:问题:冗余 邻接表法:问题①入度不方便查找:十字链表法;...
  • 由于邻接矩阵这种存储结构存在一定空间浪费,因此考虑用邻接表 邻接表 这是一种数组与链表结合一起来存储。...十字链表邻接表和邻接表整合在一起。 十字链表虽然结构复杂,但其创建图的时间复杂度...
  • 除了结构复杂外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字也是非常好的数据结构模型,如果我们在遍历中只关心出度则选择邻接,反之选择逆邻接。 边结点结构特点:...
  • 邻接表固然优秀,但也有不足,例如对有向图的处理中,有时候需要再建立一...十字链表的好处就是因为把邻接表和邻接表整合在一起,这样容易找到以Vi为尾的弧, 也容易找到以Vi为头的弧,因而容易求得顶点的出度 ...
  • 图存储之邻接多重表

    2020-10-17 15:28:20
    邻接多重表十字链表类似,在邻接多重表中,每条边用一个结点表示,结构如下: 其中,mark为标志域,可用以标记该条边是否被搜索过;ivexjvex为该边依附的两个顶点在图中的位置;ilink指向下一条依附于顶点...
  • 行和是出度,列和是入度网:用一个不可能的值表示不存在的边的权代码邻接表:最常使用的图存储结构,把数组链表结合使用有向图的逆邻接表带权邻接表:给边结点增加一个存储权值的数据域代码十字链表,正交链表:...
  • 十字链表数组元素的结构是:数据、第一条入边引用、第一条出边引用。 十字链表链的元素结构是:边的起点、边的终点、下一条出边引用、下一条入边引用 而 多重邻接表数组元素结构是:数据、包含 当前索引对应...
  • 邻接多重表的边结点顶点结点如下图: 由以上结构组成的无向图如下: 建议以单个顶点来分析邻接多重表的结构 红线:单独以V1顶点连接出的红线来看,红线链表代表以第一条边为参考,所有连接着顶点V1的边 绿线:...
  • 前面讲过,无向图的存储可以使用邻接表,但在实际使用时,如果想对图中某顶点进行实操(修改或删除...邻接多重表存储无向图的方式,可看作是邻接表和十字链表的结合。同邻接表十字链表存储图的方法相同,都是独自...
  • 两种存储结构的转换(5分),如果其中一种存储结构为十字链表邻接多重表则增加5分。 输出图的深度优先遍历序列或广度优先遍历序列(5分) 求图的深度优先或广度优先的生成树(或生成森林)(存储结构为孩子-兄弟...
  • 数据结构 多重邻接表

    2020-09-24 00:00:03
    前言 有向图的表示结构有多种,由于其有向性,结构中要人...和十字类似,多重邻接表是无向图的一种链式存储结构,区别的是多重邻接表: 对于结点的设置不再把出边入边分成两张链表,而是一张链表表示邻边; 对于
  • 除此之外还有链式存储结构,包括邻接表、十字链表和邻接多重表。其中邻接矩阵和邻接表最常用。 邻接表 邻接表(Adjacency List)是图的一种链式结构。图中有多少个顶点,就有多少个单链表...
  • 通常,图更多的是采用链表存储,具体的存储方法有 3 种,分别是邻接表、邻接多重表和十字链表。本节先讲解图的邻接表存储法。邻接表既适用于存储无向图,也适用于存储有向图。在具体讲解邻接表存储图的实现方法之前...
  • 昨天给大家讲了图的存储结构,一共有四种,邻接表,邻接矩阵,十字链表以及邻接多重表,每个表都有自己的特色以及用途。 今天要给大家分享的是将一个用邻接表表示的图转为邻接矩阵表示,我们知道,邻接矩阵中,存储...
  • 图的链式存储有多种,有邻接表、十字链表和邻接多重表,下面注意说明邻接表。 邻接表: 邻接表由两部分组 成:表头结点表和边表。 例: 深度优先遍历: 为了避免同一顶点被访问多次,在遍历图的过程中,必须记下每...
  • 数据结构实验7 建立邻接表

    千次阅读 2017-11-24 11:02:36
    图的存储结构主要有图的数组(邻接矩阵)表示法、图的邻接表表示法、有向图的十字链表和无向图的邻接多重表。其中图的数组(邻接矩阵)表示法和图的邻接表表示法都适用于有向图和无向图。本次实验完成图的邻接表和图...
  • 数据结构--图的存储方式

    千次阅读 2015-03-30 11:35:22
    主要写一下图的几种表示方法。 今天写的几种图存储结构...我在网上查了一些资料和看了课本上的十字链表和邻接多重表的例子,个人觉得讲的不那么通俗,尤其是课本... 目录:  0.预备知识  1.邻接矩阵  

空空如也

空空如也

1 2 3 4 5 6
收藏数 103
精华内容 41
关键字:

十字链表和邻接多重表