路径规划系列文章目录
- 路径规划算法综述
- 图论基础介绍
目录
路径规划系列文章目录
一、图的存储方式介绍
二、邻接矩阵介绍
三、邻接矩阵实现
四、总结
一、图的存储方式介绍
图的结构比较复杂,是非线性结构,任意两点都可能存在联系,相对来说存储方法较多。目前主要有:
- 邻接矩阵表示法
- 邻接表表示法
- 邻接多重表表示法
- 十字链表表示法
无论上述哪种存储方式,我们都要存储顶点和边的信息,在本系列文章中,我们介绍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 ArcNum;//边数量
GraphKind gKind; //图类型
cellType** AdjMatrix;//邻接矩阵
public:
GraphAdjMatrix();
void createGraph();//构建图
void GraphSet(int VerNum,int ArcNum,int kind);//图属性设置
int getVerNum() {return VerNum;}
int getArcNum() {return ArcNum;}
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;
ArcNum = 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,便于判定两个顶点之间是否有边(弧)相连; 计算顶点的度数,或有向图的入度、出度方便; 计算图的边数算法简单等。文章来源:https://www.toymoban.com/news/detail-456158.html
图的邻接矩阵表示的缺点: 邻接矩阵事实上是一种顺序存储结构,具有顺序结构共有的缺点,比如:只能按最大空间需求申请内存空间、插入和删除顶点复杂等; 空间复杂度高,n个顶点的图,存储邻接矩阵需要n2个单元,如果一个图的顶点数较多,但边(弧)数较少的话--稀疏图,邻接矩阵一样需要n2个存储单元,就太浪费存储空间; 统计图的边数算法虽然简单,用双重循环统计“1”的个数即可,但其时间复杂度为O(n2)。文章来源地址https://www.toymoban.com/news/detail-456158.html
到了这里,关于图论之邻接矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!