文章目录一、今日刷题1.题目2.分析3.代码①暴力破解②链表存储法③无需链表的复杂度最佳解法一、今日刷题1.题目搜索名人假设你是一个专业的狗仔，参加了一个n人派对，其中每个人被从0到n-1标号。在这个派对人群当中可能存在一位“名人”。所谓“名人”的定义是：其他所有n-1个人都认识他/她，而他/她并不认识其他任何人。现在你想要确认这个“名人”是谁，或者确定这里没有“名人”。而你唯一能做的就是问诸如“A你好呀，请问你认不认识B呀？”的问题，以确定A是否认识B。你需要在（渐近意义上）尽可能少的问题内来确定这位“名人”是谁（或者确定这里没有“名人”）。在本题中，你可以使用辅助函数boolknows(a

本篇博客将考察各种最短路径问题。    无权最短路径    Dijkstra算法    具有负边值的图    无圈图    所有顶点对间的最短路径    最短路径的例子–词梯游戏输入是一个赋权图：与每条边(vi,vj)相联系的是穿越该边的开销（或称为值）ci,j。一条路径v1v2……vN的值是这叫作赋权路径长(weightedpathlength)。而无权路径长只是路径上的边数，即N-1。单源最短路径问题(Single-SourceShortest-PathProblem)：给定一个赋权图G=(V,E)和一个特定顶点s作为输入，找出从s到G中每一个其他顶点的最短赋权路径。例如，在图1中，从v1

哈密顿路1、哈密顿路定义设G=为一图（无向图或有向图）哈密顿路：是指不重复的走过图G中所有的点，则构成哈密顿通路。不重复：节点且只经过一次。哈密顿回路：是指不重复的走过图G中所有的点，并且回到起点。哈密顿图：若G中存在哈密顿回路，则称它是哈密顿图2、哈密顿图条件：注意：目前没有找到哈密顿图的简单的充要条件哈密顿图的必要条件：若G=(V,E)是一个哈密顿图，则对于V的每一个非空子集S，均有W(G－S)≤|S|。其中|S|是S中的顶点数，W(G－S)表示图G擦去属于S中的顶点后，剩下子图的连通分支的个数。（1）该图去掉s个顶点之后的分支数一定小于等于去掉的顶点数s，若不满足一定不是哈密顿图。（2）

文章目录最小生成树普里姆算法实现过程代码实现最小生成树什么是最小生成树?对于如图所示的带权无向连通图来说：从图中任意顶点出发，进行dfs或者bfs便可以访问到图中的所有顶点，因此连通图中一次遍历所经过的边的集合以及图中所有顶点的集合就构成了该图的一颗生成树。其中把具有权之和最小的生成树叫做最小生成树。如图中：红色线表示的就是这棵树的最小生成树。最小生成树可以应用到许多实际生活中，比如说求用尽可能小的造价修建若干条高速公路，求n个城市连接在一起的最短路径等等。。普里姆算法普里姆算法是一种构造性算法，用于求得一个带权无向连通图的最小生成树。普里姆算法规定：G=(V，E)是一个带权无向联通图。V表示

图论1.自反与反自反2.对称与反对称3.传递与非传递1.自反与反自反自反：相同顶点都在集合内。反自反：相同顶点都不在集合内。参考下图：有三部分，红色的自反，蓝色的反自反，以及白色的都不是。例1：V={1,2,3,4}V=\{1,2,3,4\}V={1,2,3,4}，判断下列集合是否自反。R1={,,}R_1=\{,,\}R1​={1,1>,3,3>,4,4>}R2={,,,,,}R_2=\{,,,,,\}R2​={1,1>,2,2>,3,3>,4,4>,1,3>,2,4>}R3={,,,}R_3=\{,,,\}R3​={1,3>,1,2>,2,3>,1,4>}解：R1R_1R1​有相同顶点，但

🎈作者：Linux猿🎈简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！🎈关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀🎈欢迎小伙伴们点赞👍、收藏⭐、留言💬目录一、什么是最小生成树？

Kruskal算法主要内容一、基本思路1、基本思想与概念2、算法步骤3、注意二、Java、C语言模板实现三、例题题解一、基本思路1、基本思想与概念解决问题：多个城市中铺公路，使城市之间可以相互联通，问如何才能让铺设公路的长度最短——铺设的路径即为最小生成树。思想：从小到大枚举每条边，从小到大试图将每条边假如生成树，只要这条边对应的两个点不在一个集合，则把这条边加到集合中来。主要面对的是稀疏图的最小生成树问题使用并查集来进行同一集合的判断。2、算法步骤将所有边按照权重进行从小到大排序（快排）——O（mlogn）算法瓶颈枚举每一条边a，b，权重cif（a,b不连通）{将这条边加入集合中，相当于给a

1.图相关的算法图中一个最常见的操作是，通过一个点遍历它的临边。（1）邻接矩阵：时间复杂度为O(V)。（2）邻接表：由于每一行本来存储的就是连接的点，所以可以直接找到。当然，以上操作将g这个图设置成public变量就可以实现，但是如何维护g仍然为private变量呢？因为，这样从设计模式角度来讲是更好的，外界用户无法修改g这个图，当然可以使用一个函数，但是需要将数据复制一份，这样不是太好的，更好的方法呢？使用迭代器。迭代器将具体实现隐藏了，这样稀疏图和稠密图的接口就可以保持一致。代码如下：SparseGraph.h#ifndefVERTEX_ADJACENT_ITERATOR_SPARSEGR

同构是在数学对象之间定义的一类映射，它能揭示出在这些对象的属性或者操作之间存在的关系。若这两个数学结构之间存在同构映射，那么这两个结构叫做是同构的。一般来说，如果忽略同构的对象的属性或操作的具体定义，单从结构上讲，同构的对象是完全等价的。----Wikipedia同构图：假设G=(V,E)和G1=(V1,E1)是两个图，假设存在一个双射m:V—>V1，使得对全部的x,y∈V均有xy∈xy∈E等价于m(x)m(y)∈E1，则称G和G1是同构的。上图中，G和G1是同构的，因为：1.从G的结点到G1的结点，存在一个一对一的映射函数f(one-to-oneontofunctionf)2.从G的边到G1

文章目录最短路:建图！1单源最短路：求一个点到其他所有点的最短路1.1所有边权都是正数(1)朴素的Dijkstra算法（On^2）（2）堆优化版的Dijkstra算法（Omlogn）1.1存在负权边（1）Bellman--FordO（nm）（2）SPFA一般：O（m），最坏O（nm）2.多源汇最短路：起点和终点不确定Flod算法O（n^3）最短路:建图！源点—起点汇点—终点约定n为点数，m为边数1单源最短路：求一个点到其他所有点的最短路1.1所有边权都是正数(1)朴素的Dijkstra算法（On^2）例题：Dijkstra求最短路I代码：#include#include#includeusin