数据结构与算法————无向图

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

1、图的定义及分类

图是由一组顶点和一组能够将两个顶点相连的边组成的

无向图,数据结构,算法设计与分析,数据结构

 一般使用数字0V-1来表示一张含有 V 个顶点的图中的各个顶点

2、图的相关术语

相邻顶点:

当两个顶点通过一条边相连时, 我们称这两个顶点是相邻的, 并称该连接依附于这两个顶点

度数:

某个顶点的度数即为依附于它的边的总数

无向图,数据结构,算法设计与分析,数据结构

3、无向图的表示方法

1.邻接矩阵

我们可以使用一个 V 乘 V 的二维矩阵。 当顶点 v 和顶点 w 之间有相连接的边时, 定义 v 行 w 列的元素值为1, 否则为0。

无向图,数据结构,算法设计与分析,数据结构

2.邻接表

 我们可以使用一个以顶点为索引的列表数组, 其中的每个元素都是和该顶点相邻的顶点列表

无向图,数据结构,算法设计与分析,数据结构

 4、图的邻接表存储表示

我们需要定义三种结构

首先,我们要定义 边节点的结构,比如图中v3-v0这一条边,它包含了两个信息:这条边所属的顶点   指向该顶点下一条边的指针

如图所示,3代表了它连接v0和v3顶点,后面的指针域代表下一条边

无向图,数据结构,算法设计与分析,数据结构

//边的结构
typedef struct ArcNode
{
	int adjvex;//这条边所属的顶点
	 ArcNode *nextarc;//指向该顶点下一条边的指针
}ArcNode; 

然后我们要定义表头节点,它包含了两个信息:顶点的信息,比如顶点的权值 指向该顶点的第一条边

无向图,数据结构,算法设计与分析,数据结构

typedef struct VexNode
{
	int data;//储存顶点的信息
	ArcNode* firstarc;//指向该顶点的第一条边
}VexNode,AdjList[Max];

注意理解Adjlist[Max]的含义,数组类型AdjList,它是由VexNode类型元素构成的,数组的长度为Max。Max表示图中顶点的个数。 

换句话说,AdjList[MVNum]是一个数组类型,包含了Max个元素,每个元素都是VexNode类型的结构体,我们把AdjList称为邻接表类型

最后我们再定义无向图,它包含了两个信息:①邻接表  ②图的顶点数量和边数量

//图的结构
typedef struct
{
	AdjList list;
	int vexnum;
	int arcnum;
}AlGraph;

 5、邻接表的构建

步骤:

①输入总顶点数,总边数
②输入各顶点的值
③输入各边所依附的两个顶点
④构建新的边节点(使用头插法)

bool CreateGraph(AlGraph& G)
{
	cout << "请输入总顶点数,边数" << endl;
	cin >> G.vexnum >> G.arcnum;
	cout << "请输入各顶点的值" << endl;
	//构建邻接表的顶点
	for (int i = 1; i <=G.vexnum; i++)
	{
		cin >> G.list[i].data;
		G.list[i].firstarc = NULL;
	}
	cout << "请输入各边所依附的顶点" << endl;
	int i,j;
	int v1, v2;
	//构建新的边节点
	for (int k = 0; k < G.arcnum; k++)
	{
		cin >> v1 >> v2;//v1,v2是一条边所对应的两个顶点
		//i,j表示顶点在邻接表中对应的下标
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		//因为是无向图,所以一条边可以依附于两个顶点,所以我们要新创建两个边节点
		ArcNode* p1 = new ArcNode();
		ArcNode* p2 = new ArcNode();
		//头插法将新结点*p1插入顶点vi的边表头部 
		p1->adjvex = j;//注意区分下标,如果是插入顶点vi,那么下标就是j,反之如果插入顶点vj,那么下标就是i
		p1->nextarc = G.list[i].firstarc;
		G.list[i].firstarc = p1;
		//头插法将新结点* p2插入顶点vj的边表头部
		p2->adjvex = i;
		p2->nextarc = G.list[j].firstarc;
		G.list[j].firstarc = p2;
	}
	return true;
}

无向图,数据结构,算法设计与分析,数据结构文章来源地址https://www.toymoban.com/news/detail-757704.html

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

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

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

相关文章

  • 《数据结构与算法分析》课程设计——迷宫问题

    中国矿业大学信控学院   补一下我之前在博客园发布的内容  懒得调了, 想复制完整代码直接复制最下面的 ,想复制分布代码去看我博客园链接吧 《数据结构与算法分析》课程设计——迷宫问题 - 刷子zz - 博客园 一、  问题描述 问题中迷宫可用方阵[m,n]表示,0表示能通过

    2024年02月10日
    浏览(52)
  • 算法分析与设计考前冲刺 (算法基础、数据结构与STL、递归和分治、 动态规划、贪心算法、 回溯算法)

    算法分析与设计考前冲刺 算法基础 算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。 程序是算法用某种程序设计语言的具体的 具体实现 算法特征: 有穷性(有限步) 确定性 输入 输出 可行性(有限时间) 算法的复杂性: 时间复杂性 和空间复

    2024年02月02日
    浏览(44)
  • C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

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

    2024年02月05日
    浏览(55)
  • 数据结构:有向完全图和无向完全图的边数

    一个拥有n个结点的无向完全图的边数为:n×(n−1)÷2 具体的解释: 比如我们有一个拥有4个结点的无向完全图, 我们首尾依次连接,共有4条边。 然后我们选择其他的两条边来连线。 又多出了2条边。一共有4 + 2 = 6条边。 我们来分析一下具体的过程,首先如果为n个结点的话,

    2024年02月11日
    浏览(41)
  • 【数据结构与算法分析】使用C语言实现队列的两种(带头结点与不带头结点)链式存储,并且给出一种循环队列的设计思想

      当我们编写程序时,经常需要处理各种数据结构。队列是一种常见的数据结构,它有着广泛的应用场景。队列的基本操作包括入队和出队,应用于模拟等待队列、消息队列、计算机缓存等场合。   在实际编程中,我们可以用不同的数据结构来实现队列。本文主要介绍了

    2024年02月08日
    浏览(118)
  • 数据结构|连通图、完全图、无向图、有向图的边数计算问题

    完全图 也称简单完全图。一个图任意两个顶点之间都有边的话,该图就称为完全图。 连通图(一般都是指无向图) 如果图中任意俩顶点都连通,则该图为连通图。 有向图 由点和弧所构成的图( 强连通图必然是有向图,因为强连通和弱连通的概念只在有向图中存在 ) 无向

    2023年04月08日
    浏览(47)
  • HNU数据结构与算法分析-作业1-算法分析

      1. (简答题) 1.(教材3.4)(a)假设某一个算法的时间代价为 ,对于输入规模n,在某台计算机上实现并完成该算法的时间为t秒。现在另有一台计算机,运行速度为第一台的64倍,那么t秒内新机器上能完成的输入规模为多大? 2.(教材3.12) 写出下列程序段平均情况下时间代

    2024年02月05日
    浏览(45)
  • C/C++语言 数据结构 创建邻接表存储的无向图及其邻接表的输出

    目录 1.邻接表相关知识补充  2. 图的邻接存储表示 3.测试输入与输出样例 4.代码实现 4.1 创建无向图邻接表 4.2 输入无向图的邻接表 定义: 对于图中每个顶点 vi,把所有邻接于 vi的顶点(对有向图是将从vi出发的弧的弧头顶点链接在一起)链接成一个带头结点的单链表,将所

    2024年02月05日
    浏览(47)
  • HNU数据结构与算法分析-作业2-线性结构

      1. (简答题) 4.1 假设一个线性表包含下列元素: |2,23,15,5,9 使用Shaffer编写的教材《数据结构与算法分析》的List ADT编写一些C++语句,删除值为15的元素。 (要求:采用C或C++语言描述算法) 4.6 使用Shaffer编写的教材《数据结构与算法分析》的LList类,给LList类的实现添加一个成

    2024年02月05日
    浏览(54)
  • 数据结构基本概念及算法分析

    数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科 1.1.1 数据 数据: 描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合. 数据不仅包括整型,实型等数据类型,还包括字符及

    2024年02月15日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包