路径规划系列文章目录
目录
路径规划系列文章目录
一、图的存储方式介绍
二、邻接矩阵介绍
三、邻接矩阵实现
四、总结
一、图的存储方式介绍
图的结构比较复杂，是非线性结构，任意两点都可能存在联系，相对来说存储方法较多。目前主要有：
- 邻接矩阵表示法
- 邻接表表示法
- 邻接多重表表示法
- 十字链表表示法
无论上述哪种存储方式，我们都要存储顶点和边的信息，在本系列文章中，我们介绍1,2两种表示法。
二、邻接矩阵介绍
邻接矩阵就是利用二维矩阵表示图中各顶点之间的关系，对于有n个顶点的图来说，用n阶方阵来表示该图，其中矩阵元素表示从顶点到之间的边，的大小表示边的权值。如果顶点到没有边，则可以将设置为0或者。
如下图所示，左边是一个无向图，右边是其对应的邻接矩阵，该图是无权图，因此有边的值都设置为1。
下面是有向图及其邻接矩阵
从上面可见，无向图的邻接矩阵是关于主轴对称的，第i行或第j列就是顶点的度（边数）。图中的边数为"1的个数"/2。对于有向图，由于其具有方向性，因此邻接矩阵一般是不对称的，第i行1的个数是顶点的出度，第i列1的个数是其入度。图的边数等于矩阵中1的个数。
对于带权图来说，只需要将1替换为边的权值即可，下面是带权图及其邻接矩阵。
其中，表示没有边，可以是一个计算机能够接受的较大的值即可。
三、邻接矩阵实现
#include<iostream>
using namespace std;
#define INF 65535 //表示无穷大，其他合理的值也可
#define MaxVerNum 1000 //定义顶点最大数量
typedef int cellType; //定义邻接矩阵元素数据类型，即权值的数据类型
//定义图的类型分别为无向图，无向带权图，有向图，有向带权图
typedef enum{
UDG,UDN,DG,DN
}GraphKind;
class GraphAdjMatrix
{
private:
int VerNum;//顶点数量
int Ar***um;//边数量
GraphKind gKind; //图类型
cellType** AdjMatrix;//邻接矩阵
public:
GraphAdjMatrix();
void createGraph();//构建图
void GraphSet(int VerNum,int Ar***um,int kind);//图属性设置
int getVerNum() {return VerNum;}
int getAr***um() {return Ar***um;}
GraphKind geyGraphKind() {return gKind;};
void setMatrix(int i,int j,int w) ; //邻接矩阵设置
void printMatrix();//打印邻接矩阵
};
GraphAdjMatrix::GraphAdjMatrix()//构造函数
{
AdjMatrix = new cellType*[MaxVerNum];
for(int i=0;i<MaxVerNum;i++)// 为邻接矩阵分配内存
AdjMatrix[i] = new cellType[MaxVerNum];
}
void GraphAdjMatrix::setMatrix(int i,int j,int w)
{
AdjMatrix[i][j]=w;
if(gKind==UDG||gKind==UDN) //如果是无向图，则设置对称位置权重
AdjMatrix[j][i]=w;
};
void GraphAdjMatrix::createGraph()
{
int vn,an,k;//分别代表顶点数量，边数量，以及图类型
cout<<"输入顶点数量,边数量，图类型用空格隔开"<<endl;
cout<<"0-无向无权图 1-无向带权图 2-有向无权图 3-有向带权图"<<endl;
cin>>vn>>an>>k;
VerNum = vn;
Ar***um = an;
gKind = (GraphKind)k;
int i,j,w;
//初始化邻接矩阵
for(int i=1;i<=vn;i++)
{
for(int j=1;j<=vn;j++)
{
AdjMatrix[i][j]=INF;
}
}
/*无向图，无向带权图，有向图，有向带权图 */
GraphKind gk;
while(an--)
{
if (k == UDG || k == DG)//如果是无权图，则将边权重设为1
{
cin>>i>>j;
AdjMatrix[i][j]=1;
if (k==UDG)//如果是无向图，对称位置设置权重
AdjMatrix[j][i]=1;
}
else
{
cin>>i>>j>>w;
AdjMatrix[i][j]=w;
if (k == UDN)//如果是无向图，对称位置设置权重
AdjMatrix[j][i]=w;
}
}
}
void GraphAdjMatrix::printMatrix()
{
for(int i=1;i<=VerNum;i++)
{
for(int j=1;j<=VerNum;j++)
{
if (AdjMatrix[i][j]==INF)
cout<<"*"<<"\t";
else
cout<<AdjMatrix[i][j]<<"\t";
}
cout<<endl;
}
}
int main()
{
GraphAdjMatrix cg;
cg.createGraph();
cg.printMatrix();
return 0;
}
四、总结
图的邻接矩阵表示的优点： 非常直观，并且容易实现，编写算法也较简便，因而应用较广； 根据矩阵元素Aij=1或0，便于判定两个顶点之间是否有边（弧）相连； 计算顶点的度数，或有向图的入度、出度方便； 计算图的边数算法简单等。
图的邻接矩阵表示的缺点： 邻接矩阵事实上是一种顺序存储结构，具有顺序结构共有的缺点，比如：只能按最大空间需求申请内存空间、插入和删除顶点复杂等； 空间复杂度高，n个顶点的图，存储邻接矩阵需要n2个单元，如果一个图的顶点数较多，但边（弧）数较少的话--稀疏图，邻接矩阵一样需要n2个存储单元，就太浪费存储空间； 统计图的边数算法虽然简单，用双重循环统计“1”的个数即可，但其时间复杂度为O(n2)。
