文章目录离散数学与组合数学-04图论4.1图的引入4.1.1图的示例4.1.2无序对和无序积4.1.3图的定义4.2图的表示4.2.1集合表示和图形表示4.2.2矩阵表示法4.2.3邻接点与邻接边4.3图的分类4.3.1按边的方向分类4.3.2按平行边分类4.3.3按权值分类4.3.4综合分类方法4.4图论基础-子图和补图4.4.1子图4.4.2完全图4.4.3补图4.5图论基础-握手定理4.5.1结点的度数4.5.2握手定理4.5.3图的度数序列4.6图论基础-图的重构4.6.1引言4.6.2图的同构定义4.6.3图同构的必要条件4.7图论基础-通路和回路4.7.1通路和回路的概念4.7.2
1.前言最近在看《算法图解》，其中第七章狄克斯特拉算法个人感觉并没有讲的清楚，比如看完7.1节给人的感觉是狄克斯特拉算法会遍历图中的每一条边，后续狄克斯特拉不适用负权边的说法就站不住脚了。后续在查阅诸多资料之后，总结文章一篇，尽可能以通俗易懂且思路清晰的方式来讲解狄克斯特拉算法。2.简介狄克斯特拉算法用于寻找在加权图中前往目标节点的最短路径，加权图是对边进行加权的图。2.1.定理设想这样一个场景——在一个没有负权边的有向图中，如果从起点直接到节点A的开销小于从起点直接到节点B的开销，那么即使从起点出发经过节点B还有其他路径可以到达节点A，其总开销也会大于从起点到节点A的开销。比如在上图中，起点
1.前言最近在看《算法图解》，其中第七章狄克斯特拉算法个人感觉并没有讲的清楚，比如看完7.1节给人的感觉是狄克斯特拉算法会遍历图中的每一条边，后续狄克斯特拉不适用负权边的说法就站不住脚了。后续在查阅诸多资料之后，总结文章一篇，尽可能以通俗易懂且思路清晰的方式来讲解狄克斯特拉算法。2.简介狄克斯特拉算法用于寻找在加权图中前往目标节点的最短路径，加权图是对边进行加权的图。2.1.定理设想这样一个场景——在一个没有负权边的有向图中，如果从起点直接到节点A的开销小于从起点直接到节点B的开销，那么即使从起点出发经过节点B还有其他路径可以到达节点A，其总开销也会大于从起点到节点A的开销。比如在上图中，起点
CBS实例以下将通过一个简单的实例体现CBS的基本过程：讲解：上层结点：指的是每个”小方格“；节点：树的节点；(ai,aj,s,t)：ai与aj在t时刻都在s结点上；OPENcbs：存放待探测的状态，与下层的OPEN意思一样，都是将下一步（某时刻）可能要走的结点存放进来；N：为结点；N.constraints：一个约束集，包含对问题中所有Agent的约束；（我们要做的就是在某个结点上给定的约束集中，帮Agent规划避开在该结点的约束集后的其最佳路线）；N.solution：问题的一个解，这个解可能不是有效的，但是这个解中所有的Agent的路径都满足该结点的约束集中的约束；（看例子：在节点1，我
CBS实例以下将通过一个简单的实例体现CBS的基本过程：讲解：上层结点：指的是每个”小方格“；节点：树的节点；(ai,aj,s,t)：ai与aj在t时刻都在s结点上；OPENcbs：存放待探测的状态，与下层的OPEN意思一样，都是将下一步（某时刻）可能要走的结点存放进来；N：为结点；N.constraints：一个约束集，包含对问题中所有Agent的约束；（我们要做的就是在某个结点上给定的约束集中，帮Agent规划避开在该结点的约束集后的其最佳路线）；N.solution：问题的一个解，这个解可能不是有效的，但是这个解中所有的Agent的路径都满足该结点的约束集中的约束；（看例子：在节点1，我
第一题、最大岛屿面积 力扣题目链接classSolution{private:intcount;intdir[4][2]={0,1,1,0,-1,0,0,-1};voiddfs(vector>&grid,vector>&visited,intx,inty){for(inti=0;i=grid.size()||nexty=grid[0].size())continue;if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){visited[nextx][nexty]=true;count++;dfs(grid,visited,nextx,nexty);
总结：本场比赛总共A了两题，主要是因为是在课上做的，老师一直比比个不停，还让关上手机电脑，静不下心去做，做题感觉很差AAXorBProblem两个数异或和为零则两个数相等！！！思路：使用数组记录每个数的个数，可以先输入，然后再对数组进行逐个遍历，可通过计算得出数对个数等于每个数的平方和。也可以边输入边处理，每输入一个数便更新数对的结果数赛场AC代码：#include#include#defineintlonglongusingnamespacestd;inta[100005];intb[114520];signedmain(){ intn,ans=0; cin>>n; for(inti=1;i
总结：本场比赛总共A了两题，主要是因为是在课上做的，老师一直比比个不停，还让关上手机电脑，静不下心去做，做题感觉很差AAXorBProblem两个数异或和为零则两个数相等！！！思路：使用数组记录每个数的个数，可以先输入，然后再对数组进行逐个遍历，可通过计算得出数对个数等于每个数的平方和。也可以边输入边处理，每输入一个数便更新数对的结果数赛场AC代码：#include#include#defineintlonglongusingnamespacestd;inta[100005];intb[114520];signedmain(){ intn,ans=0; cin>>n; for(inti=1;i
解题思路最小生成树（Kruskal算法）不同的的最小生成树：不是连通的权重最小；而是连通起始点和终点的路径上最大最小速度比值最小。如何使得速度比值最小：问题1：什么情况下比值最小？（1、3、5、4、2）⇒(1、2、3、4、5）（1、3、5、4、2）\Rightarrow(1、2、3、4、5）（1、3、5、4、2）⇒(1、2、3、4、5）问题2：直接基于Kruskal算法构建生成树，算该连通图中的最小比值是否可行？步骤：1、按Kruskal算法思路，按路径值排序；2、从最短边开始基于并查集构建最小生成树；3、添加边，当起始点和终点连通，计算速度比值；4、从第二短边重新基于并查集构建最小生成树，重
题目描述一个有n个结点的无向连通图，这些结点以编号：1、2、……n进行编号，现给出结点间的连接关系。请以结点1为起点，按广度优先搜索（bfs）、优先访问小编号结点的顺序遍历并输出该图。输入第一行为两整数，n和e，表示n个顶点，e条边；（2以下e行每行两个数，表示两个结点是联通的。输出只有一行，为节点按照广度优先、小编号结点优先访问的结果。样例输入5712131424253545样例输出12345参考代码：邻接矩阵：#includeusingnamespacestd;#defineN15intn,e,x,y;intq[15],hh,tt=1;boolg[N][N];boolk[N];voidbf
