拓扑排序,支持循环依赖

Question

考虑以下依赖关系(其中A --> BB意味着A取决于A,因此有效地,A是'父')

A --> B
A --> C
C --> D
C --> E

更加图形化:

    A
    |
----------
|        |
B        C
         |
    -----------
    |         |
    D         E

拓扑排序算法将返回如下内容:

ABCDE

我找到了这个代码(展示A和展览B),但都不支持cyclice依赖.我觉得这可能会发生:

A --> B
B --> C
B --> D
C --> B
C --> E

图形:

A
|
B <--> C
|      |
D      E

这可能会返回ABCDE或ACBDE.因此,因为B和C处于相同的"水平",它们之间的顺序并不重要(同样对于D和E).

我怎么能完成这样的事情.我意识到这不是一个拓扑排序,但我不是专家数学家,所以我真的不知道从哪里开始寻找,更不用说如何实现它了.

就个人而言,我在C#工作,但如果你知道如何用其他任何语言来做,我会很乐意研究你的代码并将其翻译成C#.

更新

我也有以下情况:

A <--------
|         |
--> B --> C
    |     |
    D     E

所以,重要的是,这不一定是一棵树.我可以有任意图形.实际上,并非所有节点都必须彼此连接.

Answer 1

首先,如果你有一个图表,你可以问"你依赖什么",这在概念上会更容易？我将假设我们有一个图表,其中从A到B的有向边意味着"A取决于B",这与您的陈述相反.

我对你的问题感到有些困惑,因为忽略循环的拓扑排序几乎与常规拓扑排序相同.我将开发算法,以便您可以按照自己的意愿处理周期; 也许这会有所帮助.

这种想法是:

• 图是节点的集合,使得每个节点具有邻居集合.正如我所说,如果节点A有一个邻居B,那么A取决于B,所以B必须在A之前发生.

• 排序采用图形并生成排序的节点列表.

• 在排序操作期间,维护字典,将每个节点映射到三个值之一:alive,dead和undead.尚未处理活动节点.已经处理了死节点.正在处理不死节点; 它不再存在但尚未死亡.

• 如果遇到死节点,可以跳过它; 它已经在输出列表中.

• 如果遇到活动节点,则以递归方式处理它.

• 如果遇到不死节点,那么它就是循环的一部分.你喜欢什么.(如果周期是非法的,则产生错误,如果周期合法则将其视为死亡,等等)

function topoSort(graph) 
  state = []
  list = []
  for each node in graph
    state[node] = alive
  for each node in graph
    visit(graph, node, list, state)
  return list

function visit(graph, node, list, state)
  if state[node] == dead
    return // We've done this one already.
  if state[node] == undead
    return // We have a cycle; if you have special cycle handling code do it here.
  // It's alive. Mark it as undead.
  state[node] = undead
  for each neighbour in getNeighbours(graph, node)
    visit(graph, neighbour, list, state)
  state[node] = dead
  append(list, node);

合理？

Answer 2

编辑3年后:自从我在2014年第一次实现这个以来,我偶尔也会回到这里.当我第一次发布这个答案时,我并没有真正理解它,所以答案过于复杂.实际上,排序实现非常简单:

public class Node
{
    public int Data { get; set; }
    public List<Node> Children { get; set; }

    public Node()
    {
        Children = new List<Node>();
    }
}

public class Graph
{
    public List<Node> Nodes { get; set; }

    public Graph()
    {
        Nodes = new List<Node>();
    }

    public List<Node> TopologicSort()
    {
        var results = new List<Node>();
        var seen = new List<Node>();
        var pending = new List<Node>();

        Visit(Nodes, results, seen, pending);

        return results;
    }

    private void Visit(List<Node> graph, List<Node> results, List<Node> dead, List<Node> pending)
    {
        // Foreach node in the graph
        foreach (var n in graph)
        {
            // Skip if node has been visited
            if (!dead.Contains(n))
            {
                if (!pending.Contains(n))
                {
                    pending.Add(n);
                }
                else
                {
                    Console.WriteLine(String.Format("Cycle detected (node Data={0})", n.Data));
                    return;
                }

                // recursively call this function for every child of the current node
                Visit(n.Children, results, dead, pending);

                if (pending.Contains(n))
                {
                    pending.Remove(n);
                }

                dead.Add(n);

                // Made it past the recusion part, so there are no more dependents.
                // Therefore, append node to the output list.
                results.Add(n);
            }
        }
    }
}