图的存储结构
废话不多说，上来撸干货。 我们知道，实现图共有两种常用的方法：邻接矩阵、邻接表法。接下来我们就来一一介绍这两种方法。 实际上，图的存储结构有些复杂，为了方便读者理解，也为了方便笔者的写作，这部分的篇幅会长一些，稍有些啰嗦，还望见谅。
一、邻接矩阵法
显然，图是由顶点（vex）和边（arc）构成的。在这种情况下，如果我们想直接将这两部分合在一起存储，不说别的，单单思维上就很混乱。因为边本身就是由两个顶点连接组成的，所以说，合在一起很困难。 于是，我们就想到了分开存储。而顶点中所包含的数据一般是相同的，所以，利用一维数组来存储顶点数据是很好的办法。那么对于边来说呢？ 边是由两个顶点共同构成的，显然一维数组是无法解决的，那也好办，用二维数组试试。一看，二维数组显然是满足我们的需求的嘛，我们正好可以利用二维数组的两个下标，比如说a[i][j]，我们可以把i想象成顶点表中的第i个顶点，j是第j个顶点，然后用特殊的标识来确定两点之间是否有边，是不是很简单呢？ 这种特殊的标识，就要用到我们在离散数学中学到的矩阵了。我们可以用1表示存在边，0表示不存在边。如图：
这样，就构成了一个二维数组。此外，注意观察：
以矩阵的对角线为中心，两边的数据是对称相等的，这样你联想到了什么呢？没错，就是我们之前学过的对称矩阵。根据之前我们讲的，1和0分别代表有边和无边，所以，通过这个图，我们很容易就能够画出这个无向图了。 此外，通过一行或者是一列中“1”的个数，就能知道某个点的度。若是求结点的邻接点，只需要将该行（列）中“1”对应的数字符号即可。
下面介绍有向图。直接上邻接矩阵。
从这个矩阵上。根据上面无向图的分析，“0”和“1”分别代表的是有边和没有边，所以可以看出各点之间的关系。对于有向图来说，虽然矩阵仍然以主对角线“0”为分界线，但可以看出，对角线的两面并不是对称的。 一般来讲，有向图研究的是入度和出度，在这幅图上，横向代表的是入度，纵向代表的是出度。所以，v1的入度是1，出度是2。 由此可见，要判断有向图或者无向图两点间有没有边，只需查看v[i][j]是否不为零即可（如果是有向网或无向网，边的权值一般不为1，有可能为无穷大，表示不存在边）。
下面看如何用代码实现这个过程：
结构定义
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
//- - - - -图的邻接矩阵存储表示- - - - -
typedef struct{
char vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;
int LocateVex(AMGraph G , VerTexType v){
//确定点v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
if(G.vexs[i] == v)
return i;
return -1;
}//LocateVex有了结构定义，我们就可以进行图的创建，实质上就是向结构中输入数据。
int CreateUDN(AMGraph &G){
//采用邻接矩阵表示法，创建无向网G
int i , j , k;
cout <<"请输入总顶点数，总边数，以空格隔开：";
cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
cout << endl;
cout << "输入点的名称，如a" << endl;
for(i = 0; i < G.vexnum; ++i){
cout << "请输入第" << (i+1) << "个点的名称:";
cin >> G.vexs[i]; //依次输入点的信息
}
cout << endl;
for(i = 0; i < G.vexnum; ++i) //初始化邻接矩阵，边的权值均置为极大值MaxInt
for(j = 0; j < G.vexnum; ++j)
G.arcs[i][j] = MaxInt;
cout << "输入边依附的顶点及权值，如 a b 5" << endl;
for(k = 0; k < G.arcnum;++k){ //构造邻接矩阵
VerTexType v1 , v2;
ArcType w;
cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";
cin >> v1 >> v2 >> w; //输入一条边依附的顶点及权值
i = LocateVex(G, v1); j = LocateVex(G, v2); //确定v1和v2在G中的位置，即顶点数组的下标
G.arcs[i][j] = w; //边<v1, v2>的权值置为w
G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边<v2, v1>的权值为w
}//for
return OK;
}//CreateUDN 时间复杂度 从代码中可知，如果创建n个顶点e条边的邻接矩阵，时间复杂度为O(n+n^2+e)，对邻接矩阵的初始化耗费了O（n^2）的时间。
二、邻接表法
对于邻接矩阵，我们会发现，当图的边数较少的时候，这种存储方法是非常浪费存储空间的（如图所示）。
我们在学习链表的时候知道，由于顺序表存储会浪费空间，所以我们引出了链式表的概念。 显然，我们也能通过链式表来避免这种空间的浪费。 首先，图中的顶点和邻接矩阵中的处理方式相同，用一维数组来存储。（链表也可以，不过操作起来不是很方便） 其次，图中的每个顶点vi的所有邻接点构成一个线性表。由于邻接点的个数不确定，所以用单链表来存储。无向图称为边表，有向图称为顶点vi作为弧尾的出边表。
从图中可以得知，顶点表的各点由data域和指针域firstedge（指向边表的第一个邻接点）。而边表结点由adjvex域（邻接点域，存储某顶点的邻接点在顶点表中的下标）和next指针域（存储边表下一个结点）组成，如图所示，对于无向图，顶点的度通过边表顶点个数可知，若要判断两点间是否存在边，只需看某顶点的边表中是否存在另一个顶点的下标即可。 不过对于有向图，若要确定出度，只需要看顶点vi作为弧尾的出边表中的顶点个数，而出度就需要另外想办法了。
根据“顶点vi作为弧尾的出边表”这个名字可知出度，那么我们是不是可以做出“顶点vi作为弧头的入边表”呢？答案是肯定的。 由此，我们来引出“逆邻接表”的概念。 即以顶点Vi作为弧头建立边表，此时邻接点的个数就是入度了。
所以，可以看出v0的入度是2……
接下来就是代码实现了：
结构定义
//- - - - -图的邻接表存储表示- - - - -
typedef struct ArcNode{ //边结点
int adjvex; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
OtherInfo info; //和边相关的信息
}ArcNode;
typedef struct VNode{
VerTexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct{
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;创建过程
int LocateVex(ALGraph G , VerTexType v){
//确定点v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
if(G.vertices[i].data == v)
return i;
return -1;
}//LocateVex
int CreateUDG(ALGraph &G){
//采用邻接表表示法，创建无向图G
int i , k;
cout <<"请输入总顶点数，总边数中间以空格隔开:";
cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
cout << endl;
cout << "输入点的名称，如 a " <<endl;
for(i = 0; i < G.vexnum; ++i){ //输入各点，构造表头结点表
cout << "请输入第" << (i+1) << "个点的名称:";
cin >> G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL
}//for
cout << endl;
cout << "请输入一条边依附的顶点,如 a b" << endl;
for(k = 0; k < G.arcnum;++k){ //输入各边，构造邻接表
VerTexType v1 , v2;
int i , j;
cout << "请输入第" << (k + 1) << "条边依附的顶点:";
cin >> v1 >> v2; //输入一条边依附的两个顶点
i = LocateVex(G, v1); j = LocateVex(G, v2);
//确定v1和v2在G中位置，即顶点在G.vertices中的序号
ArcNode *p1=new ArcNode; //生成一个新的边结点*p1
p1->adjvex=j; //邻接点序号为j
p1->nextarc= G.vertices[i].firstarc; G.vertices[i].firstarc=p1;
//将新结点*p1插入顶点vi的边表头部
ArcNode *p2=new ArcNode; //生成另一个对称的新的边结点*p2
p2->adjvex=i; //邻接点序号为i
p2->nextarc= G.vertices[j].firstarc; G.vertices[j].firstarc=p2;
//将新结点*p2插入顶点vj的边表头部
}//for
return OK;
}//CreateUDG时间复杂度 O(n+e)
欢迎小伙伴们留言！
结语
感谢您的阅读，欢迎指正博客中存在的问题，也可以跟我联系，一起进步，一起交流！
微信公众号：进击的程序狗 邮箱：roobtyan@outlook.com 个人博客：https://roobtyan.github.io
腾讯云开发者
