Ⅰ 十字链表是什么
十字链表是有向图的另一种链式存储结构，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。
十字链表在这种结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将弧结点分别组织到以弧尾结点为头结点和以弧头结点为头结点的链表中。由此可见，图中的每条弧存在于两个链表中，一个是弧头相同的链表，一个是弧尾相同的链表，两个链表在该弧处交叉形成“十”字，因此称作十字链表。十字链表的结点结构如图7－14所示。顶点结点由2个域组成，其中data域存储和顶点相关的信息，如顶点的名称等；firstin和firstout为两个指针域，分别指向以该顶点为弧头和弧尾的第一个弧结点。弧结点有5个域，其中尾域tailve*和头域headve*分别指向弧尾和弧头这两个顶点在图中的位置，指针域hlink指向弧头相同的下一条弧，而指针域tlink指向弧尾相同的下一条弧，Info域指向该弧的相关信息。
十字链表的结点结构
Ⅱ 图的基本概念，图的存储--邻接矩阵、邻接表、十字链表、邻接多重表
一个图(G)定义为一个偶对(V,E)，记为G=(V,E)。
V是顶点(Vertex)的非空有限集合，记为V(G)。
E是无序集V&V的一个子集，记为E(G)，其元素是图的弧(Arc)。
将顶点集合为空的图称为空图。
弧：表示两个顶点v和w之间存在一个关系，用顶点偶对<v,w>表示。
(1)无向图:
在一个图中，如果任意两个顶点构成的偶对(v,w)∈E 是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。
(2)有向图:
在一个图中，如果任意两个顶点构成的偶对(v,w)∈E 是有序的，即顶点之间的连线是有方向的，则称该图为有向图。一般记作<v,w>
(3)完全无向图:
在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为完全无向图。在一个含有 n 个顶点的完全无向图中，有n(n-1)/2条边。
(4)完全有向图:
在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为完全有向图。在一个含有 n 个顶点的完全有向图中，有n(n-1)条边。
(5)稠密图、稀疏图:
若一个图接近完全图，称为稠密图;称边数很少( )的图为稀疏图。
(6)顶点的度、入度、出度:
顶点的度(degree)是指依附于某顶点 的边数，通常记为TD( )。
在无向图中，所有顶点度的和是图中边的2倍。
在有向图中，要区别顶点的入度(Indegree)与出度(Outdegree)的概念。
顶点 的入度是指以顶点为终点的弧的数目，记为ID ( );
顶点 出度是指以顶点 为始点的弧的数目，记为 OD( )。
顶点 的出度与入度之和称为 的度，记为TD( )。即TD( )=OD( )+ID ( )。
(7)边的权、网图:
与边有关的数据信息称为权(weight)。在实际应用中，权值可以有某种含义。
边上带权的图称为网图或网络(network)。如果边是有方向的带权图，则就是一个有向网图。
(8)路径、路径长度:
对无向图，若从顶点 经过若干条边能到达 ，则称顶点 和 是连通的，又称顶点 到 有路径。
对有向图，从顶点 到 有有向路径，指的是从顶点 经过若干条有向边能到达 。
路径上边或有向边(弧)的数目称为路径长度。
(9)简单路径、回路、简单回路:
在一条路径中，若没有重复相同的顶点，该路径称为简单路径。
第一个顶点和最后一个顶点相同的路径称为回路(环)。
除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。
(10)子图和生成子图:
对于图 G=(V，E)，G’=(V’，E’)，若存在 V’是 V 的子集 ，E’是 E的子集，则称图 G’是 G 的一个子图；
若V’=V且E’是E的子集，则称图G’是G的一个生成子图。
(11)连通图、连通分量:
对无向图G=(V,E)，若任意 都是连通的，则称该图是连通图，否则称为非连通图。
若G是非连通图，则极大连通子图称为连通分量。
极大的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。
任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
(12)强连通图、强连通分量:
对于有向图来说，若图中任意一对顶点 均有从一个顶点 到另一个顶点 有路径，也有从 到 的路径，则称该有向图是强连通图。
有向图的极大强连通子图称为强连通分量。
强连通图只有一个强连通分量，即本身。非强连通图有多个强连通分量。
(13)生成树:
一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。
(14)生成森林:
有向树是只有一个顶点的入度为0，其余顶点的入度均为1的有向图。
有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。
(1)邻接矩阵法(Adjacency Matrix)
基本思想：对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。
在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。
1)无向图的数组表示
①无向无权图的邻接矩阵
无向无权图其邻接矩阵是n阶对称方阵。
若两条边相连,A[i][j]=1; 若不相连A[i][j]=0。
②无向带权图的邻接矩阵
若两条边相连， ，W为权值。
若两条边不相连，A[i][j]=
③无向图邻接矩阵的特性
无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放 上(或下)三角矩阵的元素即可。
对于顶点 ，其度数是第i行的非0元素(或非 元素)的个数。
无向图的边数是上（或下）三角形矩阵的非0元素(或非 元素)的个数。
2)有向图的数组表示
①有向无权图的邻接矩阵
若有向无权图G=(V,E)有n个顶点，则其邻接矩阵是n阶方阵：
若从 到 有弧，A[i][j]=1；
若从 到 没有弧，A[i][j]=0；
②有向带权图的邻接矩阵
③有向图邻接矩阵的特性
对于顶点 ，第i行的非0元素(或非 元素)的个数是其出度OD( )；
第i列的非0元素(或非 元素)的个数是其入度ID( );
邻接矩阵中非0元素(或非 元素)的个数就是图的弧的个数。
对于n个顶点e条边的无向图，邻接矩阵表示时有n n个元素，2 e个非0元素。
对于n个顶点e条边的有向图，邻接矩阵表示时有n n个元素，e个非0元素。
3)图的邻接矩阵的操作
定义两个数组分别存储顶点信息(数据元素)和边或弧的信息(数据元素之间的关系) 。
图的各种操作。
①图的创建
②图的顶点定位
实际上是确定一个顶点在 vexs 数组中的位置(下标) ，其过程完全等同于在顺序存储的线性表中查找一个数据元素。
③向图中增加顶点
向图中增加一个顶点的操作，类似在顺序存储的线性表的末尾增加一个数据元素。
④向图中增加一条弧
根据给定的弧或边所依附的顶点，修改邻接矩阵中所对应的数组元素。
(2)邻接链表法
1)基本思想：类似于树的孩子链表法，就是对于图 G 中的每个顶点 ，将所有邻接于 的顶点 链成一个单链表，这个单链表就称为顶点 的邻接链表，再将所有点的邻接表表头放到数组中，就构成了图的邻接链表。
对无向图，其邻接链表是唯一(按顺序链接)的；对有向图，其邻接链表有两种形式。
2)从图的邻接表存储方法容易看出，这种表示具有以下特点:
①表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目。
②在边稀疏的情况下，用邻接表表示图比邻接矩阵节省存储空间。
③在无向图的邻接表中，顶点 的度恰为第 i 个链表中的结点数。
④有向图可以建立一个正邻接表和逆邻接表，便于统计每个结点的出度和入度。
⑤在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点( 和 )之间是否有边或弧相连，则需搜索第 i 个或第 j 个链表，因此，不及邻接矩阵方便。
对于n个顶点e条边的无向图，邻接表表示时有n个表头结点，2 e个表结点。
对于n个顶点e条边的有向图，邻接表表示时有n个表头结点，表结点数不确定，但正邻接表加上逆邻接表表结点数为e。
3)表结点及其类型定义
图的各种操作
①图的创建
②顶点定位
图的顶点定位实际上是确定一个顶点在 AdjList 数组中的某个元素的 data 域内容。
③向图中增加顶点
向图中增加一个顶点的操作，在 AdjList 数组的末尾增加一个数据元素。
④向图中增加一条弧
根据给定弧或边所依附的顶点，修改单链表，无向图修改两个单链表;有向图修改一个单链表。
(3) 十字链表法
十字链表(Orthogonal List)是有向图的另一种链式存储结构，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。
在这种结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将弧结点分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。这种结构的结点逻辑结构如图所示。
data 域:存储和顶点相关的信息;
指针域 firstin:指向以该顶点为弧头的第一条弧所对应的弧结点，即逆邻接链表;
指针域 firstout:指向以该顶点为弧尾的第一条弧所对应的弧结点，即正邻接链表;
尾域 tailvex:指示弧尾顶点在图中的位置;
头域 headvex:指示弧头顶点在图中的位置;
指针域 hlink:指向弧头相同的下一条弧;
指针域 tlink:指向弧尾相同的下一条弧;
Info 域:指向该弧的相关信息，比如权值;
结点类型定义：
下图所示是一个有向图及其十字链表(略去了表结点的 info 域)。实质就是先把图的正邻接链表(出度)画出来，然后再把firstin,firstout,hlink,tlink连起来。
(4)邻接多重表法
邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构。
邻接多重表的结构和十字链表类似，每条边用一个结点表示。
邻接多重表中的顶点结点结构与邻接表中的完全相同，而表结点包括六个域。
data 域:存储和顶点相关的信息;
指针域 firstedge:指向依附于该顶点的第一条边所对应的表结点;
标志域 mark:用以标识该条边是否被访问过;
ivex 和 jvex 域:分别保存该边所依附的两个顶点在图中的位置;
info 域:保存该边的相关信息;
指针域 ilink:指向下一条依附于顶点 ivex 的边;
指针域 jlink:指向下一条依附于顶点 jvex 的边;
结点类型定义:
邻接多重表与邻接表的区别:后者的同一条边用两个表结点表示，而前者只用一个表结点表示;除标志域外，邻接多重表与邻接表表达的信息是相同的，因此，操作的实现也基本相似。
Ⅲ 十字链表的介绍
十字链表（Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。
Ⅳ 十字链表的十字链表
十字链表（Orthogonal List)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧都有一个结点，对应于每个定顶点也有一个结点。
十字链表之于有向图，类似于邻接表之于无向图。
也可以理解为 将行的单链表和列的单链表结合起来存储稀疏矩阵称为十字链表， 每个节点表示一个非零元素。
Ⅳ 图的五种存储结构
图的邻接矩阵（Adjacency Matrix）： 图的邻接矩阵用两个数组来表示图。一个一维数组存储图中顶点信息，另一个二维数组（一般称之为邻接矩阵）来存储图中的边或者弧的信息。从邻接矩阵中我们自然知道一个顶点的度（对于无向图）或者有向图中一个顶点的入度出度信息。
假设图G有n个顶点，则邻接矩阵是一个n*n的方阵。
1.对于如果图上的每条边不带权值来说，那么我们就用真（一般为1）和假（一般为0）来表示一个顶点到另一个顶点存不存在边。下面是一个图的邻接矩阵的定义：
邻接矩阵法实现带权值的无向图的创建如下：
按照如图输入各边（不重复）
测试程序如下：
结果可得该矩阵，证明创建树成功。 假设n个顶点e条边的创建，createGraph算法的时间复杂度为O（n+n*n+e）。如果需要创建一个有向图，那么和上面一样一个一个录入边下标和权值。
邻接矩阵这种存储结构的优缺点： 缺点是对于边数相对顶点较少的稀疏图来说会存在极大的空间浪费。假设有n个顶点,优点是对于有向完全图和无向完全图来说邻接矩阵是一种不错的存储结构，浪费的话也只浪费了n个顶点的容量。
在树的存储结构一节中我们提到对于孩子表示法的第三种：用一段连续的存储单元（数组）存储树中的所有结点，利用一个单链表来存储数组中每个结点的孩子的信息。对于图的存储结构来说，我们也可以利用这种方法实现图的存储
邻接表(Adjacency List): 这种数组与链表相结合的存储方法叫做邻接表。1.为什么不也用单链表存储图的结点信息呢？原因就是数组这种顺序存储结构读取结点信息速率快。对于顶点数组中，每个数据元素还需要存储一个指向第一个邻接顶点的指针，这样才可以查找边的信息2.图中每个顶点Vi(i > 0)的所有邻接点构成一个线性表 （在无向图中这个线性表称为Vi的边表，有向图中称为顶点作为弧尾的出边表） ，由于邻接点的不确定性，所以用链表存储，有多少个邻接点就malloc一个空间存储邻接点，这样更不会造成空间的浪费（与邻接矩阵相比来说）。3.对于邻接表中的某个顶点来说，用户关心的是这个顶点的邻接点，完全可以遍历用单链表设计成的边表或者出边表得到，所以没必要设计成双链表。
邻接表的存储结构：
假设现在有一无向图G，如下图：
从邻接表结构中，知道一个顶点的度或者判断两个顶点之间是否存在边或者求一个顶点的所有邻接顶点是很容易的。
假设现在有一有向图G，如下图：
无向图的邻接表创建示例如下：
假设在上图（无向图）中的V0V1V2V3顶点值为ABCD，则依据下面测试程序可得结果：
邻接表的优缺点： 优点是：邻接表存储图，既能够知道一个顶点的度和顶点的邻接结点的信息，并且更不会造成空间的浪费。缺点是邻接表存储有向图时，如果关心的是顶点的出度问题自然用邻接表结构，但是想了解入度需要遍历图才知道（需要考虑逆邻接表）。
十字链表(Orthogonal List) ：有向图的一种存储方法，它把邻接表和逆邻接表结合起来，因此在十字链表结构中可以知道一个顶点的入度和出度情况。
重新定义顶点表的结点如下图：
现在有一有向图如下图：
则它的存储结构示意图为：
其定义如下：
十字链表是用来存储有向图的，这样可以看出一个顶点的出入度信息。对于无向图来说完全没必要用十字链表来存储。
在无向图中，因为我们关注的是顶点的信息，在考虑节约空间的情况下我们利用邻接表来存储无向图。但是如果我们关注的是边的信息，例如需要删除某条边对于邻接表来说是挺繁琐的。它需要操作两个单链表删除两个结点。因此我们仿照十字链表的方式对边表结点结构重新定义如下图：
它的邻接多重表结构为：
多重邻接表的优点：对于边的操作相比于邻接表来说更加方便。比如说我们现在需要删除(V0,V2)这条边，只需将69步骤中的指针改为nullptr即可。
边集数组(edgeset array)： 边集数组是由两个数组组成，一个存储顶点信息，另一个存储边的信息，这个边数组中的每个数据元素由起点下标，终点下标，和权组成（如果边上含有权值的话）。
边数组结构如下图：
边集数组实现图的存储的优缺点：优点是对于边的操作方便快捷，操作的只是数组元素。比如说删除某条边，只需要删除一个数组元素。缺点是：对于图的顶点信息，我们只有遍历整个边数组才知道，这个费时。因此对于关注边的操作来说，边集数组更加方便。