前端培训找不到工作的多吗_中国环球贸易网_品牌如何推广_免费的关键词挖掘工具

---

图的存储

---

一、图的存储

1.邻接矩阵

1.1 介绍

就是用矩阵来表示图，其中图的顶点有几个就是有几行几列，所以这是个方阵。

那矩阵里面的值是什么呢？如果它没有权，那就用1、0表示有没有边，还是得看图，比如下面这个图，第一行第二列是1，就代表A到B有边，无向图A到B有边说明B到A也有边，所以第二行第一列也是1（所以无向图的邻接矩阵是个对称矩阵），有向图就不是，比如有向图的邻接矩阵第二行第一列就不是1，表示B到A是没边的。

现在我们知道了邻接矩阵大概是怎么个意思，就是把图的顶点和边存储起来用矩阵来表示，那么我们的数据结构是什么样的呢？肯定先有个顶点数组，再来个矩阵（二维数组），可以酌情添加顶点数啥的，就是这样：

#define MaxVertexNum 100  //顶点数目的最大值typedef struct{char Vex[MaxVertexNum];     //顶点表int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵，边表int vexNum, arcNum;         //图的当前顶点数和边数/弧数
}MGraph;

由上可知，我们顶点表是char类型的，但其实如果有其他需要，顶点表中也可以存更复杂的信息。还有我们其实是用1、0来表示有没有边的，我们用了int型，但其实可以用bool型或枚举型变量表示边，因为一个int占4B，一个bool型占1B，占的空间会少点。

那么总结一下，结点数为n的图G=(V,E)的邻接矩阵A是n*n的。将G的顶点编号为v₁，v₂，……，v_n，则：

• 若（v_i,v_j）或<v_i,v_j>是E(G)中的边，则A[i][j]=1；
• 若（v_i,v_j）或<v_i,v_j>不是E(G)中的边，则A[i][j]=0；

知道了这些之后，我们如何求顶点的度、出度、入度呢？

对于无向图来说，显然第i个结点的度=第i行（或第i列）非零元素的个数；对于有向图来说，由于它是有向的，所以要出度入度分别求：

• 第i个结点的出度=第i行的非零元素的个数
• 第i个结点的入度=第i列的非零元素的个数
• 第i个结点的度=第i行、第i列的非零元素的个数之和

邻接矩阵法求顶点的度/出度/入度的时间复杂度是O(n)（或O(|V|)，都是一个意思）

那么我们刚刚说的都是不带权的，如果带权的该怎么整？其实显然就是让这个矩阵不要再存有没有边了，有边就存权值，没边就是∞，这就行了。还有我们顶点自己到自己，显然是没有距离，所以给它自己到自己都设为0（设为其他也行，反正是自己到自己）。上个图：

当然我们数据结构还是和原来一样，只不过存的内容变成了权，而且我们要设置一个东西来表示“∞”，一般是最大的int值，也就是用int的上限值表示“无穷”（弱弱说一句：在C/C++中，int类型占4B，所以最大的int值是2³¹-1，也就是2147483647，当个小拓展）。

#define MaxVertexNum 100  //顶点数目的最大值
#define INFINITY 2147483647  //宏定义常量“无穷”typedef struct{char Vex[MaxVertexNum];     //顶点表int Edge[MaxVertexNum][MaxVertexNum];   //边的权int vexNum, arcNum;         //图的当前顶点数和边数/弧数
}MGraph;

这个“权”其实也不一定是int。我们上一篇不是说过吗，它其实是表示某种实际意义，所以这个定义为我们需要的权值的数据类型就可以了。

我们现在啥都知道了，来分析一下邻接矩阵法的性能

首先当然是复杂度。使用邻接矩阵法，空间复杂度和有多少条边没关系，因为不论有多少条边我们都开那么大的空间，所以我们的空间复杂度是O(|V|²)。（顶点的O(|V|)量级比O(|V|²)量级小所以忽略）；那么我们开那么多空间，如果没利用到就可惜了，所以邻接矩阵法比较适合用于存储稠密图；

无向图的邻接矩阵是对称矩阵，可以用压缩存储（只存储上三角区/下三角区），还记得么？就是之前说的按照行优先啥的将各元素存入一位数组中，然后又是矩阵下标a_i,_j和一维数组下标B[k]对应啥的，在之前的那篇——数据结构第三章（三）-数组和特殊矩阵里哈。

_{我还是多说点，带着回顾一下，就是按行优先原则存储，只存储主对角线+下三角区，我们存到多大的数组里？第一行1个，第二行2个…第n行n个，所以大小为n*(n+1)/2个，就是一个B[n*（n+1）/2-1]的数组内。我们怎么知道ai,j对应的B[k]中k是什么？我们下三角区的ai,j,上面有i-1行，这i-1行，一共有1+2+…+i-1个元素，即i(i-1)/2个。除此之外，ai,j它当行前面有j-1个元素，所以行优先中，ai,j是第i(i-1)/2+j个元素，对应的B[k]中k就是i(i-1)/2+j-1（第一个元素对应的是B[0]），这是当i≥j的时候（下三角区嘛）。当i<j的时候，上三角区的元素呢？由于是个对称矩阵，所以ai,j=aj,i，所以当i<j时，B[k]中k就是j(j-1)/2+i-1。}

1.2 邻接矩阵法的性质

看这个看这个看这个图，这是一个平平无奇的邻接矩阵是吧：

先给个结论，马上我们再细说：

设图G的邻接矩阵为A（矩阵元素为0/1），则Aⁿ的元素Aⁿ[i][j] 等于由顶点i到顶点j的长度为n的路径的数目。

来看这个矩阵相乘：

比如按照上面说的，那么A²[1][4]就是求A到D的长度为2的路径的数目。我们要求A²[1][4]我们怎么求？对乘加是吧，把左边矩阵的第1行和右边矩阵的第4列对乘加，也就是：

A²[1][4] = a_1,1a_1,4 + a_1,2a_2,4 + a_1,3a_3,4 + a_1,4a_4,4 = 1

拆开看：

a_1,1是什么？是A到A的路径，a_1,4是什么？是A到D的路径。a_1,4是0，A到D没路。
a_1,2是什么？是A到B的路径，a_2,4是什么？是B到D的路径。a_1,2是1，A到B有路；a_2,4是1，B到D有路，所以 a_1,2a_2,4 =1，也就是有一个从A到D长度为2的路径，是A——>B——>D。
a_1,3是什么？是A到C的路径，a_3,4是什么？是C到D的路径。a_1,3是0，A到C没路；a_3,4也是0，C到D也没路。
a_1,4是什么？是A到D的路径，a_4,4是什么？是D到D的路径。a_1,4是0，A到D没路。

soA到D的长度为2的路径的数目只有一条，路径为A——>B——>D。

我感觉，感觉哈，其实就是，求长度为x的路径的数目，就是看它每一步是不是都是1，中间几个转弯都是1的话不就是相当于有长度为x的路径了吗，因为就是要乘x次。

知道了原理之后其实就可以直接求出矩阵看了，比如看这张图，我们求了个A³，又因为刚刚说Aⁿ的元素Aⁿ[i][j] 等于由顶点i到顶点j的长度为n的路径的数目，所以我们随便挑一个，你看A³[1][4]是1，也就是A到D的长度为3的路径的数目有1条，我们再对应上面的图看看，发现确实是1条，A——>B——>C——>D。

2.邻接表

我们刚刚说的邻接矩阵其实就是数组实现的顺序存储，空间复杂度高，不适合存储稀疏图。如果我们要存稀疏图怎么办呢？这就是我们要说的邻接表，它非常方便，使用顺序+链式存储来实现的。

来看这个，眼熟吗？这个其实有点像之前我们说到的树的孩子表示法，也就是顺序存储各个结点，每个结点中保存孩子链表头指针，然后指针指向第一个孩子（指针只存自己的孩子，不往下存），这个真的很像，简直一毛一样：

我们先定义边：

//“边/弧”
typedef struct ArcNode{int adjvex;     //边/弧指向哪个结点struct ArcNode *next;  //指向下一条弧的指针int weight;     //边权值
}ArcNode;

所谓的边/弧指向哪个结点其实就是这个结点的数组下标。其实这就是个结点，它保存的数据就是弧头和这条的权值而已。

看顶点：

#define MaxVertexNum 100  //顶点数目的最大值//“顶点”
typedef struct VNode{char data;      //顶点信息，类型自定义ArcNode *first; //第一条边/弧
}VNode, AdjList[MaxVertexNum];

这就相当于你看上面那个图的包含data和*first的一整个，存一个结点信息一个指针，也没啥特殊的。

那我们的图就是：

//用邻接表存储的图
typedef struct{AdjList verticles;int vexNum, arcNum; //图的当前顶点数和边数/弧数
}ALGraph;

这就是有了MaxVertexNum个刚刚说的一整个，也就是这个图先给它整了这么多顶点来用着。当然也可酌情更改，这些都不是固定的。

看看有向图的，都一样的：

但是！！！有不一样的地方！！！

你有没有发现，我们无向图其实整重复了，我们存了两次，也就是比如你看有A到B，也有B到A，但是其实我们只有一条边，每条边都存两次所以我们无向图边结点的数量其实是 2|E| ，所以整体空间复杂度为 O( |V| + 2|E| )；但是我们有向图就不这样，因为我们有向，所以不会重复，也就是我们有向图边结点的数量是 |E| ，整体空间复杂度为 O( |V| + |E| )。

现在我们已经知道了什么是邻接表，那和邻接矩阵一样，我们要开始考虑怎么求顶点的度、出度、入度了。无向图求度其实就是往下遍历我们的“孩子链表”，有几个度就是几，有向图出度也是这样；但是有向图入度就不是了，我们得遍历整个图才知道都有谁指向它，所以会很麻烦。

除此之外，我们如何找到与一个顶点相连的边/弧？也是一样的，无向图就很方便，有向图还是找入边不方便，遍历整个图才能找到。

当然我们的邻接表其实是不唯一的，没有特定的顺序，链表中谁当第一个结点第二个结点顺序都是不固定的，但是邻接矩阵唯一，只要确定了顶点编号，图的邻接矩阵表示方式就唯一确定了。

小结一下：

	邻接表	邻接矩阵
空间复杂度	无向图 O( V + 2E )，有向图O( V + E)	O(V2)
适合用于	存储稀疏图	存储稠密图
表示方式	不唯一	唯一
计算度/出度/入度	计算有向图的度、入度不方便，其余很方便	必须遍历对应行或列
找相邻的边	找有向图的入边不方便，其余很方便	必须遍历对应行或列

3.十字链表（存储有向图）

我们刚刚已经知道了邻接表法找顶点的入边不方便，且用邻接矩阵法如果是稀疏图空间复杂度又太高，那我们为了解决这些，就衍生出一种新的方式，如下：

这是啥玩意儿？表面上看很复杂，其实一点也不复杂。其实就还是顶点+弧的配置，但这回顶点里面的信息有点多，它包含指向以这个顶点出发的第一条边，和以这个顶点为结尾的第一条边；边结点的信息也有点多，它包含这条边的首和末顶点编号，还包含和这个边的出发顶点一样的下一条边与和这个边的结束顶点一样的下一条边。

什么意思呢？对着上面那个图来看：比如你看A结点，它有一条边指向一个边结点（这个边结点的首是0末是1，表示由A到B），但是由图可知我们A结点出发的边不止有AB，还有AC，所以第一个边结点的tlink指针指向了下一个边结点（这个边结点的首是0末是2，表示由A到C），我们就找到了以A为出发点的所有边（因为现在这个结点的tlink是null）。

除了刚刚说的绿色部分，我们还能看到橙色部分是不？现在再来看A结点，橙色部分指向的是一个边结点（这个边结点的首是2末是0，表示由C到A），就可以知道以A为末尾是谁在指它。又由图可知我们A被指也不止有CA，还有DA，所以我们顺着边结点的hlink找，就找到了另一个边结点（这个边结点的首是3末是0，表示由D到A），这就找到了以A为末尾是谁在指它的所有结点（因为现在这个DA的hlink是null）。

注意一下我们边结点随便从一个边结点出发，它的hlink指针指向的都是结束点与headvex相同的边，它的tlink指针指向的都是结束点与tailvex相同的边。

现在再看是不是很清晰：

我们这个十字链表的空间复杂度显然是O( |V| + |E| )；那么我们现在再来看看之前的那个问题：如何找到指定节点的出入边？其实就是刚刚说的，顺着绿色线路寻找找的就是指定节点所有出边，顺着橙色线路寻找找到的就是指定节点的所有入边。

注意：十字链表只用于存储有向图。

4.邻接多重表（存储无向图）

无向图也没什么出边入边的，所以也没什么弧头弧尾。但是邻接多重表和十字链表还是很相似的，就是不再区分头尾只用边了，长这样：

比如我们找C结点的边，我们看C结点指向的第一个结点，它的结点编号i是2，代表C结点，j是1，代表B结点，我们就找到了BC这条边，我们应该顺着 iLink 去找（找依附于顶点 i 的下一条边），我们找到了下一个边结点， j 是3，代表我们找到了CD这条边，再顺着 iLink 找，找到了下一个结点，j是4，代表我们找到了CE这条边，至此查找结束，因为这个结点的 iLink 是null，代表我们找完了所有和C连接的边；

再比如我们找和B相连的边，我们看B结点指向的第一个结点，它的结点编号i是2，代表C结点，j是1，代表B结点，我们就找到了BC这条边，我们应该顺着 jLink 去找（找依附于顶点 j 的下一条边），我们找到了下一个边结点，i 是4，代表我们找到了BE这条边，至此查找结束，因为这个结点的 jLink 是null，代表我们找完了所有和B连接的边。

这样的话我们的空间复杂度就是 O( |V| + |E| )了，相比用邻接表存的O( |V| + 2|E| )要好很多；这个删除边、结点等操作也很方便，删除边就和删除链表节点一样，不过要注意删除结点的话要把所有相邻的边结点都相应删除。

注意：邻接多重表只用于存储无向图。

二、图的基本操作

一些基本操作就是大概看到知道是用来干啥的就行了，因为我们后面会讲到关于图的算法，书上也没细说，但是这些都得有个印象：

• Adjacent(G,x,y)：判断图G是否存在边<x,y>或（x,y）；
• Neighbor(H,x)：列出图G与结点x相邻的边；
• InsertVertex(G,x)：在图G中插入顶点x；
• DeleteVertex(G,x)：从图G中删除顶点x；
• AddEdge(G,x,y)：若有向边<x,y>或无向边（x,y）不存在，则向图G中添加该边；
• RemoveEdge(G,x,y)：若有向边<x,y>或无向边（x,y）存在，则向图G中删除该边；
• FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1；
• NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x最后一个邻接点，则返回-1；
• Get_edge_value(G,x,y)：获取图G中边（x,y）或<x,y>对应权值；
• Set_edge_value(G,x,y,v)：设置图G中边（x,y）或<x,y>对应权值为v。

---

总结

讲了一些图的存储方式，一般用最多的还是邻接矩阵法了，因为这个比较直观方便。还有就是要注意以下出度、入度的求法，以及各个方式的空间复杂度有什么不同。