不带三角剖分的欧式最小生成树
我一直在浏览有关使用Delaunay三角剖分技术找到EMST(Euclidean MST)的文章，但同时也读到可以通过扫掠线算法找到EMST的地方.因为这样做会更容易实现，所以我想实现它而不是使用现有的库. 任何人都可以引导我/将我定向到具有该算法说明的(可能是免费的)论文/资源的链接吗? 解决方案 来自此和此应该可以帮助您入门.他们都使用扫掠线算法来获取MST.
..
graph-algorithm相关内容
是什么使数据结构递归?
我正在阅读有关递归数据类型，该引用具有以下引号: 在计算机编程语言中，递归数据类型(也称为递归定义，归纳定义或归纳数据类型)是可能包含相同类型其他值的值的数据类型 我了解链表和树可以是递归数据类型，因为它包含相同数据结构的较小版本，例如树可以具有子树. 但是，这让我真的很困惑，因为固定大小的数组还不包含子数组吗?仍然是同一类型? 有人可以举例说明什么使数据结构递归吗?
..
查找与Python中某个字符串相关的所有元组
我正在尝试查找与字符串相关的所有元组，而不仅仅是与之匹配的元组. 这是我做的: from itertools import chain data = [('A','B'),('B','C'),('B','D'),('B','F'),('F','W'),('W','H'),('G','Z')] init = 'A' filtered_init = [item for item in dat
..
在R中获取连接的组件
我有一个值为0或1的矩阵，我想获得一个相邻的1的组的列表. 例如矩阵 mat = rbind(c(1,0,0,0,0), c(1,0,0,1,0), c(0,0,1,0,0), c(0,0,0,0,0), c(1,1,1,1,1)) > mat [,1] [,2] [,3] [,
..
确定无向图是否为树的最佳算法
确定无向图是否为树的最佳算法的时间复杂度是多少? 我们可以说有n个顶点的Big-oh(n)吗? 解决方案 是的，它是O(n).在有向图中进行深度优先搜索时，具有3种类型的非树边缘-交叉，向后和向前. 对于无方向情况，唯一的非树边缘是后边缘.因此，您只需要搜索后边缘. 简而言之，选择一个起始顶点.遍历并继续检查遇到的边缘是否为后边缘.如果您找到n-1个树的边缘却没有找到后边
..
Python连接的组件
我正在为类Graph编写函数get_connected_components: def get_connected_components(self): path=[] for i in self.graph.keys(): q=self.graph[i] while q: print(q) v=q
..
从边列表构造邻接列表?
在图算法的上下文中，通常为我们提供图的方便表示形式(通常作为邻接表或邻接矩阵)以进行操作. 我的问题是，从给定的所有边列表中构造邻接表的有效方法是什么? 出于这个问题的目的，假设边是元组的列表(如python)，并且(a，b)表示从a到b的定向边. 解决方案 itertools.groupby的组合(from itertools import groupby edges = [
..
图论。如何解决这类问题？我想知道在尝试解决此问题时需要思考的逻辑和方式。
在笛卡尔平面上找到从（0，0）到（n，n）的路径数，该路径数永远不会超过y = x线。可以沿着路径进行三种类型的移动： 向上移动，即从（i，j）移至（i ，j + 1）; 向右移动，即从（i，j）移至（i + 1，j）； 右移，即从（i，j）到（i + 1，j + 1） 解决方案 路径计数101 首先，我们解决一个简单的问题： 用以下方法查找笛卡尔平面
..
有向图线性算法
我想知道使用动态规划在线性时间内计算顶点s与图形的其他每个顶点之间的最短路径长度的最佳方法。 图形为加权DAG。 解决方案 您可以期望的是一种在边和顶点数量上呈线性的算法，即 O （| E | + | V |），也可以在负权重的情况下正常工作。 这是通过首先计算拓扑来完成的 一些表示法：我们称 d'（s，v） 从 s 到 v 和 d（u ，v）从 u 到 v 的弧的长度/
..
确定从s到t的所有最短路径是否都包含边e
让G =（V; E）是一个有向图，其边缘全部具有非负权重。令s，t为V中的2个顶点，令e为E中的边。 描述一种算法，该算法确定从s到t的所有最短路径是否都包含边e。 好吧，这就是实现Dijsktra时间复杂度的方法： 只需从s运行Dijkstra并计算delta（s，t）（从s到t的最短路径的权重）。 删除边e，然后从新图中的s重新运行Djikstra。 如果新图中的delta（s，
..
为什么Dijkstra的算法使用堆（优先级队列）？
我曾尝试在不使用优先级队列（堆）的情况下在循环加权图上使用Djikstra的算法，并且该算法有效。 维基百科指出，该算法的原始实现不使用优先级队列，并且运行时间为O（V 2 ）。 现在，如果我们只是删除优先级队列并使用普通队列，运行时间是线性的，即O（V + E）。 有人可以解释为什么我们需要优先级队列吗？ 解决方案 我有完全相同的疑问，并找到了一个测试用例，其中没有pr
..
单连接图？
一个单连通图是一个有向图，它最多有 个从u到v∀u，v的路径。 考虑以下解决方案： 从任何顶点运行DFS。 现在再次运行DFS，但这一次是从顶点开始，以减少完成时间的顺序。仅对某些先前的DFS中未访问的顶点运行此DFS。如果在同一组件中找到交叉边缘或在前边缘中，则该交叉边缘不是单个连接的。 如果所有顶点均已完成且前边缘没有交叉，则将它们单独连接。 O（V + E） 这是
..
找到不属于任何树木直径的边缘
我很好奇是否有一种快速的方法来查找是否存在一个边缘，该边缘不是n元树的任何可能直径的一部分。例如，在下面的树中，A-B边缘将不是任何直径的一部分。 我尝试列出所有可能的方法直径，但这会花费很多时间，而且我敢肯定有一种更快的方法。 解决方案 让我们从一个一个更简单的问题：我们将如何找到树的任何直径？一种方法是选择一个节点，然后在该节点处植树。然后可以通过以下两种方式之一找到图形的直径：
..
如何更改要遍历的结构？
此问题是由此CodinGame难题提出的。 我正在使用Dijkstra的方法实现基本的寻路算法。它使用边界 HashMap和完成 HashMap来保存与寻路相关的节点信息。在一个特定的循环中，我在边界中找到价值最高的节点，删除该节点，然后将该节点添加到完成 ，并在 boundary 中添加/更新节点的邻居信息。 尝试变异边界在循环时使Rust的借阅检查器变得不容易，但是循环的逻辑对我来
..
除了邻接表或邻接矩阵之外，是否还有其他数据结构来表示图？
我一直在寻找用于表示图的不同数据结构，因此遇到Nvidia CUDA Toolkit，并在source_indices，destination_offsets的帮助下找到了一种表示图的新方法。 对图的这种创新表示方式着迷，我寻找了其他表示图的方式。但是没有发现任何新内容。 我想知道是否有其他方法来表示图而不是邻接矩阵或列表... 解决方案 我想知道除邻接矩阵或列表之外，是否
..
我们可以使用Union-Find数据结构检测有向图中的周期吗？
我知道可以使用DFS和BFS在直接图中检测周期。我想知道是否可以使用 Union-Find 检测有向图中的循环？ 如果是， ，那又如何？和 如果不能，为什么？ 解决方案 否，我们不能使用联合查找来检测有向图中的循环。这是因为不能使用不交集（执行联合查找的数据结构）表示有向图。 当我们说“联合b”时我们无法确定边缘的方向 是去b了吗？ （或） b是要去a吗？ 但是
..
马尔可夫聚类
准确地说，我有两个问题。首先，我想知道是否有一种简便的方法来适应马尔可夫聚类算法，以便我可以提前指定到底要多少个聚类。如果没有，您会推荐哪种类似算法？ 其次，应该如何处理马尔可夫世界中重叠的簇？ 解决方案 1）。没有简单的方法来适应MCL算法（注意：它的名字是“马尔可夫聚类算法”，不带“ ing”。很多人像在“进行马尔可夫聚类”中那样说出来，以输出指定数量的聚类） 。我认为，在99.
..
500+个航路点/节点的最短路径算法(例如Dijkstra)?
我在这里询问了最短路径算法: 2D航路点寻路:将WP组合到从curLocation转到targetLocation (要了解我的情况，请同时阅读该问题和该问题.) 看来Dijkstra最短路径算法将能够满足我的需要.但是，我的路线图中大约有500到1000个节点. 到目前为止，我所看到的实现将节点的数量限制在50个以下.我的问题是:我是否仍应使用Dijkstra最短路径算法或替代
..
检测图中的相互边缘
我有一个图的邻接列表表示形式，但它不是对称的，即.如果节点A具有B的边缘，则B具有带有A的边缘并不正确.我想这将是一个有向图(有向图). 从节点检测所有双向路径的好方法是什么.我知道我可以使用DFS来检测从一个节点到该图的另一个节点的路径.我猜我正在寻找的是双向DFS，其中仅考虑了双向边缘. 因此，一种方法是查看节点的邻居并弄清楚这是否是双向关系.但是，为此，我将需要遍历此相邻节点的所
..
图算法:邻接图的可达性
我有一个依存关系图，我已经将其表示为Map>(用Java讲，或者说f(Node n) -> Collection[Node]作为函数；这是从给定节点n到依赖于它的节点集合的映射) n).该图可能是循环的*. 给出节点列表badlist，我想解决 可达性问题 :即生成一个Map> badmap，该Map
..