图论之邻接矩阵

大家好，欢迎来到IT知识分享网。

路径规划系列文章目录

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

目录

路径规划系列文章目录

一、图的存储方式介绍

二、邻接矩阵介绍

三、邻接矩阵实现

四、总结

一、图的存储方式介绍

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

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

        无论上述哪种存储方式，我们都要存储顶点和边的信息，在本系列文章中，我们介绍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，便于判定两个顶点之间是否有边（弧）相连； 计算顶点的度数，或有向图的入度、出度方便； 计算图的边数算法简单等。

        图的邻接矩阵表示的缺点： 邻接矩阵事实上是一种顺序存储结构，具有顺序结构共有的缺点，比如：只能按最大空间需求申请内存空间、插入和删除顶点复杂等； 空间复杂度高，n个顶点的图，存储邻接矩阵需要n2个单元，如果一个图的顶点数较多，但边（弧）数较少的话–稀疏图，邻接矩阵一样需要n2个存储单元，就太浪费存储空间； 统计图的边数算法虽然简单，用双重循环统计“1”的个数即可，但其时间复杂度为O(n2)。