图论之邻接矩阵

这篇具有很好参考价值的文章主要介绍了图论之邻接矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

路径规划系列文章目录

  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)。文章来源地址https://www.toymoban.com/news/detail-456158.html

到了这里,关于图论之邻接矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第五章 图论 邻接矩阵存图

    dfs bfs

    2024年01月19日
    浏览(43)
  • C++ 图论之求图的连通块数量(邻接矩阵版)

    1. 连通块的定义 块内每个点之间都有一条路径。 2. 思路 我们可以用dfs深度优先搜索:从一个点出发遍历图将遍历过的点全部标记,标记过的点则不会再遍历到。 再写一个循环枚举所有的点(枚举起点),如果没标记就代表可以作为起点,数量加一,进行dfs标记点。 3. 代码

    2024年02月13日
    浏览(54)
  • 【图论】Dijkstra 算法求最短路 - 构建邻接矩阵(带权无向图)

    题目链接:1976. 到达目的地的方案数

    2024年03月22日
    浏览(44)
  • Dijkstra算法——邻接矩阵实现+路径记录

    本文是在下面这篇文章的基础上做了一些补充,增加了路径记录的功能。具体Dijkstra的实现过程可以参考下面的这篇文章。 [jarvan:Dijkstra算法详解 通俗易懂](Dijkstra算法详解 通俗易懂 - jarvan的文章 - 知乎 https://zhuanlan.zhihu.com/p/338414118) 创建 GraphAdjMat 类 GraphAdjMat 类用来实现图的

    2024年01月18日
    浏览(42)
  • 【C++数据结构 | 图速通】10分钟掌握邻接矩阵 & 邻接表 | 快速掌握图论基础 | 快速上手抽象数据类型图

    by.Qin3Yu 请注意:严格来说,图不是一种数据结构,而是一种抽象数据类型。但为了保证知识点之间的相关性,也将其列入数据结构专栏。 本文需要读者掌握顺序表和单链表的操作基础,若需学习,可参阅我的往期文章: 【C++数据结构 | 顺序表速通】使用顺序表完成简单的成

    2024年02月05日
    浏览(45)
  • 图论之毕克定理证明

    毕克定理是小学四年级奥赛内容,无意间从一本教材上看到,觉得定理蛮有意思,也和自己从事的工作有一些关联,就在网上找了一些证明资料,结合自己的思考,稍微挖掘了以下,聊以记录。 毕克定理是指一个计算点阵中顶点在格点上的多边形面积公式,该公式可以表示为

    2024年02月15日
    浏览(52)
  • 图论之寻找桥边

    目录 ①基准法 ②并查集 ③逆向思维之标记环边 ④并查集压缩路径 主函数读取文件调函数方法处理 在图论中,一条边被称为“桥”代表这条边一旦被删除,这张图的连通块数量会增加。等价地说,一条边是一座桥当且仅当这条边不在任何环上。一张图可以有零或多座桥。

    2024年02月16日
    浏览(39)
  • C++图论之强连通图

    什么是连通性? 连通,字面而言,类似于自来水管道中的水流,如果水能从某一个地点畅通流到另一个地点,说明两点之间是连通的。也说明水管具有连通性,图中即如此。 无向图和有向图的连通概念稍有差异。 无向图连通性 如果任意两点间存在路径,称此图具有连通性

    2024年02月03日
    浏览(38)
  • 图论之dfs与bfs的练习

    dfs--深度优选搜索 bfs--广度优先搜索 迷宫问题--dfs 问题: 给定一个n*m的二维迷宫数组其中S是起点,T是终点,*是墙壁(无法通过), .是道路 问从起点S出发沿着上下左右四个方向走,能否走到T点?能输出\\\"YES\\\",否则输出\\\"NO\\\"。 8 8 *****... *.S...** *****.** *****..* *T..**.* .**.**.* ..*...

    2024年02月20日
    浏览(33)
  • [数学建模]图论之最短路径问题

    目录 一、引入图论  二、图的基本概念与数据结构 1.基本概念  2.图与网络结构 1.邻接矩阵表示法  2.稀疏矩阵表示法 三、最短路径问题 1、迪杰斯特拉(Dijkstra)算法 2、贝尔曼-福特(Bellman-Ford)算法 3、弗洛伊德(Floyd)算法         图论起源于18世纪,近几十年来,计

    2024年02月06日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包