图的存储

1 邻接矩阵

1. $A[i][j]=1$ 表示顶点i与顶点j邻接，即i与j之间存在边或者弧。

2. $A[i][j]=0$ 表示顶点i与顶点j不邻接。 （0≤i，j≤n-1)

图1 图的邻接矩阵存储
a)无权图 b)有权图

1.1 邻接矩阵存储结构定义

#define MaxVertexNum 100  //顶点数目的最大值
typedef char VertexType;	//顶点的数据类型
typedef int EdgeType;	//带权图中边上权值的数据类型
typedef struct{VertexType Vex[MaxVertexNum];	//顶点表，用来存储顶点EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表，用来存储边int vexnum, arcnum;	//图的当前顶点数和弧数
}MGraph;

注意邻接矩阵表示法的空间复杂度为$O(n^2)$，其中n为图的顶点数$|V|$。

1.2 完整代码应用

以下图作为输入例子：

图2 无向图及其邻接矩阵

C++代码实现：

#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; //顶点数，边数
}AMGraph;int locatevex(AMGraph G,VexType x){for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标if(x==G.Vex[i])return i;return -1;//没找到
}void CreateAMGraph(AMGraph &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，如果是有向图，则把'G.Edge[j][i]=1'去掉即可else{cout << "输入顶点信息错！请重新输入！"<<endl;G.edgenum++;//本次输入不算}}
}void print(AMGraph 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(){AMGraph G;CreateAMGraph(G);print(G);return 0;
}

输出结果

图3 样例输出结果

2 邻接表

图4 邻接表存储结构示例

图5 绿色部分相当于顶点表

图6 每一种颜色相当于一个边表

2.1 邻接表存储结构定义

#define MaxVertexNum 100  //顶点数目的最大值
typedef struct ArcNode{		//边表结点int adjvex;	 	//该弧所指向的顶点的位置struct ArcNode *next;	//指向下一条弧的指针
}ArcNode;
typedef struct VNode{	//顶点表结点VertexType data;	//顶点信息  ArcNode *first;  //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct{AdjList vertices;	//邻接表int vexnum, arcnum;	//图的顶点数和弧数
}ALGraph;	//ALGraph是以邻接表存储的图类型

2.2 完整代码应用

以下图作为输入样例：

图7 邻接表输入样例

#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; //顶点数，边数
}ALGraph;int locatevex(ALGraph G,VexType x){for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标if(x==G.Vex[i].data)return i;return -1;//没找到
}void insertedge(ALGraph &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(ALGraph G){//输出邻接表cout<<"----------邻接表如下：----------"<<endl;for(int i=0;i<G.vexnum;i++){AdjNode *t=G.Vex[i].first;cout<<G.Vex[i].data<<"：  ";while(t!=NULL){cout<<"["<<t->v<<"]\t";t=t->next;}cout<<endl;}
}void CreateALGraph(ALGraph &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(){ALGraph G;CreateALGraph(G);//创建有向图邻接表printg(G);//输出邻接表return 0;
}

输出结果：

图8 样例输出结果(注:邻接表不唯一，因为插入结点顺序可以不同)