引入
由于图的任意两个顶点之间都存在关系，自然无法采用诸如顺序存储结构这种适合一对一，物理地址连续的存储法，但可以采取邻接矩阵或邻接表作为图的存储结构。邻接矩阵
假设i,j分别作为二维数组的横坐标与纵坐标，很显然，i,j两个下标恰好能表示图的两个顶点编号（顶点编号从0开始）。在人为规定的前提下，二维数组中的某元素的数值即可表示顶点之间有无边的存在，如在有向图中arr[i][j]==0表示i到j无弧，否则arr[i][j]==1表示有弧。这种二对一的关系与图的点边关系相类似。
另外，为了方便表示图的关系，在本案例中，arr[i][j]表示<i,j>或(i,j)的关系，当arr[i][j]==0时表示无边。
图的数据结构分析
首先是顶点，顶点具有自己的数据类型，此处以char作为顶点的数据类型（在实际应用中，假若顶点表示城市路口，那么顶点可以存储该路口的车流量，交通状况等等信息），定义 chat 的别名为VexType ,表示顶点数据类型，同时将定义一个一维数组存储顶点的数据，以该一维数组下标作为顶点的编号；
其次是图中的边或弧的信息，此处以无向网为例，故一律称顶点间的连线为边。很显然，二维数组的元素即可作为（i,j）边的数据域，比如数据域可以存储该边的权值或其他信息（结构体定义），若边的数据类型为 int,表示权值，定义 int 的别名为ArcType,那么二维数据的数据类型即为ArcType.
最后，一个图中还有最重要的信息即，图中的顶点个数vexnum以及边的个数arcnum.
代码实现
//文件名：AMGraph.h
#pragma once
#include<iostream>
using namespace std;
#define Maxw 999999 //定义最大权值
#define Mvnum 100 //最大顶点数
typedef char VerType; //顶点数据类型
typedef int ArcType; //边的数据类型
typedef struct AMGraph {
int vexnum, arcnum;
VerType vexs[Mvnum]; //顶点信息表
ArcType arcs[Mvnum][Mvnum]; //邻接矩阵
}AMGraph;
//创建无向网
void CreateUDN(AMGraph& G);
//文件名为：AMGraph.cpp
#include"AMGraph.h"
void CreateUDN(AMGraph& G)
{
//输入顶点与边的个数，图的第一部分信息
cin >> G.vexnum >> G.arcnum;
//判断合法性
if (G.vexnum > Mvnum || G.arcnum > (G.vexnum - 1) * G.vexnum / 2)
{
cout << "所输入信息非法" << endl;
return;
}
//紧接着输入顶点的信息,图的第二部分信息
for (int i = 0;i < G.vexnum;i++)
{
cin >> G.vexs[i];
}
//将图的边初始化,权值全部置为0
for (int i = 0;i < G.vexnum;i++)
{
for (int j = 0;j < G.vexnum;j++)
G.arcs[i][j] = 0;
}
//输入权值
for (int i = 0;i < G.arcnum;i++)
{
//输入v1,v2作为边(v1,v2)的顶点以及边之间的权值w
//编号从0开始
int v1, v2, w;
//此处省略了查找v1,v2编号的过程
cin >> v1 >> v2 >> w;
//时刻关注合法性
if (v1 == v2 || v1 >= G.vexnum || v2 >= G.vexnum
|| w > Maxw||v1<0||v2<0)
{
i--;
continue;
}
if (G.arcs[v1][v2] != 0)
{
i--;
continue;
}
//输入边的权值
G.arcs[v1][v2] = G.arcs[v2][v1] = w;
}
//创建完毕
}
注意事项：顶点编号V1、V2从0开始，在条件判断务必注意。
其余转化：
当我们需要存储无向图时，只需要将数组的元素值限定在0和1，0表示无边，1表示有边；
当我们需要存储有向网时，需要修改判定条件第八行： G.arcnum > (G.vexnum - 1) * G.vexnum / 2为 G.arcnum > (G.vexnum - 1) * G.vexnum；第45行代码改为 G.arcs[v1][v2] =w；（因为有向网的弧有方向性）。存储有向图的方式都差不多。
算法评估
优点：
- 能够快速判断两个顶点间是否存在边；
- 能够快速判断每个顶点的度，只需要限定横坐标为k，扫描G.arcs[k][j]不等于0的元素个数，（j从0开始）；
缺点：
- 难以快速判断边的个数，需要从G.arcs[0][0]开始查找，时间复杂度为O（n^2）;
- 对于有向图或有向网而言，难以快速判断顶点的出度与入度。对于顶点k而言，计算其入度需要扫描G.arcs[j][k]不等于0的元素个数，（j从0开始）；计算其出度需要扫描G.arcs[k][j]不等于0的元素个数，（j从0开始）；总之，所有顶点都需要扫描一边，时间复杂度为O（n^2）;
- 空间复杂度高，O（n^2）,且空间的浪费程度高。例如，对于无向图或者无向网而言，G.arcs[j][i]与G.arcs[i][j]等存储结果一样，且单独一个都能说明i与j之间的点边关系。
适用范围
1.图为稠密图；2.无需考虑出入度问题；
压缩版邻接矩阵（非必要掌握）
针对无向图或无向网而言，由于邻接矩阵是对称矩阵，且当i==j时，G.arcs[j][i]注定等于0，毫无存在意义。因此，以下利用压缩矩阵存储提高空间利用率。
规定，顶点编号i,j从0开始。
我们定义一个一维数组作为压缩矩阵的存储结构，其中一位数组的下标x，注定于顶点编号i、j间存在代数关系。我们选取上三角矩阵的元素作为压缩矩阵的存储元素，当我们依次从原来邻接矩阵的第零行开始，从左到右，从上到下选取元素。如下图，非白色部分为选取为压缩矩阵的元素。
规定i<j，那么x与i,j的关系式为：x=（2*G.vexnum-i-1）*i/2+j-i-1
公式解释，由于第一条边(0,1)的存储下标为x0=0,那么对于边（i,j）只需要知道其前面有多少个元素，即可知道其存储下标。对于第i行，第j列元素而言，其上i-1到0层的元素个数为：SUM=(G.vexnum-1)+(G.vexnum-2)+……+(G.vexnum-i)=（2*G.vexnum-i-1）*i/2;对于第i行的第j列的元素而言，其所在列前面的元素一共有j-i-1个，因此x=（2*G.vexnum-i-1）*i/2+j-i-1。
代码实现
typedef struct CAMGraph {
int vexnum, arcnum;
VerType vexs[Mvnum]; //顶点信息表
ArcType arcs[Mvnum*(Mvnum-1)/2];
}CAMGraph;
void CreateUDN(CAMGraph& G)
{
//输入顶点与边的个数，图的第一部分信息
cin >> G.vexnum >> G.arcnum;
//判断合法性
if (G.vexnum > Mvnum || G.arcnum > (G.vexnum - 1) * G.vexnum / 2)
{
cout << "所输入信息非法" << endl;
return;
}
//紧接着输入顶点的信息,图的第二部分信息
for (int i = 0;i < G.vexnum;i++)
{
cin >> G.vexs[i];
}
//将图的边初始化,权值全部置为0
for(int i=0;i<Mvnum*(Mvnum-1)/2;i++)
G.arcs[i]=0;
//输入权值
for (int i = 0;i < G.arcnum;i++)
{
//输入v1,v2作为边(v1,v2)的顶点以及边之间的权值w
//编号从0开始
int v1, v2, w;
//此处省略了查找v1,v2编号的过程
cin >> v1 >> v2 >> w;
//调整v1与v2
if(v2<v1)
{
int t=v2;
v2=v1;
v1=t;
}
//时刻关注合法性
if (v1 == v2 || v2 >= G.vexnum
|| w > Maxw||v1<0)
{
i--;
continue;
}
if (G.arcs[v1][v2] != 0)
{
i--;
continue;
}
//输入边的权值
G.arcs[v1][v2] = w;
}
//创建完毕
}
算法分析
优点：相对于邻接矩阵而言，提升了空间的利用率，同时也继承了邻接矩阵的所有优点。
缺点：几乎继承邻接矩阵的所有缺点，因为无论如何改进，空间复杂度依旧为O(N^2).
标签：vexnum,存储,arcs,创建,v1,v2,顶点,结构 From： https://www.cnblogs.com/writing-home/p/17092812.html