图的存储
一.邻接矩阵
邻接矩阵是表示顶点之间关系的矩阵。邻接矩阵存储方法，需要用一个一维数组存储图中顶点的信息，用一个二维数组存储图中顶点之间的邻接关系，存储顶点之间邻接关系的二维数组称为邻接矩阵。
1.1邻接矩阵的表示方法
（1）无向图的邻接矩阵在无向图中，如果vi到vj有边，则邻接矩阵M[i][j]=M [j][i]=1，否则M [i][j]=0。
无向图邻接矩阵的特点如下。
1）无向图的邻接矩阵是对称矩阵，并且是唯一的。
2）第i行或第i列非零元素的个数正好是第i个顶点的度。
（2）有向图的邻接矩阵有向图中，如果vi到vj有边，则邻接矩阵M[i][j]=1，否则M[i][j]=0。
注意：尖括号<vi, vj>表示有序对，圆括号(vi, vj)表示无序对。
有向图邻接矩阵的特点如下。
1）有向图的邻接矩阵不一定是对称的。
2）第i行非零元素的个数正好是第i个顶点的出度，第i列非零元素的个数正好是第i个顶点的入度。
（3）网的邻接矩阵
网是带权图，需要存储边的权值，则邻接矩阵表示为：
其中，wij表示边上的权值，∞表示无穷大。尖括号<vi, vj>表示有序对，圆括号(vi,vj)表示无序对。当i=j时，wii也可以设置为0。
1.2代码实现
//邻接矩阵创建无向图 #include <iostream> using namespace std; #define MaxVnum 100 //顶点数最大值 typedef char VexType; //顶点的数据类型，根据需要定义 typedef int EdgeType; //边上权值的数据类型，若不带权值的图，则为0或1 typedef struct{ VexType Vex[MaxVnum]; EdgeType Edge[MaxVnum][MaxVnum]; int vexnum,edgenum; //顶点数，边数 }AMGragh; int locatevex(AMGragh G,VexType x) { for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标 if(x==G.Vex[i]) return i; return -1;//没找到 } void CreateAMGraph(AMGragh &G) { int i,j; VexType u,v; cout << "请输入顶点数："<<endl; cin>>G.vexnum; cout << "请输入边数:"<<endl; cin>>G.edgenum; cout << "请输入顶点信息:"<<endl; for(int i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组 cin>>G.Vex[i]; for(int i=0;i<G.vexnum;i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大 for(int j=0;j<G.vexnum;j++) G.Edge[i][j]=0; cout << "请输入每条边依附的两个顶点："<<endl; while(G.edgenum--) { cin>>u>>v; i=locatevex(G,u);//查找顶点u的存储下标 j=locatevex(G,v);//查找顶点v的存储下标 if(i!=-1&&j!=-1) G.Edge[i][j]=G.Edge[j][i]=1; //邻接矩阵储置1 else { cout << "输入顶点信息错！请重新输入！"<<endl; G.edgenum++;//本次输入不算 } } } void print(AMGragh G)//输出邻接矩阵 { cout<<"图的邻接矩阵为："<<endl; for(int i=0;i<G.vexnum;i++) { for(int j=0;j<G.vexnum;j++) cout<<G.Edge[i][j]<<"\t"; cout<<endl; } } int main() { AMGragh G; CreateAMGraph(G); print(G); return 0; }
1.3邻接矩阵的优缺点
优点·
快速判断两顶点之间是否有边。在图中，Edge[i][j]=1表示有边，Edge[i][j]=0表示无边；在网中，Edge[i][j]=∞表示无边，否则表示有边。时间复杂度为O(1)。·
方便计算各顶点的度。在无向图中，邻接矩阵第i行元素之和就是顶点i的度；在有向图中，第i行元素之和就是顶点i的出度，第i列元素之和就是顶点i的入度。时间复杂度为O(n)。
缺点
不便于增删顶点。增删顶点时，需要改变邻接矩阵的大小，效率较低。·
不便于访问所有邻接点。访问第i个顶点的所有邻接点，需要访问第i行的所有元素，时间复杂度为O(n)。访问所有顶点的邻接点，时间复杂度为O(n^2)。
空间复杂度高。空间复杂度为O(n^2)。
二.邻接表
邻接表（Adjacency List）是图的一种链式存储方法。邻接表包含两部分：顶点和邻接点。顶点包括顶点信息和指向第一个邻接点的指针。邻接点包括邻接点的存储下标和指向下一个邻接点的指针。顶点vi的所有邻接点构成一个单链表。
2.1邻接表的表示方法
（1）无向图的邻接表
无向图邻接表的特点如下。
1）如果无向图有n个顶点、e条边，则顶点表有n个节点，邻接点表有2e个节点。
2）顶点的度为该顶点后面单链表中的节点数。
（2）有向图的邻接表（出边）
有向图邻接表的特点如下。
1）如果有向图有n个顶点、e条边，则顶点表有n个节点，邻接点表有e个节点。2）顶点的出度为该顶点后面单链表中的节点数。
（3）有向图的逆邻接表（入边）
有时为了方便得到顶点的入度，可以建立一个有向图的逆邻接表.
有向图逆邻接表的特点如下。
1）如果有向图有n个顶点、e条边，则顶点表有n个节点，邻接点表有e个节点。2）顶点的入度为该顶点后面单链表中的节点数。
2.2 代码实现
//创建有向图的邻接表 #include <iostream> using namespace std; const int MaxVnum=100;//顶点数最大值 typedef char VexType;//顶点的数据类型为字符型 typedef struct AdjNode{ //定义邻接点类型 int v; //邻接点下标 struct AdjNode *next; //指向下一个邻接点 }AdjNode; typedef struct VexNode{ //定义顶点类型 VexType data; // VexType为顶点的数据类型，根据需要定义 AdjNode *first; //指向第一个邻接点 }VexNode; typedef struct{//定义邻接表类型 VexNode Vex[MaxVnum]; int vexnum,edgenum; //顶点数，边数 }ALGragh; int locatevex(ALGragh G,VexType x) { for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标 if(x==G.Vex[i].data) return i; return -1;//没找到 } void insertedge(ALGragh &G,int i,int j)//插入一条边 { AdjNode *s; s=new AdjNode; s->v=j; s->next=G.Vex[i].first; G.Vex[i].first=s; } void printg(ALGragh G)//输出邻接表 { cout<<"----------邻接表如下：----------"<<endl; for(int i=0;i<G.vexnum;i++) { AdjNode *t=G.Vex[i].first; cout<<cout<<G.Vex[i].data<<"： "; while(t!=NULL) { cout<<"["<<t->v<<"] "; t=t->next; } cout<<endl; } } void CreateALGraph(ALGragh &G)//创建有向图邻接表 { int i,j; VexType u,v; cout<<"请输入顶点数和边数:"<<endl; cin>>G.vexnum>>G.edgenum; cout << "请输入顶点信息:"<<endl; for(i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组 cin>>G.Vex[i].data; for(i=0;i<G.vexnum;i++) G.Vex[i].first=NULL; cout<<"请依次输入每条边的两个顶点u,v"<<endl; while(G.edgenum--) { cin>>u>>v; i=locatevex(G,u);//查找顶点u的存储下标 j=locatevex(G,v);//查找顶点v的存储下标 if(i!=-1&&j!=-1) insertedge(G,i,j); else { cout << "输入顶点信息错！请重新输入！"<<endl; G.edgenum++;//本次输入不算 } } } int main() { ALGragh G; CreateALGraph(G);//创建有向图邻接表 printg(G);//输出邻接表 return 0; }
运行结果
2.3邻接表的优缺点
优点
便于增删顶点。
便于访问所有邻接点。访问所有顶点的邻接点，时间复杂度为O(n+e)。
空间复杂度低。顶点表占用n个空间，无向图的邻接点表占用n+2e个空间，有向图的邻接点表占用n+e个空间，总体空间复杂度为O(n+e)，而邻接矩阵的空间复杂度为O(n^2)，因此对于稀疏图可采用邻接表存储，对于稠密图可以采用邻接矩阵存储。
缺点
不便于判断两顶点之间是否有边。要判断两顶点是否有边，需要遍历该顶点后面的邻接点链表。
不便于计算各顶点的度。在无向图邻接表中，顶点的度为该顶点后面单链表中的节点数；在有向图邻接表中，顶点的出度为该顶点后面单链表中的节点数，但求入度困难；在有向图逆邻接表中，顶点的入度为该顶点后面单链表中的节点数，但求出度困难。
虽然邻接表访问单个邻接点的效率不高，但是访问一个顶点的所有邻接点，仅需要访问该顶点后面的单链表即可，时间复杂度为该顶点的度O(d(vi))，而邻接矩阵访问一个顶点的所有邻接点，时间复杂度为O(n)。总体上邻接表比邻接矩阵效率更高。
三.链式双向星
图的存储方法很多，最常见的除了邻接矩阵、邻接表和边集数组外，还有链式前向星。.链式前向星是一种静态链表存储，用边集数组和邻接表相结合，可以快速访问一个顶点的所有邻接点，在算法竞赛中广泛应用。。
链式前向星存储包括两种结构:。
边集数组: edge[ ]，edge[i]表示第 i条边;。
头结点数组: head[], head[i]存以 i为起点的第一条边的 下标(在edge[]中的下标)。
举例如下:
代码实现
#include<iostream> #include<string.h> using namespace std; const int maxn = 505, maxe = 100001;//maxn:最大头结点数.maxe:最大边数 int n, m, cnt;//cnt:边下标 n:节点数. m:边数 int head[maxn];//头结点数组 struct node { int to, next, w;// to:另个结点 next:后结点所在edge数组的索引 } edge[maxe]; //边集数组 void add(int u, int v, int w) { //添加一条边 edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void printg() { //输出表 for (int u = 1; u <= n; u++) { cout << u << " "; for (int i = head[u]; i != -1; i = edge[i].next) { cout << "---" << i << ":(" << edge[i].to << " " << edge[i].w << " " << edge[i].next << ")"; } cout << endl; } } int main() { cin >> n >> m; cnt = 0; memset(head, -1, sizeof(head)); int u, v, w; for (int i = 1; i <= m; i++) { // cin >> u >> v >> w; add(u, v, w); add(v, u, w); } printg(); return 0; } //4 5 //1 2 5 //1 4 3 //2 3 8 //2 4 12 //3 4 9
总结
以上几种在竞赛中较为常用,另外除了上面三种还有十字链表,边集表示法,邻接双层表表示,较为复杂,此处不再进行介绍.
