【数据结构与算法】图

server/2024/9/23 7:38:57/

目录

  • 一.的原理
  • 二.的表示
    • 1.邻接列表
    • 2.邻接矩阵
  • 三.的结构——邻接表
  • 四.邻接表的初始化
  • 五.邻接表的创建
  • 六.完整代码

一.的原理

在我们的日常生活中,可谓是应用广泛,最长见的就有地.
在这里插入<a class=图片描述" />
可以是双向的,也可以是单向的.
是一种由节点和边组成的数据结构.
节点(顶点):中的基本单位,表示实体。
边:连接两个节点,表示实体之间的关系。
路径:从一个节点到另一个节点的一系列边。

权重:边可以带有权重,表示连接两个节点的成本或距离。
权重就像这个车票一样,当然还可以综合考虑,主要看你最看重的是什么,距离,还是路况等等都可以作为权重.
在这里插入<a class=图片描述" />

二.的表示

是比较复杂的一种数据结构,直接表示我们不好表示,我们间接表示.

1.邻接列表

就是我们将每个节点作为一个头结点数组,然后后面跟着相关联边的节点.
可以看这个列子:
在这里插入<a class=图片描述" />
这样我们就巧妙的将,两个有关联的顶点放在了一起.
但是有一个缺点就是我们要找到目标路径需要遍历节点,因为每个节点相关联边的节点有很多,需要逐一比对,才能知道有没有目标路径.

很像我们的哈希表哦,哈哈.

2.邻接矩阵

在这里插入<a class=图片描述" />
这个的优点很明显,就是只需要看数组的值是不是零,不为零就可以走通.
但是缺点同样很明显,那就是如果我们要插入或者删除一个节点,那么会需要重新构建一个二维数组,并且很多空间是浪费的.

所以大多数的情况下,我们都是用的邻接列表,而不是矩阵,除非每个节点都与很多节点相关联.

三.的结构——邻接表

这里我们就用邻接列表来构建我们的.

在这里插入<a class=图片描述" />
我框的三个部分,就是我们这个结构的主题.
三个层次,我们先从最里面的开始.
在这里插入<a class=图片描述" />
这就是与节点关联的边,将邻接的顶点记录下来,还有指向下一个与节点关联的边.
在这里插入<a class=图片描述" />
第二部分,就是咱们的顶点.
在这里插入<a class=图片描述" />
需要有数据和与之相关联的第一条边.,其他的可以连接在边的后面.
在这里插入<a class=图片描述" />
最外面的一层就是这个顶点数组.

在这里插入<a class=图片描述" />
这里我们打算动态分配,所以定义的顶点的指针.
在这里插入<a class=图片描述" />

四.邻接表的初始化

动态分配顶点数组.
在这里插入<a class=图片描述" />

五.邻接表的创建

先输入顶点数和边数,和顶点的数据,并将各个顶点相关联的边设置为空.
在这里插入<a class=图片描述" />
输入相关联边的两个顶点数据,进行连接.
在这里插入<a class=图片描述" />
因为我们是输入的数据,我们要找到其在数组中的下标,然后再用前插法,插入到顶点之后.
在这里插入<a class=图片描述" />
我们边保存的节点就是在数组中的下标位置.
这里权重没有设置.

六.完整代码

#include <iostream>using namespace std;
#define MaxSize 1024typedef struct _EdgeNode//与节点连接边的定义
{int adjvex;//邻接的顶点int weight;//权重struct _EdgeNode* next;//下一条边
}EdgeNode;typedef struct _VertexNode//顶点节点
{char data;//节点数据EdgeNode* first;//指向邻接第一条边,头节点
}VertexNode,AdjList;typedef struct _AdjListGraph
{AdjList* adjlist;int vex;//顶点数int edge;//边数
}AdjListGraph;int Location(AdjListGraph& G, char c);//的初始化
void init(AdjListGraph& G)
{G.adjlist = new AdjList[MaxSize];G.edge = 0;G.vex = 0;
}//的创建
void Create(AdjListGraph& G)
{cout << "请输入的顶点数以及边数:" << endl;cin >> G.vex >> G.edge;cout << "请输入相关的顶点:" << endl;for (int i = 0; i < G.vex; i++){cin >> G.adjlist[i].data;G.adjlist[i].first = NULL;}char v1=0, v2=0;//保存输入顶点的字符int i1, i2;//保存顶点在数组中的下标cout << "请输入相关联边的顶点:" << endl;for (int i = 0; i < G.edge; i++){cin >> v1 >> v2;i1 = Location(G, v1);i2= Location(G, v2);if (i1!=-1 && i2!=-1)//寻找到位置{EdgeNode* temp = new EdgeNode;temp->adjvex = i2;temp->next = G.adjlist[i1].first;G.adjlist[i1].first = temp;}}
}//通过顶点对应的字符寻找顶点在中的邻接点
int Location(AdjListGraph& G, char c)
{for (int i = 0; i < G.vex; i++){if (G.adjlist[i].data == c){return i;}}return -1;
}

2024年8月14日11:39:35


http://www.ppmy.cn/server/101371.html

相关文章

android FD_SET_chk问题定位

android FD_SET_chk问题定位 一、FD报错二、问题定位2.1 APM定位2.2 adb定位2.3. 代码获取FD数 三、FD优化 一、FD报错 App在运行中记录报错如下&#xff0c;FD_SET&#xff0c;这个问题大概是文件描述符&#xff08;File Descriptor&#xff0c;简称FD&#xff09;超过了最大…

2024新型数字政府综合解决方案(三)

新型数字政府综合解决方案通过融合人工智能、大数据和云计算技术&#xff0c;建立了一个智能化、互联互通的政府服务平台&#xff0c;旨在提升政府服务效率与透明度。该方案通过全面数字化政务流程&#xff0c;实现数据的实时共享和自动化处理&#xff0c;使公众能够便捷地访问…

map/set和unordered_map/unordered_set的区别及使用情况

map/set和unordered_map/unordered_set的区别 容器底层数据结构是否有序实现版本复杂度迭代器map/set红黑树有序C98O(logN&#xff09;双向迭代器unordered_map/unordered_set哈希表/散列表无序C11O(1)单向迭代器 unordered_set无序的&#xff08;VS下&#xff09; void uno…

C#工具库-NPOI

一、简介 NPOI是一个基于c#语言的&#xff0c;开源的&#xff0c;能够在不安装Microsoft Office组件的条件下读写Microsoft Office 的库。前身是Java的POI库,有“先贤”将其翻译成了c#语言的库&#xff0c;而这种由java到c#库的演变并非个例&#xff0c;比如DotNetty之于Netty,…

LabVIEW光伏微网实验系统

开发了一个基于LabVIEW的光伏微网实验系统&#xff0c;系统主要服务于工程教育和技术研究&#xff0c;以提高学生对分布式电力系统的理解和操作能力。该实验系统能够模拟光伏微网的各种运行状态&#xff0c;包括能量的生成、存储和消费等&#xff0c;特别是在无电网状态下的独立…

Windows禁止应用联网

转自两种方法阻止电脑上的软件彻底联网&#xff01; - 知乎 (zhihu.com) 但为了稳妥&#xff0c;自己还是稍微记录一下 1、创建bat脚本文件 创建文本-将下面的代码填入-保存为.bat文件 Echo Off SetLocal:beginecho: echo ****** 禁止文件夹联网 ****** echo:set /p folder…

C++STL初阶(12):stack和queue的初阶实现

1. stack的选型 对于栈的实现是我们非常熟悉的过程&#xff1a; C语言基础数据结构——栈和队列_栈和队列 插入取出数据-CSDN博客 _top表示下标&#xff0c;_capacity表示空间大小&#xff1a; 那么按照我们原来的思路&#xff0c;利用_top和_capacity T*来给stack构形。 temp…

开发军用LabVIEW程序注意事项

在开发军用LabVIEW程序时&#xff0c;开发者需要从多个角度仔细考虑&#xff0c;以满足军方对安全性、可靠性、法规遵从性等方面的严格要求。由于军事系统通常涉及高度敏感的信息和严苛的环境条件&#xff0c;程序的设计必须保证数据的保密性、系统的稳定性以及与各种军事标准的…