图论——邻接矩阵之无向网

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

在此之前,我们需要先理清图和网的区别

  1. 1.图G:有两个集合,边集V和点集E【点集用来存放各个顶点,边集用来存放各条边来表示关联两点的联系】
  2. 2.权值:即即两顶点之间互相往来需要花费的代价或消耗
  3. 3.网:带权值的图

所谓邻接矩阵,即用矩阵排布的方式来构建两点之间的关系

  • 1.针对图,邻接矩阵采用[0-1]排布【即两点之间有边就写1代表能通过,没有边就写0代表无法通过】图论——邻接矩阵之无向网图论——邻接矩阵之无向网
  •  另外,在这里我们对图的邻接矩阵进行讨论的时候,是默认点到自身也是没有边的
  • 针对网,邻接矩阵采用[权值-∞]分布【即两点之间有边就写边上所带的权值代表距离损耗,没有边就写∞代表无法到达】图论——邻接矩阵之无向网
  •  另外,会了方便,我们对于网的邻接矩阵中自身到自身的损耗也写成∞而非0

好了,概念说完了,我们接下来进行代码理解

因为网包含了图且附加了权值比较全面,所以我们拿无向网来作为例子

无向网的邻接矩阵存储定义:

const int mvnum = 100;//最大顶点个数 
#define MaxInt 36767//代表无穷 
typedef int vexType;//顶点数据类型 
typedef int edgeType;//边的数据类型 
//邻接矩阵 
typedef struct Graph{
	vexType vertex[mvnum];//点集 
	edgeType edge[mvnum][mvnum];//边集 
	int vexnum,edgenum;//顶点个数,边的个数 
}Graph;

针对无向网,我们来声明几个基本操作,例如创建无向网和遍历无向网

void CreateGraph(Graph &G);//创建无向网 
int LocateVex(Graph &G,int v);//顶点的定位 
void Traverse(Graph &G); //网的遍历 

代码实现:文章来源地址https://www.toymoban.com/news/detail-451872.html

#include <iostream>
using namespace std;

const int mvnum = 100;//最大顶点个数 
#define MaxInt 36767//代表无穷 
typedef int vexType;//顶点数据类型 
typedef int edgeType;//边的数据类型 
//邻接矩阵 
typedef struct Graph{
	vexType vertex[mvnum];//点集 
	edgeType edge[mvnum][mvnum];//边集 
	int vexnum,edgenum;//顶点个数,边的个数 
}Graph;

void CreateGraph(Graph &G);//创建无向网 
int LocateVex(Graph &G,int v);//顶点的定位 
void Traverse(Graph &G); //网的遍历 

void CreateGraph(Graph &G){
	cout<<"顶点个数:";
	cin>>G.vexnum;
	cout<<"边数:";
	cin>>G.edgenum; //确定该网的顶点个数与边数
	cout<<"点集:";
	for(int i=0;i<G.vexnum;++i){
		cin>>G.vertex[i]; //对顶点进行赋值 
	} 
	for(int i=0;i<G.vexnum;++i){
		for(int j=0;j<G.vexnum;++j){
			G.edge[i][j]=MaxInt;//因为是网,所以先提前把每两个顶点之间的边的权值设为无穷大 
		}
	}
	cout<<"构建无向网"<<endl; 
	for(int k=0;k<G.edgenum;++k){
		vexType v1,v2;
		edgeType w;
		cin>>v1>>v2>>w;//输入想要添加的边的权值以及边所依附的两顶点 
		int i=LocateVex(G,v1),j=LocateVex(G,v2);//确定两顶点在图中的位置
		G.edge[i][j]=w;
		G.edge[j][i]=G.edge[i][j];//由于无向网具有对称性,因此可以对称赋值 
	}
}

int LocateVex(Graph &G,int v){
	for(int i=0;i<G.vexnum;++i){
		if(v==G.vertex[i])	return i;
	} 
	return -1;
}

void Traverse(Graph &G){
	for(int i=0;i<G.vexnum;++i)
		for(int j=0;j<G.vexnum;++j)
			if(G.edge[i][j]!=MaxInt)
				cout<<"("<<G.vertex[i]<<" "<<G.vertex[j]<<") 权值:"<<G.edge[i][j]<<endl;
}

int main(){
	Graph g;
	CreateGraph(g);
	Traverse(g);
	return 0 ;
}

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

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

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

相关文章

  • C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

    关键点: 1.构建二维数组 2.对应边的位置赋值为1 由于比较简单就直接上代码: 个人对邻接表实现无向图的理解如下,仅供参考:         由于无向图的组成是由多个顶点和多条无向边组成的,因此我们可以把它拆分成两个结构,分别是顶点和无向边,又由于我们是使用

    2024年02月05日
    浏览(55)
  • C++构造无向图,邻接矩阵,深度优先遍历,广度优先遍历

    目录 定义无向图邻接矩阵 构造无向图 打印邻接矩阵 无向图邻接矩阵深度优先遍历(DFS) 无向图邻接矩阵广度优先遍历(BFS) 测试  完整代码 定义无向图邻接矩阵 构造无向图 1、输入总顶点数和总边数 2、依次输入顶点信息存入顶点表 3、 初始化邻接矩阵,使每个权值初始化

    2024年02月06日
    浏览(83)
  • 带权无向图的邻接矩阵表示法(C语言实现)

    ​ 定义:所谓邻接矩阵存储,是指用一个一维数组存储图中顶点的信息,用一个二维数组存储图中边的信息(即各顶点之间的邻接关系),存储顶点之间邻接关系的二维数组称为邻接矩阵。 ​ 对于 带权图 而言,若顶点V i 和 V j 之间有边相连,则邻接矩阵中对应项存放着该

    2024年02月16日
    浏览(39)
  • 对无向图进行邻接矩阵的转化,并且利用DFS(深度优先)和BFS(广度优先)算法进行遍历输出, 在邻接矩阵存储结构上,完成最小生成树的操作。

    目录 一 实验目的 二 实验内容及要求 实验内容: 实验要求: 三 实验过程及运行结果 一 算法设计思路 二 源程序代码 三、截图 四 调试情况、设计技巧及体会 1.掌握图的相关概念。 2.掌握用邻接矩阵和邻接表的方法描述图的存储结构。 3.掌握图的深度优先搜索和广度优

    2024年02月04日
    浏览(57)
  • 图论基础: 邻接矩阵与邻接表(c++实现)

    邻接矩阵(Adjacency Matrix)是表示 顶点之间相邻关系 的矩阵。 设G=(顶点,边):G=(V,E)是一个图。其中V={v1,v2,…,vn} [1] 。G的邻接矩阵是一个具有下列性质的n阶方阵: 无向图的邻接矩阵一定是成对角线对称的,是一个 对称矩阵 ,有向图 不一定 是对称的。 有向图当把它的 行

    2024年02月05日
    浏览(44)
  • 图论之邻接矩阵

    路径规划算法综述 图论基础介绍 目录 路径规划系列文章目录 一、图的存储方式介绍 二、邻接矩阵介绍 三、邻接矩阵实现 四、总结          图的结构比较复杂,是非线性结构,任意两点都可能存在联系,相对来说存储方法较多。目前主要有: 邻接矩阵表示法 邻接表表

    2024年02月06日
    浏览(35)
  • 第五章 图论 邻接矩阵存图

    dfs bfs

    2024年01月19日
    浏览(43)
  • 数据结构几种常见图的邻接矩阵的画法(有向图带权值,有向图不带权值,无向图带权值,无向图不带权值)

    这不马上要期末考试了,复习的时候突然发现了有好几种图的邻接矩阵需要画,在网上找了半天结果发现也没有特别详细的总结,所以经过总结写一下吧,希望对有需要的人,有点帮助吧!!!!(如有不对还请见谅!!!!!~~~~~~) 1,有向图带权值   2.有向图不带权值

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

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

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

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

    2024年02月05日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包