数据结构:邻接矩阵-创新互联

创建邻接矩阵,其实在离散数学中我们已经学过了,这里只是把它边的代码化了;这里就以下面这个简简单单的图为例子来讲怎么创建一个邻接矩阵吧。

公司主营业务:成都网站设计、网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。创新互联建站是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联建站推出夏津免费做网站回馈大家。

这里分有向图和无向图来讨论

1.无向图和无向图的邻接矩阵

由于无向图和无向图的边都是没有权值的,所以我们用1表示某两顶点之间有边存在,用0表示这两边是没有边存在的。

首先,我们看G2,他有4个顶点,所以,我们用一个(n*n)5*5的数组来存这个图,也就是说,我们要建一个这么大的邻接矩阵;

行就分别表示v1 v2 v3 v4;

列也是v1 v2 v3 v4;

我们需要了解的一点就是!v(i,j)表示vi到vj之间是否有边;

  • 先看v1这个顶点,他和v2   v4相连;                                                                                           看第一行(也就是v1这一行),找到v2和v4下面都写上1;
  • 再看v2这个顶点,他和v1    v3    v5相连;                                                                                 看第二行(也就是v2这一行),找到v1和v3、v5下面都写上1;
  • 再看v3这个顶点,他和v2   v4   v5相连;                                                                                     我们看第三行(也就是v3这一行),找到v2和v4、v5下面都写上1;
  • 看v4这个顶点,他和v1   v3相连;                                                                                                看第四行(也就是v4这一行),找到v1和v3下面都写上1;
  • 看v5这个顶点,他和v2   v3相连;                                                                                                 看第五行(也就是v5这一行),找到v2和v3下面都写上1;

然后我们再看G1,就是同理,因为G1是一个有向图,也就是同理,只不过有向图他两点之间是用箭头链接,这样我们只要看,谁指向谁,就说明这两个之间是联通的。

v就表示i到j之间是否为通的。

这里的G1,4个顶点,聪明的你一个会举一反三了吧,哈哈哈哈,就是和上面那个一样的,答案已经在上面给出了奥,

下面我们就看代码吧:

#include#include#include#include#define MVNum 100;
typedef VerTexType char;
using namespace std;
//邻接矩阵(数组/顺序存储)
typedef struct {
	VerTexType vexs[MVNum];//顶点表
	Arctype arcs[MVNum][MVNum];//邻接表,,记得初始化为0奥,我这里没有写了
	int vexnum,arcnum;//分别表示顶点数和边的数量
}AMGraph;

int Locate(AmGraph G,VerTexType u){
	for(int i=0;i>G.vexnum>>G.arcnum;
	for(int i=0;i>G.vexs[i];
	for(int i=0;i>v1>>v2;
		i=Locate(G,v1);
		j=Locate(G,v2);
		G.arcs[i][j]=1;
		G.arcs[i][j]=G.arcs[j][i];
	}
	return 1;
}
2.网的邻接矩阵

接下来是网的邻接矩阵了,这里注意就是,链接两点的边如果有权值我们就把他叫做网,这时候,邻接矩阵中对应得v[i][j]就不是表示存不存在边了,而是写他这一条边的权值:

在这里插入图片描述

方法还是和上面的一样,只不过这里把没有边改成了无穷大;方便我们做后面的算法;

下面我们就看看代码把

#include#include#include#include#define MVNum 100;
typedef VerTexType char;
using namespace std;
//邻接矩阵(数组/顺序存储)
typedef struct {
	VerTexType vexs[MVNum];//顶点表
	Arctype arcs[MVNum][MVNum];//邻接表
	int vexnum,arcnum;//分别表示顶点数和边的数量
}AMGraph;

int Locate(AmGraph G,VerTexType u){
	for(int i=0;i>G.vexnum>>G.arcnum;
	for(int i=0;i>G.vexs[i];
	for(int i=0;i>v1>>v2>>w;
		i=Locate(G,v1);
		j=Locate(G,v2);
		G.arcs[i][j]=w;
		G.arcs[i][j]=G.arcs[j][i];
	}
	return 1;
}

嗯............那我们就总结一下这个邻接矩阵得优点和去缺点吧

一、优点:
1. 直观,简单,好理解
2.方便查找某两边之间是否存在边
3.方便寻找某一顶点直接相邻的点
4.方便计算各个顶点的入度和出度
二、缺点:
1.不利于增加和删除顶点;
2.浪费空间——特别在稀疏图中
3.浪费时间——比如统计图中边的数目

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网页名称:数据结构:邻接矩阵-创新互联
网站网址:http://scyanting.com/article/digcjs.html