精华内容
下载资源
问答
  • 十字链表和邻接多重表,暂存。
    展开全文
  • 除此之外还有链式存储结构,包括邻接十字链表和邻接多重表。其中邻接矩阵邻接最常用。 十字链 十字链表(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.

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

    datafirstinfirstout

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

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

    tailvexheadvexheadlinktaillink

    其中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)这条边,需要对邻接表结构中右边表的两个结点进行删除,显然这是比较繁琐的。

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

    ivexilinkjvexjlink

    其中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)组成。

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

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

    展开全文
  • 使用邻接表存储图时,对于图中的每一个顶点它相关的邻接点,都存储到一个链表中。每个链表都配有头结点,头结点的数据域不为NULL,而是用于存储顶点本身的数据;后续链表中的各个结点存储的是当前顶点的所有邻接点...
  • 十字-用于有向图】 定点结点: data:数据内容 firstin:以该顶点为尾的第一个弧结点(A→B) firstout:以该顶点为头的第一个弧结点(A→B) 实际上对于选边没有一个特定的规则,所以firstin/out的结点...
  • 邻接矩阵:可以存储无向图,也可存储有向图。构造一个具有n个顶点e条边的无向图的时间复杂度O(n*n+e*n),其中对灵接矩阵的初始化消耗了O(n*n)的时间。   邻接表:图的一种链式...但是邻接表要确定ViVj...
  • 一、图的存储 (一)邻接矩阵(数组实现的顺序存储,空间复杂度高,不适合存储稀疏图) ... //邻接矩阵,边;可以用bool型或枚举型变量表示边。 int vexnum,arcnum; //图的当前顶点数和边数/弧数 }MGraph;
  • 十字主要用于存储有向图,临界多重表主要用于存储无向图,首先复习临界画法: 十字 结构 根据有向图画十字 **画图策略:**先从各个顶点结点画第二个指针,因为第二个指针为尾指针,尾指针...
  • 近期一直在构建算法技能树的数据,借此机会,重新把数据结构与算法又温习了一遍,在看到十字链表邻接多重表的画法时,十分的不理解,在C站找资料时,发现也看不懂,于是上B站,终于明白了十字链表与多重邻接的...
  • 二、邻接多重表存储无向图 小结: 下一篇: 一、十字存储 注:A->B ,其中B是弧头,A是弧尾 例子: 即:顶点结点中绿色色块代表由某条弧指向另一个顶点 橙色色块代表被某个顶点指向 弧结点中...
  • 文章目录十字基本概述开设弧结点开设顶点结点绘制过程首先只画,出边对应的邻接画出对应边的逆表现邻接多重表基本概念 十字 基本概述 思路:将邻接矩阵用链表存储,是邻接、逆邻接的结合 优点: ...
  • 十字链表中,对应于有向图中的每条弧有一个结点,对应于每个顶点也有一个结点。 弧结点中有5个域:尾域(tailvex)头域(headvex)分别指示弧尾弧头这两个顶点在图中的位置:链域hlink指向弧头相同的下一条弧;链...
  • 邻接多重表,是在邻接的基础上改进的,因为十字是适合有向图的,所以需要一个数据结构适合无向图,也就是邻接多重表。 我们发现,在无向图邻接中,边节点存在冗余,也就是说,我们在无向图的邻接中能找到...
  • 图的存储结构,对于邻接表在无向图有向图的存储结构的优化
  • 十字链表邻接表和邻接表的组合,是对有向图的优化存储结构,容易求得顶点的出度入度。除了结构复杂外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字链也是非常好的数据结构...
  • 邻接表与逆邻接表结合起来,即有向图的一种存储方法十字链表(Orthogonal List)。 我们重新定义顶点结构 firstin表示入边表头指针,指向该顶点的入边中第一个结点; firstout表示出边表头指针,指向该...
  • 上篇博客讲到,图状结构是非常复杂的结构,图也是非常复杂的,所以图的存储就是一个非常重要的部分,因为我们不仅要表示顶点集...邻接矩阵又分为有向图邻接矩阵无向图邻接矩阵。 设G=(V,E)是一个图,其中V={v1,v2...
  • 最近复习考研遇到了图的问题,发现自己对这一块的数据结构不怎么熟悉,... 图一共有四个基本存储结构,分别是邻接矩阵,邻接十字邻接多重表。它们各有各自的特点,我将这四个存储结构全部实现了一遍,并针...
  • 1、 掌握图的结构特征以及四种存储结构(数组表示法、邻接十字链表和邻接多重表)的特点程序设计方法。 2、 掌握在邻接矩阵或邻接存储结构下图的深度优先广度优先遍历算法的设计方法。 3、 进一步掌握递归...
  • 邻接矩阵法 结点数为n的图G = (V,E)的邻接矩阵A是n×n的。 将G的顶点编号为v1,v2,,…,Vn,(数组下标) 若<vi,vj>∈E,则A[i][j]=1,否则A[i][j]=O。 无向图 #define MaxvertexNum 100 typedef char ...
  • 上一节介绍了如何使用顺序存储...使用链式存储结构表示图的常用方法有 3 种:邻接邻接多重表和十字。 邻接的意思是顶点之间有边或者弧存在,通过当前顶点,可以直接找到下一个顶点。 邻接 使用邻接存...
  • 用一维数组存储顶点信息,用二维数组表示邻接关系 一个无向图: 一个带权图: 邻接矩阵存储特点: 1)无向图的邻接矩阵是对称阵。 对于无向图,i行(i列)非零元素个数=第i个顶点的度TD 对于有向图,i行(i列)非...
  •  你会发现,要表示一个有向图,因为有 出度 入度 ,需要两个邻接表邻接表和邻接表。  其实我们可以把这两个整合在一起,也就是十字(Orthogonal List)。  我们依然需要构造一种结构体A,用结构体...
  • 文章目录一:邻接矩阵——适合存储稠密图(1)邻接矩阵定义(2)代码二:邻接表 一:邻接矩阵——适合存储稠密图 (1)邻接矩阵定义 图的邻接矩阵(Adjacency Matrix):采用两个数组表示图。一个一维数组存储图中顶点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,730
精华内容 692
关键字:

十字链表和邻接多重表