问题标签 [graph-algorithm]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

Filter by
Sorted by
Tagged with
0 投票
4 回答
44131 浏览

图序列化

我正在寻找一种简单的算法来“序列化”有向图。特别是我有一组文件,它们的执行顺序相互依赖,我想在编译时找到正确的顺序。我知道这一定是一件相当普遍的事情——编译器一直都在这样做——但我的 google-fu 今天一直很弱。什么是“首选”算法?

0 投票
5 回答
3500 浏览

图搜索算法

我正在寻找具有一些不寻常属性的图形算法。

图中的每条边要么是“上”边,要么是“下”边。

一条有效的路径可以经过不定数量的“up”,然后是不定数量的“down”,反之亦然。但是,它不能多次改变方向。

例如,有效路径可能是 A “up” B “up” C “down” E “down” F 无效路径可能是 A “up” B “down” C “up” D

什么是找到两个节点之间最短有效路径的好算法?如何找到所有等长的最短路径?

0 投票
17 回答
255865 浏览

在有向图中查找所有循环

如何从/到给定节点的有向图中找到(迭代)所有循环?

例如,我想要这样的东西:

但不是:B->C->B

0 投票
1 回答
618 浏览

如何构建新的中心性度量?

我想使用 构建一个新的中心性度量igraph,最好是在R.

我该如何开始呢?

例如,我会更好地添加到igraph C libraryR interface吗?

0 投票
7 回答
9346 浏览

从集合中的数字计算目标数字

我正在处理一个家庭作业问题,它问我这个问题:

给定一组有限的数字和一个目标数字,找出该集合是否可用于使用基本数学运算(add、sub、mult、div)计算目标数字,并仅使用集合中的每个数字一次(所以我需要用尽集合)。这必须通过递归来完成。

所以,例如,如果我有一套

和目标 10,然后我可以通过使用

我试图用伪代码来表达算法,但到目前为止还没有走得太远。我认为图表是要走的路,但肯定会感谢您对此的帮助。谢谢。

0 投票
2 回答
7994 浏览

C#中的反向广度优先遍历

任何人都有 C# 中反向广度优先遍历算法的现成实现?

通过反向广度优先遍历,我的意思不是从公共节点开始搜索树,而是从底部搜索树并逐渐收敛到公共节点。

让我们看下图,这是广度优先遍历的输出: 替代文字

在我的反向广度优先遍历中,9, 10,1112将是找到的前几个节点(它们的顺序并不重要,因为它们都是一阶的)。5, 6,78是找到的第二个节点,依此类推。1将是找到的最后一个节点。

任何想法或指示?

编辑:将“广度优先搜索”更改为“广度优先遍历”以澄清问题

0 投票
3 回答
7156 浏览

开源图形布局库

我正在为.net 框架寻找一个开源(GPL、LGPL 等)图形布局库,最好是完全托管的代码。我不担心事物的可视化方面。

我可以找到很多用于 Java 的,但没有用于 .net 的...

谢谢!

0 投票
5 回答
18002 浏览

如何选择整数线性规划求解器?

我是整数线性规划的新手。我计划使用整数线性规划求解器来解决我的组合优化问题。我更熟悉 IDE 上的 C++/面向对象编程。现在我大部分时间都在使用带有 Cygwin 的 NetBeans 来编写我的应用程序。

请问是否有适合我的易于使用的 ILP 求解器?还是取决于我要解决的问题?我正在尝试做一些资源映射优化。如果需要任何进一步的信息,请告诉我。

非常感谢你,卡西。

0 投票
15 回答
315299 浏览

什么时候使用深度优先搜索 (DFS) 与广度优先搜索 (BFS) 比较实用?

我了解 DFS 和 BFS 之间的区别,但我很想知道何时使用其中一种更实用?

谁能举例说明 DFS 如何胜过 BFS,反之亦然?

0 投票
2 回答
10557 浏览

图中最大权重的循环

给定一个加权图(有向或无向),我需要找到具有最大权重的图的循环。

循环的权重是图的边权重的总和。

它可以是任何循环,而不仅仅是我们可以的基本循环

我可以尝试枚举图的所有循环,然后计算最大值,但循环的总数可能非常大(如果图是完整的,那么第一个和最后一个相同的任何顶点序列都是一个循环)。

您有什么想法可以在不枚举所有循环的情况下找到最大重量循环吗?

如果您需要图表上的假设(例如正权重),请指出它们。