图论之邻接矩阵

路径规划系列文章目录

1. 路径规划算法综述
2. 图论基础介绍

目录

路径规划系列文章目录

一、图的存储方式介绍

二、邻接矩阵介绍

三、邻接矩阵实现

四、总结

一、图的存储方式介绍

         图的结构比较复杂，是非线性结构，任意两点都可能存在联系，相对来说存储方法较多。目前主要有：

1. 邻接矩阵表示法
2. 邻接表表示法
3. 邻接多重表表示法
4. 十字链表表示法

        无论上述哪种存储方式，我们都要存储顶点和边的信息，在本系列文章中，我们介绍1,2两种表示法。

二、邻接矩阵介绍

        邻接矩阵就是利用二维矩阵表示图中各顶点之间的关系，对于有n个顶点的图来说，用n阶方阵来表示该图，其中矩阵元素表示从顶点到之间的边，的大小表示边的权值。如果顶点到没有边，则可以将设置为0或者。

        如下图所示，左边是一个无向图，右边是其对应的邻接矩阵，该图是无权图，因此有边的值都设置为1。

        下面是有向图及其邻接矩阵

         从上面可见，无向图的邻接矩阵是关于主轴对称的，第i行或第j列就是顶点的度（边数）。图中的边数为"1的个数"/2。对于有向图，由于其具有方向性，因此邻接矩阵一般是不对称的，第i行1的个数是顶点的出度，第i列1的个数是其入度。图的边数等于矩阵中1的个数。

对于带权图来说，只需要将1替换为边的权值即可，下面是带权图及其邻接矩阵。

        其中，表示没有边，可以是一个计算机能够接受的较大的值即可。

三、邻接矩阵实现

#include
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>i>>j>>w;
			AdjMatrix[i][j]=w;
			if (k == UDN)//如果是无向图，对称位置设置权重 
				AdjMatrix[j][i]=w;
		}
	}
}
void GraphAdjMatrix::printMatrix()
{
	for(int i=1;i