有向图的数据结构，允许快速删除节点？
我需要存储一个有向图（不一定是无环的），以便节点删除尽可能快速。为了知道在删除节点时哪些边需要去掉，我不介意存储额外的数据。 如果我存储边的列表（作为节点索引对），那么当删除某个节点n时，我必须搜索整个列表以查找其源或目标为n的边。这对我的应用程序来说太昂贵了。是否可以通过在节点中存储一些附...
检查有向图是否强连通的算法
我需要检查一个有向图是否强连通，也就是说，任何一个节点都可以通过其他节点到达（不一定是通过直接边缘）。 一种方法是在每个节点上运行DFS和BFS，并查看所有其他节点是否仍然可达。 是否有更好的方法来做到这一点？
Java中用于大型数据集的类似于map的数据结构
有没有已经实现的数据结构可以用来为对象（在我的情况下是边）分配一个整数？我正在从文件中读取图，有一千万个顶点、六千万条边，并使用映射将成本赋给每条边（costs.put(e,cost)）。 我是这样创建costs映射的： costs = new HashMap<Edge,Intege...
在增量构建有向图的同时更高效地计算每个依赖项的传递闭包
我需要回答以下问题：在一个依赖图中，给定一个节点，将其依赖项根据它们自己的传递依赖项分组，这些依赖项会受到特定起始节点的影响。 换句话说，给定依赖图中的一个节点，找到一组直接依赖项的集合，它们具有来自该特定起始节点的共同依赖项。 例如，给定伪代码：let a = 1 let b = 2 l...
在networkx（Python）中获取有向图的根（头部）
我在一个项目中试图使用networkx进行一些图形表示，但不确定如何完成几个看似简单的任务。我创建了一个有许多节点和边的有向图，其中只有一个根元素。现在，我想从根开始遍历每个元素的子节点，并从它们中提取一些信息。如何获取这个DiGraph的根元素？ 所以代码大概是这样的：#This is ...
合并一些已排序但未知顺序的列表
我有一些包含可变数量元素的列表。每个列表都已排序，但排序算法是未知的。我想将这些列表合并成一个大列表，该列表按相同顺序包含所有列表，且不包含重复项。 示例输入： 1. XS，M，L，XL 2. S，M，XXL 3. XXS，XS，S，L 期望的结果： - XXS，XS，S，M，L，XL...
在networkx中查找图对象内的单独图形
我有一个庞大的图形数据集 - 假设它像这样，但规模更大：1 -> 2 3 -> 4 1、2、3、4是节点，箭头表示有向边。假设它们都在同一个图对象中:import networkx as nx G = nx.DiGraph() G.add_nodes_from([1,2,3,4])...
生成一个有n个圆周的有向图。
我想生成一个有指定数量的特定长度循环的有向图。例如，该图应包含： 2个大小为3的循环 1个大小为5的循环 是否已经存在这样的算法？如果没有，您会如何解决这个问题？详细说明以下参数： 1.顶点数（例如15） 2.组件数（例如2） 3.必须在图中出现的循环（例如{3循环，3循环，5循环}） ...
这个数据结构有规范符号表示吗？
我正在寻找一种数学形式化方法来处理我正在处理的数据结构，以便我可以追踪相关的定理和算法。 假设你有以下内容： - 一个主题的有向无环图。 - 在每个主题下，主题、文档集合中的项目和组合集合中的项目之间存在一个或多个关系。 - 组可能是一个简单的集合，也可能最终成为有向无环图。它们用于管理文...
图形序列化
我正在寻找一个简单的算法来“序列化”有向图。特别是我有一组具有执行顺序相互依赖性的文件，并且我想在编译时找到正确的顺序。我知道这必须是一个相当普遍的事情 - 编译器一直在做 - 但是今天我的谷歌搜索能力很弱。这个“go-to”算法是什么？