图论及其应用 学习笔记(一)图的基本概念

发布时间:2022-11-24 学习 算法 图论
记录一下这门课程的知识点和个人理解,参考资料为这门课老师的讲解、电子科大杨春老师的PPT,以及《图论与网络最优化算法》这本书 图的定义与图论模型 图的定义 一个图是一个序偶<V,E>,记为G=(V,E),其中: V是一个有限的非空集合,称为顶点集合,其元素称为顶点或点。用|V|表示顶点数;E是由V中的点组成的无序对构成的集合,称为边集,其元素称为边,且同一点对在E中可以重复出现多次。用|E|表示边数。 图可以用图形表示:V中的元素用平面上一个黑点(小圆圈)表示,E中的元素用一条连...

【一维数组DFS】【回溯就要用到dfs】基础实验6-2.3 拯救007 (25 分)

欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录) 文章字体风格: 红色文字表示:重难点 蓝色文字表示:思路以及想法   如果大家觉得有帮助的话,感谢大家帮忙点赞!收藏!转发! 一维数组 dfs 思路 在一维数组中,各元素之间没有连接关系,或者说是相关关联的联系,那么,从一个点开始,如何遍历出一条路径?如下是dfs的思路 在main函数中 用一个循环遍历所有节点,在循环中,把每次循环到的节点进行dfs,然后在dfs中,再根据这个节点,从头开始...

【DFS和BFS习题集】(更新至16523 字)

发布时间:2022-11-24 算法 宽度优先 C++ 图论 深度优先
目录 第一题:八皇后(dfs+路径输出(前驱版)) 第一题的补充练习:N皇后(dfs + 打表) 第二题:自然数的拆分 第三题:图的遍历(BFS和DFS) 第四题: fire net(dfs) 第五题:nightmare(可以走回头路的DFS) 第六题:滑雪(求矩阵里的最长连续下降序列 ,记忆化dfs) 第七题:连连看(dfs求拐数) 第八题:逃离迷宫(dfs求拐数(相对简单)) 第九题:sticks(抽象的DFS) 第十题:变形课(隐藏的dfs) 第十一题:求拐数(地图方向限定,dfs) 第十二题:记忆...

【图论习题集】(dijkstra, 匈牙利算法,更新至8873字)

发布时间:2022-11-25 数据结构 算法 C++ 图论 深度优先
目录 板块一:最短路 第一题:畅通工程续(dijkstra的堆优化) 第二题:HDU today(普通dijkstra + map) 第三题:choose the best route(普通dijkstra + 多起点 + 有向图) 板块二:二分图 第一题:过山车(匈牙利算法基本模板) 第二题:机器调度(普通匈牙利算法,最小点覆盖) 第三题:Air Raid(最小路径覆盖) 第四题:50 years, 50 colors(比较抽象的匈牙利算法,补充邻接矩阵写法) 第五题:courses(简单题,复习巩固)...

New Year Tree

发布时间:2022-11-27 数据结构 算法 图论
New Year Tree Translation 给出一棵 n n n个节点的树,根节点为 1 1 1。每个节点上有一种颜色 ...

2022山东理工大学pta程序设计---实验五(一维数组)详解

·## 7-1 sdut- C语言实验—最值 有一个长度为n的整数序列,其中最大值和最小值不会出现在序列的第一和最后一个位置。 请写一个程序,把序列中的最小值与第一个数交换,最大值与最后一个数交换。输出转换好的序列。 输入格式: 输入包括两行。 第一行为正整数n(1≤n≤10)。 第二行为n个正整数组成的序列。 输出格式: 输出转换好的序列。数据之间用空格隔开。 输入样例: 6 2 3 8 1 4 5 输出样例: 1 3 5 2 4 8 #include <stdio.h>int q[100]...

17-11-08纠错

发布时间:2022-11-29 数据结构 算法 图论
1.不适合用链式存储结构的检索方法:二分查找(只能在顺序结构上进行并且要求元素有序) (注:哈希查找中的开散列方法,同时有顺序结构与链式结构) 2.prim算法的使用方法为基于连通分量找最小边。 代码如下: int prim() { int i,j,pos,min,sum; for(i=1;i<=N;i++) dist[i]=map[1][i]; visited[1]=1; for(i=1;i<N;i++) { min=INF; for(i=1;i<N;i++) { if(!...

MFC-QT校园导航系统(旅行商TSP算法)

发布时间:2022-11-24 C++ MFC 图论 TSP QT5
MFC-QT校园导航系统(旅行商TSP算法) [问题描述] 旅行商(TSP)问题是从起点出发,经过所有点并回到起点,其路程最短。在一个面板上有一些点,每个点有八条通路通往上下左右和斜角的八个邻点,要求用QT实现选中其中一个点作为起点,再选中一些点作为必须经过的点,展现从起点出发经过所有点回到起点的路径。 请以学校场景模拟旅行商算法(TSP),如某同学从教室出发,需要去第三食堂吃早饭、按课表去计算中心上机、去某学院找老师答疑、去图书馆还书、去校医院看病,去羽毛球馆打球,取快递,再去同奥运餐厅吃午饭,再返回教...

网络流练习题单

发布时间:2022-11-27 算法 图论
博主开始从易到难练习网络流并更新题解,欢迎一起交流。 若开始学习网络流可以在这两篇博客进行学习 最大流的四种常用算法 最大流 — Edmond Karp算法 网络流24题 本题单出自洛谷,标签搜索 网络流24题 P2756 飞行员配对方案问题 匹配问题之一:基础的网络流,用网络流来解决二分图最大匹配问题。 题目链接:P2756 飞行员配对方案问题 题解链接:题解 P2763 试题库问题 匹配问题之二,不是二分图的一对一匹配,而是一对多的匹配问题,难点仍然在于如何建图,但也属于基础题目了,注意建图所需要的开...

食物链【法一:三种关系,用三个数组存储三种关系】【法二:将有关系的都存储在一个部落,用一个一维数组存储到根节点的距离表示关系】

原题链接 法一:三种关系,用三个数组存储三种关系 //x是同类域.//x+n是捕食域//x+n+n是天敌域#include <bits/stdc++.h>using namespace std;int fa[200000];int n,m,k,x,y,ans;int get(int x){ if(x==fa[x]) return x; return fa[x]=get(fa[x]);}void merge(int x,int y){ fa[get(x)]...

最短路径=

发布时间:2022-11-29 数据结构 算法 搜索与图论 图论
【分类】 1.单源最短路 (1)所有边权都是正数 a.朴素Dijkstra算法 O( n^2 ) b.堆优化版Dijkstra算法 O( mlogn ) (2)存在负边权 a.BellmanFord O( nm ) b.SPFA 一般O( n ),最坏O(nm)  2.多源汇最短路 Floyd O( n^3) 一.单源最短路 【定义】 给定一个带权有向图G=(V,E),其中每条边的权是一个实数。另外,还给定V中的一个顶点,称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这...

【图】(四)最小生成树详解 - Prim与Kruskal - C语言

发布时间:2022-11-24 图论 数据结构 算法 C语言
目录 1 最小生成树问题 1.1 问题概述 1.2 求解问题的思想 2 算法求解 2.1 Prim算法 (1)算法思想 (2)实现 (3)算法分析 2.2 Kruskal算法 (1)算法思想 (2)并查集 (3)实现 (4)算法分析 1 最小生成树问题 求解思想: 最小生成树问题的解决方案是基于贪心的思想,向空边集A中不断加入“合适”的边,使其扩展至一棵最小生成树 1.1 问题概述 现在我们需要修建道路来连通各个城市,已知各道路修建费用不同,那么如何确定修建方案,使得连通各个城市的成本最小? ...

自动驾驶路径规划——Dijkstra算法

前言 这个学期学校开设了相应的课程,同时也在学习古月居机器人学系列的《基于栅格地图的机器人路径规划指南》,为了巩固知识,方便自己的学习与整理,遂以学习笔记的形式记录。 1. 深度优先(DFS)和广度优先(BFS)     深度优先搜索( Depth First Search , DFS ):首先从某个顶点出发,依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和该顶点有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶...

c++数据结构:图

发布时间:2022-11-29 C++ 数据结构 BUCTOJ 图论
图 Graph 图的ADT定义 G = (Vertx顶点, Edge边(无向)、弧(单向,有弧头,弧尾)) 多对多 邻接 a->f则f是a的邻接点,反之不成立 出度、入度 有向图、无向图 边 稀疏图、稠密图 边少or边多 极致的稠密图是完全图 带权图 子图G’=(V’, E’) 路径P=(v0v1…vn-1) 回路R=(v0v1…vn-1v0) 图的存储 邻接矩阵/邻接表 邻接矩阵 是顺序表 o(n2) 包含结点数目,结点名称,邻接矩阵 邻接表 是链表,使用前插法o(1),适合于存储稀疏图o(e),...

树上差分(含链式向前星,LCA,树上点差分的主要知识)

目录 1,树上差分(点差分,边差分)          1,点差分           2,边差分 2,链式向前星(建图必备) 1,符号的意义 2,遍历公式:for (int i = head[u]; i; i = edge[i].next) 3,LCA(最近公共父节点) 倍增建图LCA代码 4,一道模板题:P3128 [USACO15DEC]Max Flow P 1,树上差分(点差分,边差分)     1,点差分  (注:LCA为u与v最近的公共父节点) 让u到v这段绿色曲线都+1,我们可以从俩边...

答案解析——第五届“传智杯”全国大学生计算机大赛(练习赛)

发布时间:2022-11-29 C++ 算法竞赛 算法 图论
第五届“传智杯”全国大学生计算机大赛(练习赛) A [传智杯 #5 练习赛] 复读 题目描述 给定若干个字符串,不定数量,每行一个。有些字符串可能出现了多次。如果读入一个字符串后,发现这个字符串以前被读入过,则这个字符串被称为前面相同的字符串的复读,这个字符串被称为复读字符串。相应的,每个首次出现的字符串就是非复读字符串。 举个例子, abcdefabcabcabc 第 1 , ...

21级数据结构与算法实验7——查找表

发布时间:2022-11-27 C++ 数据结构 算法 图论
目录 7-1 电话聊天狂人 7-2 两个有序序列的中位数 7-3 词频统计 7-4 集合相似度 7-5 悄悄关注 7-6 单身狗 7-7 词典 7-8 这是二叉搜索树吗? 7-9 二叉搜索树 7-1 电话聊天狂人 分数 25 作者 DS课程组 单位 浙江大学 给定大量手机用户通话记录,找出其中通话次数最多的聊天狂人。 输入格式: 输入首先给出正整数N(≤105),为通话记录条数。随后N行,每行给出一条通话记录。简单起见,这里只列出拨出方和接收方的11位数字构成的手机号码,其中以空格分隔。 输出格式: ...

牛客竞赛NC15049 假的字符串 (字典树 + 拓扑排序判环)

发布时间:2022-11-26 数据结构 算法 C++ 图论 练习
 如何判断一个字符串无法作为字典序最小? 1.前缀出现 2.大小矛盾(出现环) 解决1.用字典树来存,先存再输出,记录单词结束位置,输出时判断前面的字母是否有为其他单词的结束 解决2.用拓扑排序判断环 代码: #include<bits/stdc++.h>using namespace std;const int MAXN = 3e5 + 10;struct node{ char c; bool end; node* right; node* nex;}p[MAXN]...

图04---最小生成树与实现

💖💖感谢各位观看这篇文章,💖💖点赞💖💖、收藏💖💖、你的支持是我前进的动力!💖💖 💖💖感谢你的阅读💖,专栏文章💖持续更新!💖关注不迷路!!💖 图01—图的基本概念与模型_ 图02— 存储结构: 邻接矩阵,关联矩阵,权矩阵,邻接表,十字链表 图03—图的遍历与实现 图04—最小生成树与实现 图05 — 最短路径问题 ...

异构网络小入

发布时间:2022-11-24 论文记录 图论
A Survey of Heterogeneous Information Network Analysis Heterogeneous Graph Attention Network 异构网络很火吗? 在一个网络中,不用节点的类型不同,这是肯定的。 所以,异构网络在表征比较复杂的情形时,是比较合适的。 自然语言处理中,图网络用的多吗? 是不是只在有知识图谱的情形下会使用到? 但在看SCI期刊论文中,比较多。 可是顶会论文中,没有怎么看到过。。 图怎么编码? 图由节点和边组成。 在编码节点时,是通过组合邻...

DGL图神经网络库使用大全

发布时间:2022-12-04 深度学习 图论 PYTHON
第1章:图 图表示实体(节点)和它们的关系(边),其中节点和边可以是有类型的 (例如,“用户” 和 “物品” 是两种不同类型的节点)。 DGL通过其核心数据结构 DGLGraph 提供了一个以图为中心的编程抽象。 DGLGraph 提供了接口以处理图的结构、节点/边 的特征,以及使用这些组件可以执行的计算。 本章路线图 本章首先简要介绍了图的定义(见1.1节),然后介绍了一些 DGLGraph 相关的核心概念: 1.1 关于图的基本概念 1.2 图、节点和边 1.3 节点和边的特征 1.4 从外部源创...

数据结构与算法 - 图

发布时间:2022-11-24 数据结构 算法 EDUCODER实训 图论
第1关:图的定义和术语 任务描述 本关任务:掌握图的定义和基本术语,并完成相应的选择题。 相关知识 图的定义 图 G 是由顶点集 V 和边集 E ,记为 G=(V,E) ,其中 V(G) 表示图 G 中的顶点的有限非空集合; E(G) 表示图 G 中顶点之间的关系集合。若 则用 |V| 表示图 G 中顶点的个数,也称为图 G 的阶, E={(u,v)∣u∈V,v∈V} ,用 ∣E∣ 表示图 G 中边的条数。 图的基本术语 下面是一些关于图的基本术语,在后面我们会经常碰到。 有向图 若 E 是有向边的有限...

数据结构作业—第十三周---- Prim算法 Kruskal算法 Dijkstra算法

发布时间:2022-11-24 数据结构 算法 # JAVA作业 图论
Prim算法: (只看点,不看边,适合边较多的图,即稠密图)       Kruskal算法: 是一种按权值的递增次序选择合适的边来构造最小生成树的方法;(稀疏图) Dijkstra算法: 适合带权有向图和带权无向图求单源最短路径; 不适合含负取值的图,求最短路径; 1 . 单选题 简单 7分 对于有n个顶点的带权连通图,它的最小生成树是指图中任意一个______。 A.由n-1条权值最小的边构成的子图 B.由n-l条权值之和最小的边构成的...

图05 --- 最短路径问题:算法与实现

💖💖感谢各位观看这篇文章,💖💖点赞💖💖、收藏💖💖、你的支持是我前进的动力!💖💖 💖💖感谢你的阅读💖,专栏文章💖持续更新!💖关注不迷路!!💖 图01—图的基本概念与模型_ 图02— 存储结构: 邻接矩阵,关联矩阵,权矩阵,邻接表,十字链表 图03—图的遍历与实现 图04—最小生成树与实现 图06 — 拓扑排序 ...

图的基本算法(邻接矩阵、邻接表、BFS广度优先搜索、DFS深度优先搜索、prim实现最小生成树、dijkstra实现单源最短路径)利用菜单选择

发布时间:2022-11-24 数据结构 算法 C++ 图论 深度优先
#include<iostream>#include<vector>#include<queue>#include<stack>#define MAX 10001using namespace std;enum GraphType{undigraph,digraph,undinetwork,dinetwork};template <class T>struct EdgeType//边{ T head, tail; int cost; EdgeTy...

CF35C Fire Again

发布时间:2022-11-24 C++ 算法 洛谷刷题记录 图论
知识点:广搜 难度:5 这个题给的难度5实际是虚高了,顶多是个绿题,CF的分是1500,还是比较准确的,这个就是一个裸的bfs,是个多源的bfs,然后我们广搜的时候每次出队的时候更新一下答案就行了,那么最后一定是最后才覆盖的点 然后就是这个题是啥标准输入输出啥的,需要在程序里面加上那个玩意儿,这个我记得学c语言的时候用到了,但是现在已经往的差不多了 #include <bits/stdc++.h>using namespace std;const int N = 2005;struct no...

POJ题目分类(补充中)

发布时间:2022-11-24 蓝桥杯 算法 C语言 图论
题目难度说明 POJ 1000简单题POJ 1003简单题POJ 1004简单题POJ 1005简单题POJ 1008简单题POJ 1012简单题POJ 1013简单题POJ 1016简单题POJ 1019简单题POJ 1026简单题POJ 1046简单题POJ 1102简单题POJ 1107简单题POJ 1247简单题POJ 1298简单题POJ 1316简单题POJ 1326简单题POJ 1519简单题POJ 1543简单题POJ 1547简单题POJ 1552简单题POJ 1565简单题POJ 15...

运筹说 第73期 | 图论创始人“数学之王”一 欧拉

发布时间:2022-11-24 运筹说 运筹学 图论
前面我们介绍了有关动态规划的相关内容,相信大家也都有了一些收获,下面我们学习的列车继续驶往“图与网络分析”的站点,在本次文章中我们将一起走近图论的奠基人——欧拉Leonhard Euler,希望能给大家学习运筹学的旅程中带来不一样的感悟。 一、图论的发展简史及应用 01图论的诞生:哥尼斯堡七桥问题   十八世纪,在今天俄罗斯加里宁格勒市还被称为哥尼斯堡的年代。像其他许多大城市一样,一条大河(普列戈利亚河)穿城而过。哥尼斯堡除了被一分为二以外,还包含河中的两个岛屿,人们建有七座桥梁连接着不同的陆地。 当时...

【P1195 口袋的天空】

发布时间:2022-11-25 C++ 数据结构 算法 图论
口袋的天空 题目背景 小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空。 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖。 题目描述 给你云朵的个数 N N N,再给你 M M M 个关系,表示哪些云朵可以...

最短路算法

发布时间:2022-11-24 算法 图论
dijkstra算法 除了负值都能用,存图可用邻接矩阵、vector、链式前向星 朴素循环 #include <bits/stdc++.h>using namespace std;const int N = 1e5 + 5;int head[N];int n, m, s;struct node { int to, nex, val;} arr[N];int tot = 0;int dis[N];bool vis[N];void add(int u, int v, int c) { arr[++...

【POJ No. 1330】 最近公共祖先 Nearest Common Ancestors

发布时间:2022-11-24 算法 正经做题 图论
【POJ No. 1330】 最近公共祖先 Nearest Common Ancestors 北大OJ 题目地址 【题意】 一棵树如下图所示,每个节点都标有{1,2, …, 16}的整数,节点8是树根。 若节点x 位于根和y 之间的路径中,则x 是y 的祖先,节点也是自己的祖先。8、4、10和16是16的祖先,8、4、6和7是7的祖先。若x 是y 的祖先和z 的祖先,则x 被称为y和z 的公共祖先,因此8和4是16和7的公共祖先。若x 是y 和z 的公共祖先并且在它们的公共祖先中最接近y 和z ,则x...

Dijkstra算法讲解

Dijkstra算法 它是贪心算法实现的,首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓松弛,就是遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近就更新距离,这样遍历完所有点之后就存下了起点到其他所有点的最短距离。 代码实现: #include<bits/stdc++.h>#define Inf 0x3f3f3f3fusing namespace std; int map[1005][1005]; int vis[1005],dis[1005];in...

07-图6 旅游规划

发布时间:2022-11-25 旅游 算法 # 浙大MOOC题目集 图论
07-图6 旅游规划 分数 25 作者 陈越 单位 浙江大学 有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。 输入格式: 输入说明:输入数据的第1行给出4个正整数N、M、S、D,其中N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N−1);M是高速公路的条数;S是出发地的城市编号;D是目的地的城市编号。随后的M行中,每行给出一条...

Floyd算法

发布时间:2022-11-25 C++ 算法 # 图论 图论
AcWing 854. Floyd求最短路 题目 https://www.acwing.com/problem/content/description/856/ 给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。 再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出 impossible。 数据保证图中不存在负权回路。 思路 Floyd算法:动态规划的思想 状态表示:f[k][i][j]表示考虑经过前k个点,从i到...

算法提升:图的盲目搜索算法(DFS、BFS、DFS-ID)

发布时间:2022-11-26 算法 深度优先 图论
目录 概念 BFS DFS DFS-ID 概念 盲目搜索算法指的是不使用领域知识的不知情搜索算法。主要包括三种算法:深度优先搜索(DFS)、广度优先搜索(BFS)和迭代加深(DFS-ID)的深度优先搜索。 当树很深、分支因子不大、在树中解出现的位置相对较深时,选择深度优先搜索。 当搜索树的分支因子不太大、在树中解出现的位置在合理的深度级别、路径不是非常深的时候,选择广度优先搜索。 在深度优先和广度优先的基础上,结合二者形成了一种全新的算法:迭代加深的深度优先 PS: 简单的说就是不断扩大搜索深度的深...

图算法——求最短路径(Dijkstra算法)

发布时间:2022-12-02 数据结构 算法 图论
       目录 一、什么是最短路径 二、迪杰斯特拉(Dijkstra)算法  三、应用Dijkstra算法 (1) Dijkstra算法函数分析         求图的最短路径在实际生活中有许多应用,比如说在你在一个景区的某个景点,参观完后,要怎么走最少的路程到你想参观的下个景点,这就利用到了求图最短路径的算法。求图的最短路径有很多算法,这里介绍一种迪杰斯特拉(Dijkstra)算法来求图的最短路径。         在介绍算法前,需要掌握一点图的基本知识,比如说什么是路径,什么是路径长度等。如果对这...

最小生成树 & Kruskal算法 - 习题

发布时间:2022-11-24 算法 图论
P3366 【模板】最小生成树 传送门 #include<bits/stdc++.h>#define MAXN 200005using namespace std;struct myEdge{ int u,v;//两个端点 int w;//权 myEdge(){} myEdge(int p1,int p2,int quan):u(p1),v(p2),w(quan){}}e[MAXN];int cnt;//边数int p[MAXN];//点u的父亲节点int n,m;//点数,边数int f...

===图论-知识点部分===(持续更新)

发布时间:2022-11-24 算法 图论
图的存储 (1)直接储存 这种方法就是直接储存边。 常用于需要排序边的场景(如Kruskal算法) struct myEdge{ int u,v;//两个端点 int w;//权 myEdge(){} myEdge(int p1,int p2,int quan):u(p1),v(p2),w(quan){}}e[MAXN];int cnt;//边数void ReadEdge(){ int a,b,w; cin>>a>>b>>w; e[++cnt] = myEdge(a...