2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
1回答
当图有多个连通分量时，我不知道如何实现Kruskal算法
根据我对Kruskal算法的理解，它多次向集合中添加最小边。然后，当所有的边都被检查时，它会返回一组最充分的边。
但是，如果我的图是断开的呢？说我有：
A - B - C - D
E - F
假设成本( are )=成本(E)= 1，其余的边大于1。
当我运行Kruskal时，我会得到所有的边的成本，但是我想得到每个连接组件的成本，所以我对所有连接的组件做了一个平均最小的成本。
浏览 0提问于2014-03-07得票数 3
1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
1回答
这个问题是我先前提出的类似问题的延续：。
问题摘要：我需要找到图中从顶点A到顶点B的最佳路径，假设路径质量是以路径上边权的最小值来计算，其次是具有最大最小值的最佳路径。通常情况下，它被称为。
以前我需要用非常小的图(最多15个顶点)来解决这个问题，所以我不需要复杂的算法，而且在友好的人的帮助下，我设计了我的工作算法。不幸的是，现在我需要重新定义我的需求，使我的图形可以非常大(甚至5万条边)。我知道我需要为我的图找到最大生成树，并在得到的MST中从开始到停止得到一个简单的路径。我决定使用库。它已经实现了。通过将每个边权乘以(-1)，用Kruskal表示最小生成树，就可以得到最大生成树，但该库中的
浏览 2提问于2013-09-04得票数 0
3回答
博鲁夫卡算法()是否只适用于无向图？
例如，如果我们有一个图结构，如下所示：
node 1 -> node 2 (weight 1), node 3 (weight 1), node 4 (weight 1)
node 2 -> node 3 (weight 2)
node 3 -> node 4 (weight 2)
node 4 -> node 2 (weight 2)
那么最小生成树应该包括边：
1 -> 2
1 -> 3
1 -> 4
然而，Boruvka的算法会吐出
1 -> 2
2 -> 3
3 -> 4
因
浏览 1提问于2012-12-11得票数 2
我希望能够将我的图分成子组件，这样删除任何单个节点都不会创建更多的子组件(不包括单个节点)。作为示例，请参见下面的两个图像。
第一个图像显示了完整的图形。第二幅图显示了将图形拆分为尽可能小的子组件时的子组件。从第二幅图中可以看出，顶点名称已被保留。我不需要新的结构是一个单独的图，它可以是一个图的列表，甚至是每个组件中的节点的列表。
节点4-5-6的组件仍然存在，因为移除这三个节点中的任何一个都不会创建新的组件，因为被断开的节点将只是单个节点。
目前，我正在尝试组合一个迭代过程，以升序顺序删除节点，并递归到生成的新组件中。然而，这是困难的，我想以前有人做得更好。
浏览 13提问于2019-03-27得票数 0
回答已采纳
我想在无向图中找到一个强连通的组件，也就是说，如果我从一个节点A开始，那么我将返回到节点A，并且每条边都被访问一次。
对于有向图，可以使用Tarjan的算法求强连通分量，但如何处理无向图。
浏览 5提问于2017-06-16得票数 3
2回答
我试图找到一个算法，在一个无向连通图中找到子图，其中子图中的每个顶点与子图中的每一个顶点都有一条边。
我真正的问题是我很难对这个问题进行分类，这样我就可以研究可能的算法或解决方案。
有人知道这个问题叫什么吗?或者是否有任何现有的算法可以实现这一点？
浏览 3提问于2014-06-18得票数 1
回答已采纳
1回答
反向删除算法:从包含所有边的图开始。然后按权重的递减顺序重复通过边缘。对于每条边，检查删除该边是否会断开该图的连接；如果不会，则删除它。
如何证明此算法计算MST？
浏览 3提问于2020-03-27得票数 0
1回答
问题是给定一个加权边双向图，找出边的集合，通过删除给定的一组节点彼此断开连接的边。而且这些边权重的和也应该是最小的。这个问题有什么名字吗？有没有什么特别的算法来解决它们？我知道这一定是NP完全问题。
浏览 1提问于2012-04-27得票数 1
回答已采纳
算法设计手册中的练习
6-10。4.设G= (V，E)是无向图。一个边的集F⊆E称为反馈边集，如果G的每个圈在F (b)中至少有一个边，设G是一个带正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0提问于2014-11-05得票数 1
3回答
有没有人知道如何改变prim的算法，从而处理一个没有连通的图？我知道我必须使用森林，但我不知道如何在Haskell中实现它。
浏览 3提问于2011-12-12得票数 0
1回答
我有一个包含多个小子图的图。目标是将一个子图的所有蓝色节点标记为红色当且仅当该子图中的所有节点都是蓝色的。如果一个子图中的一个节点有不同的颜色，绿色，那么我们不会改变该子图中节点的颜色。
这是我使用的查询：
MATCH (a:BLUE) WHERE NOT (a)-[*]-(:GREEN) WITH a LIMIT 10000 SET a:RED REMOVE a:BLUE
这是查询前后的处理方式：
问题在于它速度慢，因为它需要多次遍历相同的子图。例如，：
若要将A标记为红色，则需要遍历A。再一次，为了标记B，它需要穿越again。同样，标记C也是如此。
我想知道是否有任何方法可以一次一
浏览 6提问于2017-06-23得票数 3
回答已采纳
1回答
一种将大区域分割为凸多边形的算法
、、、、
我正在将A*寻路算法实现到一个基于网格的引擎中，但我想在多边形区域中创建节点，而不仅仅是使用网格点。
在这个区域会有障碍物，不应该被移动。
我在想，有没有什么算法可以把一个有障碍物的较大区域分割成一个具有尽可能少的连通凸多边形的图？
浏览 15提问于2016-08-17得票数 2
回答已采纳
1回答
我有一个多个“动物笔”的加权图，每个笔至少有3个边/点和至少两个笔。为了连接所有的笔，我必须找出要移除的最小加权边(你可以通过移除没有连接到其他笔的外边来连接它们)。
有人能推荐一种算法或过程吗?我可以用它来找到要移除的最小权重墙。我在考虑Prim的算法，但我甚至不完全确定如何应用它。
这是上的problem S4
我不想要答案，只是想知道如何解决这个问题。
浏览 0提问于2012-02-23得票数 5
回答已采纳
1回答
我试图实现Tarjan的强连通图算法()，这是我的代码，我很困惑为什么顶点4和顶点5也输出为强连通组件？
我使用的是一个非常简单的图表，只有5个节点需要测试。我的代码是用Python2.7编写的。
from collections import defaultdict
class SccGraph:
def __init__(self, vertex_size):
self.out_neighbour = defaultdict(list)
self.vertex = set()
self.visited = set()
浏览 6提问于2017-01-07得票数 1
回答已采纳
3回答
组合优化
、、、
假设我们有一个连通的无向图: G=(V，E)。
连通集的定义:属于G的V的一组点构成一个有效的连通集当且仅当这个组中的每个点都在T-1条边内，T是该组中的点的个数。
请注意，连通集只是G的一个连通子图，没有边，但有点。
我们有一个定义在连通集上的任意函数F，即给定一个任意连通集CS，F(CS)将给我们一个实数值。
如果两个连通集的并不是连通集，则称它们是不相交的。
图中红色、黑色、绿色点集都是有效的连通集，绿色点集与红色点集不相交，黑色点集与红色点集不相交。
现在的问题是:我们想从G中找到一组不相交的连通集，这样：(1)每个连通集至少有K个点。(K是全局参数)。(2)它们的函数值之和，即
浏览 1提问于2010-10-13得票数 7
4回答
最小生成树子图
、、、、
我正在阅读我的书中的所有练习，准备下周复习一次课堂考试，我真的对这个子图问题感到困惑。
目前我的想法使我相信，既然我们已经有了最小生成树G，那么既然我们在最小生成树中有子节点，就必须存在G‘。就目前情况而言，我有点不知所措。
如果X‘的节点集和边集分别是X的节点集和边集的子集，则X’是图X的子图。设(V，T)是G的最小生成树，G‘=(V’，E‘)是G的连通子图。
(a)证明了(V‘，E’∩T)是G‘的最小生成树的子图.
(b)在什么条件下(V‘，E’∩T)是G‘的最小生成树？证明你的主张。
提前谢谢！
浏览 2提问于2012-10-29得票数 4
回答已采纳
4回答
完全断开二部图的连接
、、、、
我有一个不连通的二部无向图。我想完全断开图表的连接。我唯一能执行的操作是删除一个节点。移除节点将自动删除其边。任务是最小化要删除的节点数量。图中的每个节点最多有4条边。
通过完全断开一个图，我的意思是不应该通过链接连接两个节点。基本上是一个空的边集。
浏览 1提问于2012-08-07得票数 4
回答已采纳
1回答
引理1:如果H是图G的子图，则dist_G(u，v)<= dist_H(u，v)。
证明 H中的每条u-v路径也出现在G中，并且G可能有比H中的任意u-v路径更短的u-v路。
引理2:如果H是图G的连通子图，使得V(H)=V(G)，则直径(G)≤直径(H)
证明
直径(G)=最大{dist_G( u，v)}对所有u，v在V(G)中
假设直径(G)= dist_G(x，y)对某些x，y在V(G) = V(H)中
某些a，b在V(H) = V(G)中的直径(H)= dist_H(a，b)
注意，dist_H(s，t) <= dist_H(a，b)适用于V(H)中的所有s
浏览 3提问于2016-07-08得票数 0
假设我们可以构造一个有N个顶点的图，那么图需要的最小边数是多少，这样它就不能有一个交点？换句话说，它需要双管齐下。
一个完整的图显然没有任何的交点，但我们仍然可以删除它的一些边，它可能仍然没有任何。因此，它似乎可以有较少的边数比完整的图。对于N个顶点，我们可以用多种方法构造图。所以这个最小数应该满足所有这些图。
澄清，因为标题是混淆的用户-最小的m(作为一个函数的n)，使每个n-顶点图，至少有m边必然是两个相关的？
浏览 5提问于2014-08-25得票数 2
回答已采纳
1回答
给出了一个有向加权图，它是强连通的。我需要从这个图中找到一个强连通子图，使得最大和最小权边之间的差是最小。
更清楚地说，我需要去除边，这样在去除它们之后，图仍然是强连通的，而最大边和最小权边之间的差是最小。
这里有一个例子：
第一行是图的N个节点数和M个边。下一条M线表示这个图的边。
3 6
1 2 8
2 3 32
3 1 16
1 3 81
3 2 243
2 1 27
选定的N节点子图将包含以下边：
1 2 8
2 3 32
3 1 16
最大边和最小边的差值是:32-8= 24.在所有选择中都是最少的。
我在寻找一个最优的解决方案。最多有3000个节点和5000条边。
浏览 9提问于2021-07-24得票数 2
回答已采纳
3回答
我很难理解MST是否会是一棵树。
假设图G= (V，E)，做连接V中所有顶点且总权重最小的边T⊆E的子集必须是一棵树，或者当-一些边可能有负权时，它是否是其他子图。-所有的边缘都有正的权重。
我在想，对于一些可能有负权的边，它必须是一棵树，对于所有边都有正权的边，它可以是其他一些子图。
如果我是对的还是错的，请帮助我。
如果它一定是一棵树，你能用连接性和最小性来解释矛盾吗？但是如果你认为它可能是其他的子图，那么你能给我举一个例子吗，一个可能不是树的连通图的权重较低。
浏览 3提问于2013-11-11得票数 0
1回答
如果我有一个有一个节点而没有边的图。连通分量的数目= 1，对吗？
如果我有一个有两个节点而没有边的图。连通分量的数目= 2，对吗？
如果我有一个有两个节点和一个边的图。连通分量的数目= 1，对吗？
我有一段代码：
typedef adjacency_list <vecS, vecS, undirectedS> Graph;
typedef graph_traits < Graph >::edge_descriptor Edge;
/* typedef graph_traits<Graph>::vertex_descriptor Vertex;
浏览 2提问于2014-11-18得票数 1
回答已采纳
3回答
如何遍历具有特定属性的树
、、、
我有一棵树，如下所示。
红色意味着它有一个特定的属性，未填充表示它没有它。我想把Red支票降到最低。
如果Red比所有祖先都是Red (不应该再次检查)。
如果Not Red比所有的代名词都是Not Red。
树的深度是d。
树的宽度是n。
注意，子节点的值大于父节点。
- Example: In the tree below,
- Node '0' has children [1, 2, 3],
- Node '1' has children [2, 3],
- Node
浏览 7提问于2013-07-13得票数 0
回答已采纳
例如，顶点之间是否允许多条边？或者，我们可以有从A到B和B到A的两个边吗？我只是想知道我们说的是什么样的有向图。
浏览 1提问于2015-11-08得票数 0
回答已采纳
1回答
我有一个完整的，加权的，无向图。边权值是两个节点之间连接的代价，因此最小生成树是总代价最低的边的子集，使得图保持连通。
MST必须在任何时候都是连接的，但不幸的是，这些连接并不是很可靠，所以我想在这个图形/网络中添加冗余。
是否有可能计算一个边的子集，使总边成本最小化，边连通度超过一定的最小值？
我看得出来，强暴是怎么可能的，但我在寻找更实用的东西。关于这个问题，我没能找到多少，我想主要是因为我没有搜索所需的词汇表。
我目前的想法是：
计算MST
虽然它仍然低于一定的连接性
查找最低于该连接的节点
用最小的权重激活节点的边缘
我没有同时找到某个连通性下面的所有
浏览 0提问于2019-06-27得票数 1
1回答
连通无向无圈图与树
、、、
当我在麻省理工学院的“算法概论”中学习图论的时候，我被介绍了一些关于图和树的定义。
在麻省理工学院对算法第三版书的介绍中，附录树一章向我展示了定理B.2，“自由树的特性”
设G= (V，E)是无向图。以下语句是等价的。
G是一棵免费的树..。
G是无环的，且x-E=V- 1.
是否有一个连通的、无向的、非循环的图不是树的例子？
从理论上讲，如果有一个无向无圈图，它满足了一个条件，那就可以作为例子了吗？
如果有一个例子满足这个条件，你能给我看一下吗？
浏览 4提问于2015-11-17得票数 4
回答已采纳
没有任何限制，你必须跨越每条边，只有一次，或每一个顶点。
图中是否有这样一条路径存在的必要条件和充分性(如欧拉路径存在的节点度)，还是证明有或没有这样一条路径的已知算法(也许从起始路径的所有边求出最小路径)？
我已经考虑了几种可能性，其中最强的是将强连接的组件折叠成单个超级节点，然后检查生成的图是否只是覆盖所有边缘的“链接列表”-like图(这很简单，只是从起始节点/超级节点走过来，总是从当前节点中说出一条边，计算访问时的传出边缘(以及任何内部边缘，如果它是超级节点)，当您到达叶节点时，查看是否所有边都被计数)。在这种解决方案中，保存所有原始边是很重要的，即使它们变得多余(例如，在将连通的分量
浏览 1提问于2013-03-20得票数 2
1回答
给定一个正权重的无向循环图，我如何找到最小的一组要删除的边，从而使该图成为非循环图？算法必须在O((E+V)logV)时间内运行。
我试图解决这个问题，并考虑使用贾克斯特拉的算法(因为它也在O(E+VlogV)时间内运行，但我不确定如何前进。
浏览 5提问于2021-06-08得票数 1
我们知道对于不相交的集合有“并和查找”。
但是如何进行反向操作呢？考虑一个由E条边连接的N个节点的集合(这实际上是一个图)。在每一步，我们要删除一些边，并检查这个删除操作是否会导致另一个不相交的集合。有没有可能像"Union and find“中那样快速完成呢？
附言:这不是家庭作业，我们有假期:)
浏览 2提问于2011-06-22得票数 13
回答已采纳
2回答
我对Kruskal算法有个理解上的问题。以下是代码
#include <stdio.h>
#define MAX_VERTICLES 100
#define INF 1000
int parent[MAX_VERTICLES];
int num[MAX_VERTICLES];
void setInit(int n) {
int i;
for (i = 0; i < n; i++) {
parent[i] = -1;
num[i] = 1;
}
}
int setFind(int vertex) {
int
浏览 15提问于2017-01-12得票数 0
1回答
有人知道这个算法吗，因为我正在考虑使用它，但我不确定它是否真的满足我的所有要求。所以基本上，我想要做的是将一个图分成几个子图。然而，每个子图的节点应该是连接的，也就是说，不应该是这样的情况，例如，如果我想到达节点x，我必须通过另一个子图。而这正是我所关心的。有没有可能，当我用Kernighan-Lin算法分割一个图时，子图的节点会分散在各处？
浏览 28提问于2013-07-08得票数 1
2回答
有没有一种算法，当给定一个图时，计算该图的顶点连通性(为了将该图分成两个连接的图而要删除的最小顶点数)。(请注意，该图可能已断开连接)。谢谢!
浏览 1提问于2013-04-14得票数 2
回答已采纳
2回答
我想把有向图中的一个单连通分支定义为一个子图，其中对于每一对节点u和v，存在一条从u到v或从v到u的路径。它还应该具有这样的性质，即它不是另一个单连通分支的子图。
我知道如何找到弱连接组件和强连接组件。如何找到单连接的组件？
一种非常低效的方法可能会从每个节点进行广度搜索，以查看可以从每个节点到达哪些节点，并尝试从这些节点集以某种方式计算组件。
浏览 2提问于2013-07-21得票数 0
回答已采纳
2回答
我正在为面试做练习，我在Glassdoor上发现了以下问题。
Given a board with black (1) and white (0), black are all connected. find the min rectangle that contains all black. An example given is
0 0 0 0 0
0 1 1 1 0
0 1 1 0 0
0 1 0 0 0
0 0 0 0 0
这个问题挑战了我对连通性的理解，下面矩阵中的1会被认为都是相互连接的吗？
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 1 1
浏览 2提问于2014-03-24得票数 2
假设我们有一个有向图，它不是一个完整的图，并且有多个SCC。我想知道，如果我们转换图并使用Kosaraju算法，强连通组件的模式是否会发生变化？说“转图”，我指的是翻转边的方向。如果我们试图在转置/反置图中而不是原来的图中找到SCC，我们发现的SCC会有所不同吗？
我提出了这个问题，因为我误解了SCC的算法，并在我的转置/反转图上运行它。我得到的是相同的SCC正确的答案/运行Kosaraju的算法。它普遍适用于所有的图表吗？
浏览 2提问于2013-11-20得票数 0
回答已采纳
2回答
我正在使用对JS中的图执行拓扑排序。问题是，在极少数情况下，图中会包含圈。这些都是结构的次要部分，因此丢弃一些边缘不会对最终结果产生太大影响。然而，当它们出现时，算法就会中断。更新它的最有效方法是什么，这样如果有一两个周期，它就不会崩溃？
浏览 3提问于2013-08-17得票数 1
2回答
来自
有向图被称为弱连通图，如果用无向边替换它的所有有向边产生一个连通(无向)图
这个准确吗？
上面的图是连通的，当所有有向边都被无向edges.But替换时，B到D或D到B之间没有路径，这违反了弱类型的property..Am I，对吗？
浏览 2提问于2013-09-06得票数 4
回答已采纳
1回答
有效地找到所有连通导出子图
、、、、
是否有一个有效的(*)算法来寻找一个连通的无向顶点标号图的所有连通(诱导)子图？
(*)我理解，在一般情况下，任何这样的算法都可能有O( 2^n )的复杂度，因为对于一个团(Kn)，有2^n个连通子图。但是，我通常处理的图的连通子图要少得多，所以我正在寻找一种方法来生成它们，而不必考虑所有2^n个子图并丢弃那些不连通的子图(就像在的解决方案中一样)。
一个算法的运行时间与解决方案的数量呈线性关系(即它可以直接从图的结构生成解决方案，而不会浪费时间考虑所有非解决方案)，这显然是理想的。在节点数中增加一个多项式的步骤也是可以的(例如，预先计算图的传递闭包--我认为这在这种情况下不会有帮助)。
或者
浏览 3提问于2013-03-27得票数 12
回答已采纳
3回答
有人知道解决以下问题的算法吗？
给定一个无向连通图，找出两个不同的边可以被切成不连通的方式的数目。
我认为问题的一部分(我知道一种算法)是计算一条线可以被切成断开的方式的数目。然后计算如何将这些行与其他行分组，得到值(M-K)*K + K*(K-1)/2，M = no。边的K = no。一次切边。
我不知道该怎么做的部分是找到切割2条线的其他方法的数量，例如，在只有循环1 - 2 - 3 - 1的图中，任何边的组合都是切割线使图形断开的有效方法。
我对程序中找到所有1条边的部分进行了编码，然后通过删除这些边将图分割成两个连接的部分。我试着为第二部分写些东西，做了两个版本，但是没有一个在
浏览 2提问于2009-07-17得票数 2
回答已采纳
1回答
当我看到时，这个问题突然浮现在我的脑海中。为了简单起见，我们可以将讨论限制在无向、加权、连通图上。显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
2回答
给出了任意连通无向图G(V,E)，证明了在G中始终存在一个顶点v，其从图中删除不影响G的连通性，即在每个顶点之间都存在一条路径。显示一个O(|E|+|V|)时间算法来寻找这样一个顶点。
所以我开始试着想出一种解决这个问题的算法。我认为一个很好的方法是使用广度优先搜索(BFS)。然后，您将能够删除顶点在最高层。由于BFS是由层完成的，因此从最高层删除顶点不应该断开图中的其他顶点。
我在正确的轨道上吗？我该怎么证明呢？
浏览 1提问于2016-10-15得票数 0
回答已采纳
2回答
给定一个大小为n的无向图。如何计算图中有多少个大小为k的连接组件？假设为k<=n，并且输入图是连接的。
例如，给定一个[(0,1), (1,2)]的图。它具有3大小为1的连接组件、2大小为2的连接组件和1大小为3的连接组件。
浏览 26提问于2020-06-01得票数 0
1回答
我正在寻找一种在C#中生成随机平面图的方法。我研究过一些算法，比如Voronoi图，Delaunay三角剖分算法和凸包算法。它们很有用，我成功地生成了一个图，但是我面临一些我还没有解决的边缘情况。请记住，我有两个主要的约束:最小/最大边长和最小/最大角(任意两个边之间)，在目标顶点/边计数中有误差是可以的。
我认为有两种方法可以生成这张图: A.有各种可能的平面图，我需要一个小的，所以这对我有用，但我不知道如何在没有交叉点的情况下把它画成平面图。从几何学的角度来看，这是我最理解的。
我发现了一些为大图快速生成的论文，所以对我来说很复杂。我可以接受一个经过测试的慢算法/库/代码。
浏览 9提问于2022-03-01得票数 -1
1回答
我想说明的是，对于一个示例图族，连通子图的数量随着n的增加而增加。
对于一个完整的图，这很容易显示，因为一个完整的图具有
n(n-1)/2 =n/2
边。一条边要么在子图中，要么不在子图中。因此，每个子图都可以用长度为
2^(n超过2)
因为它是一个完整的图，所以每个子图都是连通的。
但让我们假设，例如，我们想要显示3-或4-正则图中的连通子图的数量也呈指数增长。我们可以用同样的方式枚举子图。但我们必须排除它们中的许多，因为它们是不相关的。
我们如何做到这一点？有没有办法区分所有连通子图和非连通子图？
致以问候和感谢您的想法
浏览 0提问于2016-03-18得票数 0
2回答
R树与R中的图划分库
、、、、
我需要进行有效的d维点搜索，也需要对d维中的一个点进行有效的k查询。因此我需要一个R-树库。我需要一个库来构建R-树结构，我可以在需要的时候使用它来查询。
此外，我还需要一些类似于或的库，尽管我的应用程序不涉及超图。我的要求是找到一个图的最小割集，它把图划分成大约两个大小相等的图。
问题是，我需要在R中支持这些的库。
我已经找到了一个库，它具有基于kd-树的k-NN查询，但问题是，要么我必须一次完成所有kd查询并将结果存储在一个巨大的数组中，要么需要每次需要时调用该函数(nn或nn2)，这与O(n lg n)检索增长的时间增长背道而驰。
有人能告诉我R中是否有这样的图书馆吗？
注意:为了高效地
浏览 1提问于2012-06-09得票数 4
回答已采纳
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议
腾讯云开发者
