图的存储方式
图的存储
一.邻接矩阵
邻接矩阵是表示顶点之间关系的矩阵。邻接矩阵存储方法，需要用一个一维数组存储图中顶点的信息，用一个二维数组存储图中顶点之间的邻接关系，存储顶点之间邻接关系的二维数组称为邻接矩阵。
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
总结
以上几种在竞赛中较为常用,另外除了上面三种还有十字链表,边集表示法,邻接双层表表示,较为复杂,此处不再进行介绍.
