假设我有一个图表，其中节点存储在排序列表中。我现在想对该图进行拓扑排序，同时保持未定义拓扑顺序的原始顺序。有什么好的算法吗？
问问题
5166 次
6 回答
17
一种可能性是计算字典序上的最小拓扑顺序。该算法是维护一个优先级队列，其中包含有效入度（在尚未处理的节点上）为零的节点。反复将标签最少的节点出列，将其附加到订单中，递减其后继节点的有效入度，将现在入度为零的节点入队。这会在 btilly 的示例中生成 1234567890，但通常不会最小化反转。
我喜欢这个算法的属性是输出有一个清晰的定义，显然只满足一个顺序，并且每当有反转时（节点 x 出现在节点 y 之后，即使 x < y），x 的最大依赖关系大于 y 的最大依赖关系依赖关系，这是反转 x 和 y 的“借口”。一个推论是，在没有约束的情况下，lex 最小顺序是排序顺序。
于 2012-06-27T23:09:34.187 回答
6
问题有两个方面：
- 拓扑排序
- 稳定排序
经过多次错误和试验，我想出了一个类似于冒泡排序但具有拓扑顺序标准的简单算法。
我在具有完整边组合的完整图上彻底测试了该算法，因此它可以被认为是经过验证的。
根据元素的原始顺序，可以容忍和解决循环依赖关系。生成的顺序是完美的，代表最接近的匹配。
以下是 C# 中的源代码：
static class TopologicalSort
{
/// <summary>
/// Delegate definition for dependency function.
/// </summary>
/// <typeparam name="T">The type.</typeparam>
/// <param name="a">The A.</param>
/// <param name="b">The B.</param>
/// <returns>
/// Returns <c>true</c> when A depends on B. Otherwise, <c>false</c>.
/// </returns>
public delegate bool TopologicalDependencyFunction<in T>(T a, T b);
/// <summary>
/// Sorts the elements of a sequence in dependency order according to comparison function with Gapotchenko algorithm.
/// The sort is stable. Cyclic dependencies are tolerated and resolved according to original order of elements in sequence.
/// </summary>
/// <typeparam name="T">The type of the elements of source.</typeparam>
/// <param name="source">A sequence of values to order.</param>
/// <param name="dependencyFunction">The dependency function.</param>
/// <param name="equalityComparer">The equality comparer.</param>
/// <returns>The ordered sequence.</returns>
public static IEnumerable<T> StableOrder<T>(
IEnumerable<T> source,
TopologicalDependencyFunction<T> dependencyFunction,
IEqualityComparer<T> equalityComparer)
{
if (source == null)
throw new ArgumentNullException("source");
if (dependencyFunction == null)
throw new ArgumentNullException("dependencyFunction");
if (equalityComparer == null)
throw new ArgumentNullException("equalityComparer");
var graph = DependencyGraph<T>.TryCreate(source, dependencyFunction, equalityComparer);
if (graph == null)
return source;
var list = source.ToList();
int n = list.Count;
Restart:
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (graph.DoesXHaveDirectDependencyOnY(list[j], list[i]))
{
bool jOnI = graph.DoesXHaveTransientDependencyOnY(list[j], list[i]);
bool iOnJ = graph.DoesXHaveTransientDependencyOnY(list[i], list[j]);
bool circularDependency = jOnI && iOnJ;
if (!circularDependency)
{
var t = list[i];
list.RemoveAt(i);
list.Insert(j, t);
goto Restart;
}
}
}
}
return list;
}
/// <summary>
/// Sorts the elements of a sequence in dependency order according to comparison function with Gapotchenko algorithm.
/// The sort is stable. Cyclic dependencies are tolerated and resolved according to original order of elements in sequence.
/// </summary>
/// <typeparam name="T">The type of the elements of source.</typeparam>
/// <param name="source">A sequence of values to order.</param>
/// <param name="dependencyFunction">The dependency function.</param>
/// <returns>The ordered sequence.</returns>
public static IEnumerable<T> StableOrder<T>(
IEnumerable<T> source,
TopologicalDependencyFunction<T> dependencyFunction)
{
return StableOrder(source, dependencyFunction, EqualityComparer<T>.Default);
}
sealed class DependencyGraph<T>
{
private DependencyGraph()
{
}
public IEqualityComparer<T> EqualityComparer
{
get;
private set;
}
public sealed class Node
{
public int Position
{
get;
set;
}
List<T> _Children = new List<T>();
public IList<T> Children
{
get
{
return _Children;
}
}
}
public IDictionary<T, Node> Nodes
{
get;
private set;
}
public static DependencyGraph<T> TryCreate(
IEnumerable<T> source,
TopologicalDependencyFunction<T> dependencyFunction,
IEqualityComparer<T> equalityComparer)
{
var list = source as IList<T>;
if (list == null)
list = source.ToArray();
int n = list.Count;
if (n < 2)
return null;
var graph = new DependencyGraph<T>();
graph.EqualityComparer = equalityComparer;
graph.Nodes = new Dictionary<T, Node>(n, equalityComparer);
bool hasDependencies = false;
for (int position = 0; position < n; ++position)
{
var element = list[position];
Node node;
if (!graph.Nodes.TryGetValue(element, out node))
{
node = new Node();
node.Position = position;
graph.Nodes.Add(element, node);
}
foreach (var anotherElement in list)
{
if (equalityComparer.Equals(element, anotherElement))
continue;
if (dependencyFunction(element, anotherElement))
{
node.Children.Add(anotherElement);
hasDependencies = true;
}
}
}
if (!hasDependencies)
return null;
return graph;
}
public bool DoesXHaveDirectDependencyOnY(T x, T y)
{
Node node;
if (Nodes.TryGetValue(x, out node))
{
if (node.Children.Contains(y, EqualityComparer))
return true;
}
return false;
}
sealed class DependencyTraverser
{
public DependencyTraverser(DependencyGraph<T> graph)
{
_Graph = graph;
_VisitedNodes = new HashSet<T>(graph.EqualityComparer);
}
DependencyGraph<T> _Graph;
HashSet<T> _VisitedNodes;
public bool DoesXHaveTransientDependencyOnY(T x, T y)
{
if (!_VisitedNodes.Add(x))
return false;
Node node;
if (_Graph.Nodes.TryGetValue(x, out node))
{
if (node.Children.Contains(y, _Graph.EqualityComparer))
return true;
foreach (var i in node.Children)
{
if (DoesXHaveTransientDependencyOnY(i, y))
return true;
}
}
return false;
}
}
public bool DoesXHaveTransientDependencyOnY(T x, T y)
{
var traverser = new DependencyTraverser(this);
return traverser.DoesXHaveTransientDependencyOnY(x, y);
}
}
}
还有一个小示例应用程序：
class Program
{
static bool DependencyFunction(char a, char b)
{
switch (a + " depends on " + b)
{
case "A depends on B":
return true;
case "B depends on D":
return true;
default:
return false;
}
}
static void Main(string[] args)
{
var source = "ABCDEF";
var result = TopologicalSort.StableOrder(source.ToCharArray(), DependencyFunction);
Console.WriteLine(string.Concat(result));
}
}
给定输入元素 {A, B, C, D, E, F}，其中 A 依赖于 B，B 依赖于 D，输出为 {D, B, A, C, E, F}。
更新： 我写了一篇关于稳定拓扑排序目标、算法及其证明的小文章。希望这能提供更多解释，并对开发人员和研究人员有用。
于 2014-07-09T17:11:55.197 回答
3
您没有足够的标准来指定您要查找的内容。例如，考虑一个具有两个有向分量的图。
1 -> 2 -> 3 -> 4 -> 5
6 -> 7 -> 8 -> 9 -> 0
您更喜欢以下哪一种？
6, 7, 8, 9, 0, 1, 2, 3, 4, 5
1, 2, 3, 4, 5, 6, 7, 8, 9, 0
第一个结果是通过将最低节点尽可能靠近列表的头部来打破所有关系。因此0胜。第二个结果是试图最小化 A < B 和 B 在拓扑排序中出现在 A 之前的次数。两者都是合理的答案。第二个可能更令人愉快。
我可以很容易地为第一个生成算法。首先，取最低节点，并进行广度优先搜索以定位到最短根节点的距离。如果存在平局，请确定可能出现在这种最短路径上的节点集。取该集合中的最低节点，并放置从它到根的最佳可能路径，然后放置从我们开始的最低节点到它的最佳可能路径。搜索尚未在拓扑排序中的下一个最低节点，然后继续。
为更令人愉悦的版本生成算法似乎要困难得多。请参阅http://en.wikipedia.org/wiki/Feedback_arc_set以了解相关问题，该问题强烈表明它实际上是 NP 完全的。
于 2012-06-27T18:20:39.983 回答
2
这是一种简单的拓扑排序迭代方法：不断删除度数为 0 的节点及其边。
要获得稳定的版本，只需修改为：不断删除最小索引节点的度数为 0 及其边缘。
在伪python中：
# N is the number of nodes, labeled 0..N-1
# edges[i] is a list of nodes j, corresponding to edges (i, j)
inDegree = [0] * N
for i in range(N):
for j in edges[i]:
inDegree[j] += 1
# Now we maintain a "frontier" of in-degree 0 nodes.
# We take the smallest one until the frontier is exhausted.
# Note: You could use a priority queue / heap instead of a list,
# giving O(NlogN) runtime. This naive implementation is
# O(N^2) worst-case (when the order is very ambiguous).
frontier = []
for i in range(N):
if inDegree[i] == 0:
frontier.append(i)
order = []
while frontier:
i = min(frontier)
frontier.remove(i)
for j in edges[i]:
inDegree[j] -= 1
if inDegree[j] == 0:
frontier.append(j)
# Done - order is now a list of the nodes in topological order,
# with ties broken by original order in the list.
于 2017-12-09T17:14:47.980 回答
0
维基百科上的深度优先搜索算法对我有用：
const assert = chai.assert;
const stableTopologicalSort = ({
edges,
nodes
}) => {
// https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
const result = [];
const marks = new Map();
const visit = node => {
if (marks.get(node) !== `permanent`) {
assert.notEqual(marks.get(node), `temporary`, `not a DAG`);
marks.set(node, `temporary`);
edges.filter(([, to]) => to === node).forEach(([from]) => visit(from));
marks.set(node, `permanent`);
result.push(node);
}
};
nodes.forEach(visit);
return result;
};
const graph = {
edges: [
[5, 11],
[7, 11],
[3, 8],
[11, 2],
[11, 9],
[11, 10],
[8, 9],
[3, 10]
],
nodes: [2, 3, 5, 7, 8, 9, 10, 11]
};
assert.deepEqual(stableTopologicalSort(graph), [5, 7, 11, 2, 3, 8, 9, 10]);<script src="https://cdnjs.cloudflare.com/ajax/libs/chai/4.2.0/chai.min.js"></script>于 2018-11-03T00:22:35.413 回答
0
将“稳定拓扑排序”解释为 DAG 的线性化，使得拓扑顺序无关紧要的线性化范围按字典顺序排序。这可以通过线性化的DFS方法解决，修改为按字典顺序访问节点。
我有一个带有线性化方法的 Python Digraph 类，如下所示：
def linearize_as_needed(self):
if self.islinearized:
return
# Algorithm: DFS Topological sort
# https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
temporary = set()
permanent = set()
L = [ ]
def visit(vertices):
for vertex in sorted(vertices, reverse=True):
if vertex in permanent:
pass
elif vertex in temporary:
raise NotADAG
else:
temporary.add(vertex)
if vertex in self.arrows:
visit(self.arrows[vertex])
L.append(vertex)
temporary.remove(vertex)
permanent.add(vertex)
# print('visit: {} => {}'.format(vertices, L))
visit(self.vertices)
self._linear = list(reversed(L))
self._iter = iter(self._linear)
self.islinearized = True
这里
self.vertices
是所有顶点的集合，并且
self.arrows
将邻接关系作为左节点到右节点集的字典。
于 2017-08-18T13:09:09.787 回答