我正在寻找一个算法来解决以下问题。我有一个给定集合(a-h)的多个子集(1-n)。我想找到最小的子集合,通过组合可以构建出所有给定的子集。这个子集合可以包含1-n中不存在的子集。 a b c d e f g h 1 1 2 1 1 3 1 1 1 4 1 ...
如果我们的目标时间复杂度为O(|V| * |E|)或O(V ^ 3)等,则此问题有一个简单的解决方案。然而,最近我的教授布置了这样一个任务: 让G =(V,E)成为连通的无向图。编写一种算法,在O(| V | + | E |)中确定G是否包含三角形。 到这一点,我陷入了困境。维基百...
使用不相交集数据结构可以轻松获取图的连通分量。而且,它仅支持增量连通组件。 然而,在我的情况下,删除边缘非常普遍,因此我正在寻找一种算法或新的结构,可以完全动态地维护连接组件(包括添加和删除边缘)
我想使用这个jgrapht接口类在我的图形上包含边的权重或成本:package org.jgrapht; public interface WeightedGraph<V extends Object, E extends Object> extends Graph<V, ...
我查看了许多图形布局的包(例如Graphviz、Gephi、Cytoscape、NetworkX等),但似乎没有一个能够适应这种规模。有哪些技术可以用于可视化如此大的图形或将其缩小到更易处理的大小?
阅读了 Stevey Yegge 的 Get That Job At Google 文章后,我发现这句话很有意思: 每当有人给你一个问题时,想到图形。它们是表示任何关系的最基本和灵活的方式,所以任何有趣的设计问题都有50%的可能涉及图形。在尝试其他解决方案之前,请确保无法考虑使用图形解决它...
我想知道是否有人可以推荐一个好的C++树实现,最好是兼容STL。 就记录而言,我以前多次编写过树算法,我知道它可能很有趣,但如果可能的话,我想变得务实和懒惰。 因此,实际链接到可用解决方案是这里的目标。 注意:我正在寻找一棵通用树,而不是平衡树或映射/集合,对于这种情况,树的结构本身和连接...
计算k-核图的方法是通过迭代修剪顶点来完成的。然而,对于我的应用程序,我希望能够添加顶点到起始图并获得更新后的核心,而无需重新计算整个k-核心。是否有可靠的算法可以利用先前迭代的工作? 对于那些好奇的人,k-核心正在被用作查找团的预处理阶段。任何大小为5的团都保证是图的4-核心的一部分。在我...
有一些算法,例如Edmond's Algorithm或Boruvka's Algorithm,需要程序员创建一个图形,该图形是通过将一些节点合并为单个节点而获得的,并在稍后将其扩展回来。 收缩的正式描述如下: 假设G是具有顶点V和边缘E的图形。 让C是G的连通组件。 关于C的G的收缩定义为...