【数据结构】七、图

一、概念

:记为G(V,E)

有向图:每条边都有方向

无向图:边无方向

完全图:每个顶点都与剩下的所有顶点相连

完全有向图有n(n-1)条边;完全无向图有n(n-1)/2条边

对于完全无向图,第一个节点与剩下n-1个节点相连,第二个与剩下n-2个相连……倒数第二个与最后一个相连,[(n-1)+(n-2)+......+1] = n*(n-1)/2

乘2得到完全有向图的边数

带权图:边上标有数值的图

连通图:任意两点都有路可走

要连通具有n个顶点的有向图,至少需要n条边。(构成环)

生成树:该树包含图的所有n个节点,树有n-1条边,将图连通。

如果添加一条边,必定出现环;

邻接点:一条边两端的点互为邻接点。

:与点相连的边的条数为点的度;有向图中,从点发出的边数叫点的出度 ,在点终止的边数叫点的入度。

路径:从一个点沿着边走到另一个点,途径的顶点序列叫路径。

路径长度:非带权图的路径长度是指此路径上边的条数; 带权图的路径长度是指路径上各边的权之和。

二、图的存储结构

2.1邻接矩阵

建立一个长和宽都为顶点数的数组,用数组元素的值表示点之间的连接情况。

无向图:

  • 点不相连为0,相连为1
  • 无向图邻接矩阵对称
  • 顶点i的度 = 第i行/列中,1的个数

有向图

  • 不对称
  • 元素a_{ij}为1,表明有一条点i指向点j的边(注意方向)
  • 顶点i的出度 = 第i行中,1的个数
  • 顶点i的入度 = 第i列中,1的个数
  • 顶点i的度 = 第i行和第i列中,1的个数之和

带权图

相当于把有向图的1换为边上的值

设图的邻接矩阵如下所示。各顶点的度依次是(   )

A. 1 2 1 2

B. 2 2 1 1

C. 3 4 2 3

D. 4 4 2 2

答案:C   行和列的1求和

空间复杂度:n^2

代码

int* adjacent_mat(int v, int e, int direct) 
{int* mat = (int*)malloc(sizeof(int) * v * v);  //分配空间if (!mat) return NULL;int i, start, end, weight;for (i = 0; i < v * v; i++)mat[i] = INF;           //节点全部初始化为无穷大(设无穷为65535)for (i = 0; i < e; i++)     //输入边信息{printf("输入起始 终止 权值:");scanf_s("%d %d %d", &start, &end, &weight);direct == 0 ? mat[start * v + end] = mat[end * v + start] = weight : mat[start * v + end] = weight;      //direct=0时生成无向图,对称赋值;等于1生成有向图}for (i = 0; i < v * v; i++) {mat[i] == INF ? printf("0 ") : printf("%d ", mat[i]);if ((i + 1) % v == 0)printf("\n");}return mat;
}

2.2邻接表

适用于稀疏矩阵

对每个节点建立一个链表,把与之相连的点存入节点,连接起来

一个图的邻接矩阵唯一,邻接表不唯一

每个节点的链表的结构

无向图的邻接表,顶点的度=该节点链表子结点个数:

有向图的邻接表和逆邻接表:

空间复杂度(n+e)  点数加边数

代码

node* adjacency_list(int v, int e, int direct) 
{headnode* headlist = (headnode*)malloc(sizeof(headnode) * v);if (!headlist) return NULL;int i;for (i = 0; i < v; i++) {headlist[i].data = i;headlist[i].next = NULL;}int start, end, weight;node* p, * newnode;for (i = 0; i < e; i++){printf("输入起始 终止 权值:");scanf_s("%d %d %d", &start, &end, &weight);if (direct != 2) {newnode = (node*)malloc(sizeof(node));newnode->adjvex = newnode->data = end;newnode->next = NULL;p = headlist[start].next;if (!p) {headlist[start].next = newnode;}else {while ((p->next) != NULL)p = p->next;p->next = newnode;}}if (direct == 0 || direct == 2){newnode = (node*)malloc(sizeof(node));newnode->adjvex = newnode->data = start;newnode->next = NULL;p = headlist[end].next;if (!p) {headlist[end].next = newnode;}else {while ((p->next) != NULL)p = p->next;p->next = newnode;}}}for (i = 0; i < v; i++) {printf("%d:", headlist[i].data);p = headlist[i].next;while (p) {printf("%d ", p->data);p = p->next;}printf("\n");}
}

2.3十字链表

考试没要求,先不写

三、图的遍历

图的遍历是从给定的源点出发,每个节点仅访问一次

基本算法有深度遍历和广度遍历两种

3.1深度优先DFS

沿着一条路一直走,没路了再回头找最近的分岔路口

如上图,从v1开始DFS,可得到v1-v2-v4-v8-v5-v3-v6-v7

void DFS(int*mat, int v, int num, int*& visited)  //深度优先,递归版。需要传入邻接矩阵,点数,起始点编号,已访问数组
{printf("%d", num);             //输出起始节点visited[num] = 1;              //标记起始节点for (int i = 0; i < v; i++)    //在起始节点这一行从头搜索未遍历过的邻接点,进行递归if (!visited[i] && mat[num * v + i] != INF)DFS(mat, v, i, visited);	
}void DFS2(int* mat, int v) 
{int head = 0, i;int* stack = (int*)malloc(sizeof(int) * v);     //创建栈if (!stack) return;int* visited = (int*)malloc(sizeof(int) * v);   //创建标记数组,初始化为0if (!visited)  return;for (i = 0; i < v; i++)visited[i] = 0;int num;printf("输入开始节点编号:");scanf_s("%d", &num);//循环中,入栈在最后,所以先入栈一个点stack[head++] = num;      //入栈,标记, 输出visited[num] = 1;printf("%d", num);int temp;while (head)    //栈空时结束{temp = stack[head - 1];   //获取栈顶for (i = 0; i < v; i++)   //对栈顶对应的邻接矩阵所在行进行遍历,有未标记且相邻的就赋值退出,找不到则退栈{if (visited[i] == 0 && mat[temp * v + i] != INF) {temp = i;break;}}if (i == v)   //找不到退栈,找到入栈head--;else {stack[head++] = i;visited[i] = 1;printf("%d", i);}}
}void DFS3(int* mat, int v) 
{int top = -1, i;int* stack = (int*)malloc(sizeof(int) * v);     //创建栈if (!stack) return;int* visited = (int*)malloc(sizeof(int) * v);   //创建标记数组,初始化为0if (!visited)  return;for (i = 0; i < v; i++)    //标记数组初始化为0visited[i] = 0;int num;printf("输入开始节点编号:");scanf_s("%d", &num);//循环中,入栈在最后,所以先入栈一个点stack[++top] = num;      //入栈,top指向栈顶元素visited[num] = 1;        //标记int temp;while (top >= 0)    //栈空时结束{temp = stack[top];   //获取栈顶printf("%d", temp);for (i = 0; i < v; i++)   //对栈顶对应的邻接矩阵所在行进行遍历,有未标记且相邻的就赋值退出,找不到则退栈{if (visited[i] == 0 && mat[temp * v + i] != INF) {stack[++top] = i;visited[i] = 1;break;}}if (i == v)   //该节点所有相邻节点访问完毕,退栈top--;}
}

3.2广度优先BFS

访问节点,把它的子节点全部访问,再依次访问子节点的全部子节点

时间复杂度

DFS和BFS相同:

用邻接矩阵存储时,O(n^2)

用邻接表存储时,O(n+e)

四、最小生成树

生成树:是一个极小连通子图,它含有图中全部顶点,但只有n-1条边

最小生成树:各边权值之和最小的树

4.1PRIM普利姆算法

将所有点分为树U和图V两个集合,找到UV两个点集之间的权值最小边,把该边V中的点移到U里面,重复,直到V点全部到U里面

表格横表头为除起点外其他点、U集合、V-U集合;竖表头为lowcost:点到U集合的最小值,adjvex:最小值相连的点

每一次选出lowcost最小的加入U集合,然后用这个节点到其它节点的距离更新lowcost和adjvex;已确定的点写0

#include<stdio.h>
#include<stdlib.h>#define INF 65535typedef struct node {int adjvex;int data;struct node* next;
}node;typedef struct {int data;node* next;
}headnode;int* adjacent_mat(int v, int e, int direct)
{int* mat = (int*)malloc(sizeof(int) * v * v);if (!mat) return NULL;int i, start, end, weight;for (i = 0; i < v * v; i++)mat[i] = INF;for (i = 0; i < e; i++){printf("输入起始 终止 权值:");scanf_s("%d %d %d", &start, &end, &weight);direct == 0 ? mat[start * v + end] = mat[end * v + start] = weight : mat[start * v + end] = weight;}for (i = 0; i < v * v; i++) {mat[i] == INF ? printf("0 ") : printf("%d ", mat[i]);if ((i + 1) % v == 0)printf("\n");}return mat;
}void prim(int* mat, int v)   //求最小生成树。始终寻找未标记点到已标记集合的最短距离;而迪杰斯特拉是寻找未标记点到源点的最短距离
{int i, num, min, x, time = 0;int* visited = (int*)malloc(sizeof(int) * v);   //标记是否已遍历if (!visited) return;for (i = 0; i < v; i++)visited[i] = 0;int* lowcost = (int*)malloc(sizeof(int) * v);   //lowcost为未标记点到已标记点集合的最小值,from为与之连接的点的编号if (!lowcost) return;int* from = (int*)malloc(sizeof(int) * v);if (!from) return;printf("输入起始节点:");scanf_s("%d", &num);visited[num] = 1;time++;for (i = 0; i < v; i++) {lowcost[i] = mat[num * v + i];from[i] = num;}while (time != v){min = INF;for (i = 0; i < v; i++)    //找到距离最小点,传播{if (lowcost[i] < min && visited[i] != 1){min = lowcost[i];x = i;}}printf("%d-%d\n", from[x], x);visited[x] = 1;//num = x;time++;for (i = 0; i < v; i++)   //更新距离最小值if (mat[x * v + i] < lowcost[i] && visited[i] != 1) {lowcost[i] = mat[x * v + i];from[i] = x;}}
}int main() {int v, e, direct;printf("输入点数 边数:");scanf_s("%d %d", &v, &e);printf("无向图输入0,有向图输入1:");scanf_s("%d", &direct);int* admat = adjacent_mat(v, e, direct);prim(admat, v);
}

时间复杂度O(n^2)  外层:为n个节点确定位置;内层:对于新确定的节点计算他和其他节点的距离

五、拓扑排序

1.选定一个没有直接前驱的点,输出

2.删除该起点和它相邻的边

3.重复1,2直到点全部输出,得到拓扑序列

如果还有未输出的节点,说明这些点都有直接前驱,即图中存在环

拓扑排序可以判断图是否有环

拓扑序列为:4 0 3 2 1 5

对上图进行拓补排序,可以得到不同的拓扑序列的个数是(    )

答案:3

六、关键路径

顶点表示事件,有向边表示活动,边的权值表示完成活动所需时间,这样的网络叫AOE网

比如说,我们要完成一项工程,为了达到最终目标,我们要先完成许多小任务

事件最早发生时间VE:是到这一事件的最长路径。因为只有所有前期工作都做完了,这个事件才能发生,所以把前期工作完成需要的最长时间是该事件的最早发生时间。

  1. ve(源点)=0
  2. ve(k) = Max{ ve{j} + Weight(j, k) }, j为k的任意前提顶点, Weight(j, k)表示<j, k>边上的权值 

事件的最晚发生时间VL:在完成总工程所需时间不变的情况下,一个事件最晚可以发生的时间。比如ab是c事件的前期工作,a花的时间比b长,由于c最早开始时间由最长的路径决定,所以b可以推迟一会再发生,也不会耽误总工期。

  1. vl(汇点) = ve(汇点)
  2. vl(k) = Min{ vl(j) - Weight(k, j) } ,k为j的任意前驱

边的最早开始时间E:即起始点的最早发生时间,事件一发生,活动就开始

边的最晚开始时间L:终点的最晚发生时间减去活动所需时间,由活动结束最晚时间倒退活动最晚开始时间

时间余量:活动的最早最晚开始时间之差,代表该活动最长拖延时间。如果该活动时间余量为0,说明为保证总时间,该活动不能拖延,称其为关键活动。把关键活动连起来得到关键路径

应用题模板

写出点的ve和vl,边的权值、e和l

下列关于AOE网的叙述中,不正确的是( )。
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成,那么整个工程将会提前完成
C.所有的关键活动提前完成,那么整个工程将会提前完成
D.某些关键活动提前完成,那么整个工程将会提前完成

答案:B   关键路径是网络中最长路径,表示完成工程的最短时间。关键活动延期,总工程延期;关键活动提前,总工程不一定提前,因为关键路径可能不止一条

七、最短路径

迪杰斯特拉算法

用于求一个点到其它点的最短路径

找与起点相连的节点,更新距离和路径

找距离最小的节点,将其固定,更新为起点

应用题模板

如下有向带权图,若采用迪杰斯特拉算法求源点a到其他各顶点的最短路径,得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是()

答案:fde

下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中,加快其进度就可以缩短工程工期的是( )

A. c 和 e

B. d 和 e

C. f 和 d

D. f 和 h

答案:C       根据图做出ve、vl表,再做出e、l表,找到关键路径。有bdcg、bdeh、bfh三条。要缩短总工期,三条关键路径都要缩短,只有C选项能同时影响三条路径。

从本题可以看出,只看点的ve=vl不能确定关键路径 ,必须看e=l

下列关于最小生成树的说法中,正确的是()。

Ⅰ.最小生成树的代价唯一
Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ.使用普里姆( Prim)算法从不同顶点开始得到的最小生成树一定相同
Ⅳ.使用普里姆算法和克鲁斯卡尔( Kruskal)算法得到的最小生成树总不相同

A.仅Ⅰ

B.仅Ⅱ

C.仅Ⅰ、 Ⅲ

D.仅Ⅱ、 Ⅳ

答案:A    设想一个各边权值相等的树,则BCD错

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/229103.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【CISSP学习笔记】5. 安全架构和工程

该知识领域涉及如下考点&#xff0c;具体内容分布于如下各个子章节&#xff1a; 使用安全设计原理来研究、实施与管理工程过程理解安全模型的基本概念&#xff08;例如 Biba、Star Model、Bell-LaPadula 等模型&#xff09;基于系统安全要求选择控制措施理解信息系统 (IS) 的安…

Android ImageView的Bitmap在scaleType情况下Bitmap顶部与底部RectF坐标,Kotlin

Android ImageView的Bitmap在scaleType情况下&#xff0c;Bitmap顶部与底部RectF坐标&#xff0c;Kotlin 通常&#xff0c;在ImageView设置scaleType后&#xff0c;Android会把原始图片通过缩放放在ImageView里面&#xff0c;例如&#xff1a; <ImageViewandroid:id"id…

【Linux操作系统】探秘Linux奥秘:文件系统的管理与使用

&#x1f308;个人主页&#xff1a;Sarapines Programmer&#x1f525; 系列专栏&#xff1a;《操作系统实验室》&#x1f516;诗赋清音&#xff1a;柳垂轻絮拂人衣&#xff0c;心随风舞梦飞。 山川湖海皆可涉&#xff0c;勇者征途逐星辉。 目录 &#x1fa90;1 初识Linux OS &…

白话机器学习的数学-2-分类

1、设置问题 图片分类&#xff1a;只根据尺寸把它分类为 纵向图像和横向图像。 如果只用一条线将图中白色的点和黑色的点分开&#xff1a; 这次分类的目的就是找到这条线。 2、内积 找到一条线&#xff0c;这是否意味着我们要像学习回归时那样&#xff0c;求出一次函数的斜率…

大数据背景下基于联邦学习的小微企业信用风险评估研究

摘要&#xff1a; 小微企业信用风险评估难是制约其融资和发展的一个主要障碍。基于大数据的小微企业信用风险评估依然面临着单机构数据片面、跨机构数据共享难、模型不稳定等诸多挑战。针对相关问题和挑战&#xff0c;本项目拟在多主体所有权数据隐私保护与安全共享的背景下&am…

梳理Langchain-Chatchat-UI接口文档

在 Langchain-Chatchat v0.1.17 版本及以前是有前后端分离的 Vue 项目的&#xff0c;但是 v0.2.0 后就没有了。所以本文使用的是 Langchain-Chatchat v0.1.17 版本中的 Vue 项目。经过一番折腾终于将 Langchain-Chatchat v0.1.17 版本前端 Vue 接口和 Langchain-Chatchat v0.2.…

人大金仓数据库与mysql比较

简介 人大金仓数据库是基于 PostgreSQL 开发的。 SQL语言 语法 关键字 KES&#xff1a; MYSQL&#xff1a; 语句 *特性MYSQLKES字符串字面量单引号()或 双引号(")十六进制字面量0x5461626c65&#xff0c;X5461626c65/BIT字面量b1000001,0b1000001/Boolean字面量常…

数据加密、端口管控、行为审计、终端安全、整体方案解决提供商

PC端访问地址&#xff1a; https://isite.baidu.com/site/wjz012xr/2eae091d-1b97-4276-90bc-6757c5dfedee 以下是关于这几个概念的解释&#xff1a; 数据加密&#xff1a;这是一种通过加密算法和密钥将明文转换为密文&#xff0c;以及通过解密算法和解密密钥将密文恢复为明文…

生活常识-如何开社保证明(四川)

下载并打开天府市民云APP 注册后登陆 点击社保服务 点击社保证明 点击【四川省社会保险个人社保证明名(近24个月)】 点击下载 下载后点击【QQ发送给好友&#xff0c;然后发送给自己的电脑设备(我的电脑)】

设计模式之工厂设计模式【创造者模式】

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持&#xff0c;想组团高效学习… 想写博客但无从下手&#xff0c;急需…

国标GB28181对接的时候如何配置服务端口和本地端口

目 录 一、国标GB28181对接需要配置的端口等参数 二、GB28181服务器端口的配置&#xff1a;SIP服务器端口 三、GB28181设备测端口的配置&#xff1a;本地SIP端口 &#xff08;一&#xff09;本地SIP端口配置的意义 &#xff08;二&#xf…

香橙派5plus从ssd启动Ubuntu

官方接口图 我实际会用到的就几个接口&#xff0c;背面的话就一个M.2固态的位置&#xff1a; 其中WIFI模块的接口应该也可以插2230的固态&#xff0c;不过是pcie2.0的速度&#xff0c;背面的接口则是pcie3.0*4的速度&#xff0c;差距还是挺大的。 开始安装系统 准备工作 一张…

十四:爬虫-Redis基础

1、背景 随着互联网大数据时代的来临&#xff0c;传统的关系型数据库已经不能满足中大型网站日益增长的访问量和数据量。这个时候就需要一种能够快速存取数据的组件来缓解数据库服务I/O的压力&#xff0c;来解决系统性能上的瓶颈。 2、redis是什么 Redis 全称 Remote Dictio…

TTS | NaturalSpeech语音合成论文详解及项目实现【正在更新中】

----------------------------------&#x1f50a; 语音合成 相关系列直达 &#x1f50a; ------------------------------------- ✨NaturalSpeech&#xff1a;正在更新中~ ✨NaturalSpeech2&#xff1a;TTS | NaturalSpeech2语音合成论文详解及项目实现 本文主要是 讲解了Nat…

高斯矩阵相乘

高斯分布的概率密度函数&#xff1a; 其本质问题可抽象为&#xff1a;已知两个独立高斯分布&#xff0c; N 1 ∼ ( u 1 , δ 1 2 ​ ) &#xff0c; N 2 ∼ ( u 2 , δ 2 2 ) N 1∼(u1 ,δ 1^2​ )&#xff0c;N 2 ∼ ( u 2 , δ 2^ 2 ) N1∼(u1,δ12​)&#xff0c;N2∼(u2,δ…

iOS问题记录 - iOS 17通过NSUserDefaults设置UserAgent无效(续)

文章目录 前言开发环境问题描述问题分析1. 准备源码2. 定位源码3. 对比源码4. 分析总结 解决方案补充内容1. UserAgent的组成2. UserAgent的设置优先级 最后 前言 在上篇文章中对该问题做了一些判断和猜测&#xff0c;并给出了解决方案。不过&#xff0c;美中不足的是没有进一…

基于策略模式和简单工厂模式实现zip、tar、rar、7z四种压缩文件格式的解压

推荐语 这篇技术文章深入探讨了基于策略模式和简单工厂模式实现四种常见压缩文件格式的解压方法。通过阅读该文章&#xff0c;你将了解到如何利用这两种设计模式来实现灵活、可扩展的解压功能&#xff0c;同时适应不同的压缩文件格式。如果你对设计模式和文件处理感兴趣或刚好…

elasticsearch系列六:索引重建

概述 我们再起初创建索引的时候由于数据量、业务增长量都并不大&#xff0c;常常不需要搞那么多分片或者说某些字段的类型随着业务的变化&#xff0c;已经不太满足未来需求了&#xff0c;再或者由于集群上面索引分布不均匀导致节点直接容量差异较大等等这些情况&#xff0c;此时…

ubuntu中PyCharm导入虚拟环境pytorch / TensorFlow

之前编辑pytorch框架的程序都是在jupyter notebook,虽然jupyter notebook采用交互式的方式很方便&#xff0c;有时候查看别人代码的时候&#xff0c;很不方便&#xff0c;所以就下载了Pycharm&#xff0c;这里我就不赘述如何系在pycharm和如何破解&#xff0c;希望能帮助到大家…

CRM客户关系管理系统

系统开发环境以及版本 操作系统&#xff1a; Windows_7集成开发工具&#xff1a; Eclipse EE_4.7编译环境&#xff1a;JDK_1.8Web服务器&#xff1a;Tomcat_9.0数据库&#xff1a;MySQL_5.7.23 系统框架 spring框架springmvc框架mybatis框架Logback日志框架安全验证框架maven框…