图的存储—邻接矩阵和邻接表
图的存储—邻接矩阵和邻接表
图的存储—邻接矩阵和邻接表
前言
身为小白的我太容易忘记图的存储了，导致后面对于图论的题目总是很生疏，于是写下这篇文章来加深印象，希望能帮助到正在学习邻接矩阵和邻接表的你。若对文章内容有疑惑，欢迎评论区发言，小白会积极改进的。
参考文献：严蔚敏，吴伟民，《数据结构(C语言版)》[M].北京：清华大学出版社,2011.
一、图的存储结构
在图结构中，节点之间的关系是任意的，图中任意两个数据元素都可能相关，是非线性结构。
所以图没有顺序存储结构，顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系的，适用于线性结构。但是，可以采用邻接矩阵（一个二维数组），来表示元素之间的关系，此外，任意两个顶点都可能存在关系，因此可以使用链表来表示图。
二、邻接矩阵
邻接矩阵是表示顶点之间相邻关系的矩阵。设G(V,E)是具有n个顶点的图，则它的邻接矩阵就是n方阵。
1.邻接矩阵表示法
1.1 图的邻接矩阵
在图中，a[i][j]:表示顶点vi和vj的关系，也就是它们之间有没有边，如果有边就赋值为1，没有边就赋值为0：
举例：
分析：
（1）我们可以发现，在无向图中a[i][j] = a[j][i]，这是为什么呢？
我们要明白a[i][j]，表示的是顶点vi和顶点vj有没有边。在无向图中，若vi和vj之间有边，那么vj和vi之间也有边，都为1；如果没有边，那么都为0。
（2）还可以发现，无论是有向图还是无向图，当i = j我们都会把他赋值为0，将自身到自身视为没有边。
（3）在无向图中，顶点的度为第i行或第i列的元素之和。第i行表示：顶点vi和其他顶点的关系；第i列表示：其他顶点和顶点vi的关系。可以区分入度和出度，但由于是无向图，没有入度和出度之分，所以两者的值是一样的；对于有向图，第i行元素之和就是顶点vi的出度，第j列元素之和就是顶点i的入度。
1.2 网的邻接矩阵
在网（有权值的图）中，a[i][j]:表示顶点vi和vj的关系，如果存在边，那么a[i][j]赋值为它们边的权值，如果没有边，则赋值为∞：
举例：
网中除了权值，和默认值与图不同外，其余步骤都相同。
1.3 图的邻接矩阵存储表示
用邻接表表示法表示图，除了一个用于存储邻接矩阵的二维数组外，还需要用一个一维数组来来存储顶点的信息。
形式说明：
#define MaxInt = 32767 // 用于表示∞
#define MaxNum 100 // 最大定点数，因为定义数组需要长度
typedef struct {
char vexs[MaxNum]; // 存储顶点信息的一维数组
int arcs[MaxNum][MaxNum]; // 定义二维数组，表示邻接矩阵
int vexnum, arcnum; // 图的实际顶点数和边数
}AMGraph; // 因为邻接矩阵单词是:Adjacency Matrix
2.采用邻接矩阵表示法创建无向网
2.1 算法步骤
（1）获取总顶点数和总边数。// 后续操作都与它们有关
（2）初始化邻接矩阵，每个权值初始值都为极大值。
（3）输入每条边依附的顶点（输入的这两个顶点其实就是表示一条边），并输入它的权值，确定两个顶点在图中的位置（也就是获取i和j,这样就可以给a[i][j]赋值，通过函数LocateVex来确定）之后，使其相应边赋予相应的权值，同时使其对应边赋予相同的权值（因为是无向图）。
2.2 算法描述
int LocateVex(AMGraph &G, int v) { // 获取顶点v在图G中的位置
for(int i = 0; i < G.vexnum; i++) {
if(v == G.vexs[i]) {
return i;
}
}
return -1;
}
// 用邻接矩阵创建无向网，其实就是同通过对邻接矩阵的赋值操作，以表示顶点间的关系
void CreateUDN(AMGraph &G) { // UDN表示无向网
cin >> G.vexnum >> G.arcnum; // 步骤一：输入总顶点数和总边数
for(int i = 0; i < G.vexnum; i++) { // 步骤二：初始化邻接矩阵，初始值默认为∞，我们用MaxInt表示
for(int j = 0; j < G.arcnum; j++) {
G.arcs[i][j] = MaxNum;
}
}
int v1, v2, w;
int i, j;
for(int k = 0; k < G.vexnum; k++) { // 步骤三：输入各边（输入这条边依附的两个顶点），并对邻接矩阵赋值（权值），依次表示顶点之间的关系
cin >> v1 >> v2 >> w;
i = LocateVex(G,v1);
j = LocateVex(G, v2);
G.arcs[i][j] = w;
G.arcs[j][i] = w; // 注意
}
}
2.3 算法分析
该算法时间复杂度为O(n^2)
若要建立无向图，首先要明白无向图和无向网的区别：无向图的两个顶点间有边时，我们用1来标识，而无向网存储的是这条边的权值；无向图的两个顶点间没有边时，我们用0来标识，而无向网中默认是∞，所以要建立无向图，可以改动一下上面的算法就可以了：矩阵默认初始为0，无需输入权值，在输入两点之后，直接对这条边赋值为1即可。
2.4 邻接矩阵表示法的优缺点
(1)优点
1.便于判断两个顶点之间是否有边，因为a[i][j] = 1表示有边，a[i][j] = 0表示无边，一目了然。
2.便于判断各个顶点的度。通过前面的矩阵我们可以发现，对于无向图，邻接矩阵第i行或第i列的元素之和就是顶点vi的度；对于有向图，第i行元素之和就是顶点vi的出度，第j列元素之和就是顶点i的入度。
(2)缺点
1.不便于增加和删除节点。因为邻接矩阵本质就是一个二维数组，要对二维数组进行增加节点和删除节点操作都是不方便的。
2.不便于统计边的数目。a[i][j] = 1表示有边，a[i][j] = 0表示没有边，对于这个邻接矩阵，我们要遍历完整个矩阵才能统计出来，若是无向图，可以只遍历上三角，但是依旧是不方便的。
3.空间复杂度高。如果是有向图，就必须要为n阶方阵，来存储所有顶点间的关系；对于无向图，可以采用压缩存储的方式，这样需要n(n - 1)/2个单元即可。但无论以何种存储，对于稀疏图而言，非常浪费空间。
三、邻接表
3.1 邻接表表示法
邻接表表示法，其实就是给每个顶点都整一条链表，这些顶点在表头，后面跟着与这些顶点有关的顶点，也就是与这些顶点相连的顶点。注意，如果它们的边是有向的，vi到vj有边，则vj到vi没有边的边，我们不应该记录vj到vi的边，也就是不应该赋值，而是默认值。
邻接表可以由两部分组成：表头节点和边表。
3.1.1 表头结点
两部分，数据域(data)和链域(firstarc),数据域用于存储顶点vi的名称或其他有关信息；链域用于指向链表中第一个节点（与顶点vi邻接的顶点）。
3.1.2 边表
三部分，邻接点域（adjvex）、数据域（info）和链域（nextarc），邻接点域指示与顶点vi邻接的点在图中的位置；数据域存储和边相关的信息，如权值；链域指示与顶点vi邻接的下一条边的节点。
在无向图的邻接表中，顶点vi的度恰为第i个链表中的节点个数；而在有向图中，第i个链表中的节点个数只是顶点vi的入度，为求入度，必须遍历整个邻接表。在所有邻接表中，其邻接点域的值为i的节点个数就是顶点vi的入度（其他节点指向这个节点）。
3.1.3 图的邻接表存储表示
#define MaxNum 100 // 最大顶点数，因为后边有个表头节点数组
typedef struct ArcNode { // 边节点
int adjvex; // 邻接点域
struct ArcNode * nextarc; // 链域
int info; // 信息域
}ArcNode;
typedef struct VNode {
char data; // 数据域
ArcNode *firstarc; // 链域,指向一个ArcNode类型的指针。
}VNode,AdjList[MaxNum];
typedef struct {
AdjList vertices; // 它是AdjList类型的，即一个包含MaxNum个VNode结构体的数组
int vexnum, arcnum; // 当前图的顶点数和边数
}ALGraph; // 邻接表英文：Adjacency List
3.2 用邻接表表示法创建无向网
3.2.1 算法步骤
（1）输入总顶点数和总边数。// 因为后面会输入顶点的信息，以及它们的边，需要提前直到它们的数量，好控制范围
（2）依次输入点的信息存入顶点表中，使每个表头节点的指针域初始化为BULL。// 就是初始化表头节点不指向任何顶点
（3）输入每条边依附的两个顶点，确定这两个顶点的序号i和j之后，将此边节点分别插入vi和vj对应的两个边链表的头部。
3.2.2 算法描述
int LocateVex(ALGraph &G, int v) {
for(int i = 0; i < G.vexnum; i++) {
if(v == G.vertices[i].data) {
return i;
}
}
return -1;
}
void CreateUDN(ALGraph & G) {
cin >> G.vexnum >> G.arcnum; // 步骤一：输入总顶点数和边数
for(int i = 0; i < G.vexnum; i++) { // 初始化邻接表
cin >> G.vertices[i].data;
G.vertices[i].firstarc = NULL;
}
int v1, v2;
int i, j;
for(int k = 0; k < G.arcnum; k++) {
cin >> v1 >> v2;
i = LocateVex(G, v1);
j = LocateVex(G, v2);
// 创建新的边节点
ArcNode *p1 = new ArcNode; // 分配内存并创建节点
p1->adjvex = j;
p1->nextarc = G.vertices[i].firstarc; // 因为我们会把得到的新的邻接点默认为与此结点相连的第一个邻接点
G.vertices[i].firstarc = p1;
// 因为这个是无向网,v1和v2互为邻接点
ArcNode *p2 = new ArcNode;
p2->adjvex = i;
p2->nextarc = G.vertices[j].firstarc;
G.vertices[i].firstarc = p2;
}
}
3.2.3 邻接表表示法的优缺点
(1)优点
1.便于增加和删除顶点。// 只需要改变指针的指向
2.便于统计边的数目，按着顶点表顺序查找所有边表可得到边的数目，时间复杂度为O(n + e).
3.空间效率高。
(2)缺点
1.不便于判断顶点之间是否有边，要判断vi和vj是否有变，就需要查找第i个边表，最坏情况下时间复杂度为O(n).
2.不便于计算有向图各个顶点的度。
总结
本文章多是参考文献的内容，并附上了一些自己的见解。