代码之家 › 专栏 › 技术社区 › monoceres

寻找关键节点的快速算法是什么?

graph algorithm

monoceres · 技术社区 · 14 年前

我正在寻找一种快速的方法/算法来找出图中哪些节点是关键的。

alt text

节点2和节点5非常关键。

我当前的方法是尝试一次从图中删除一个非端点节点,然后检查是否可以从所有其他节点访问整个网络。这种方法显然不是很有效。

有什么更好的方法?

2 回复 | 直到 12 年前

IVlad 14 年前

在任何情况下,算法由一个简单的 depth first search 为每个节点维护某些信息。

Steven A. Lowe 14 年前

有几种更好的方法。 research is always helpful

但既然这是家庭作业,那么这个练习的重点很可能是你自己想清楚

提示:如何修饰图形以告诉您哪些节点依赖于哪些其他节点,这些信息是否有助于发现关键节点?

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前