问题标签 [sink-vertex]
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.
3 问题
0
投票
7
回答
17164
浏览
algorithm - 图表：在小于 O(|V|) 的时间内找到一个接收器 - 或显示它无法完成
我有一个带有n节点的图作为邻接矩阵。
是否有可能在更短的O(n)时间内检测到水槽？
如果是，如何？如果不是，我们如何证明？
Sink 顶点是具有来自其他节点的入边且没有出边的顶点。
0
投票
3
回答
6193
浏览
algorithm - 在有向无环图中检测汇
假设在 a 中有一个具有以下属性的顶点DAG：
所有顶点都连接到它
它没有连接到任何顶点
这通常称为汇顶点。
是否可以在图中检测到这个顶点O(n)，n图中的顶点数在哪里？
0
投票
1
回答
32
浏览
algorithm - 这个总汇算法仅适用于 dags 吗？
我发现了这种用于检查图中是否存在总汇的有向图算法。 https://www.geeksforgeeks.org/determine-whether-universal-sink-exists-directed-graph/
我的问题是：这对非 dag 有向图有效吗？
因为如果存在 v1、v2 之间的循环，那么我们可能会错过识别这个 1 并错误地将 v2 视为源接收器（或者我在这里遗漏了什么）？
