将有向无环图（DAG）转换为树

我正在尝试实现algoritm将Directed Acyclic Graph转换为Tree（为了好玩，学习，kata，命名它）。 所以我想出了数据结构Node：

/// 
 /// Represeting a node in DAG or Tree /// 
 /// Value of the node public class Node { /// 
 /// creats a node with no child nodes /// 
 /// Value of the node public Node(T value) { Value = value; ChildNodes = new List<Node>(); } /// 
 /// Creates a node with given value and copy the collection of child nodes /// 
 /// value of the node /// collection of child nodes public Node(T value, IEnumerable<Node> childNodes) { if (childNodes == null) { throw new ArgumentNullException("childNodes"); } ChildNodes = new List<Node>(childNodes); Value = value; } /// 
 /// Determines if the node has any child node /// 
 /// true if has any public bool HasChildNodes { get { return this.ChildNodes.Count != 0; } } /// 
 /// Travearse the Graph recursively /// 
 /// root node /// visitor for each node public void Traverse(Node root, Action<Node> visitor) { if (root == null) { throw new ArgumentNullException("root"); } if (visitor == null) { throw new ArgumentNullException("visitor"); } visitor(root); foreach (var node in root.ChildNodes) { Traverse(node, visitor); } } /// 
 /// Value of the node /// 
 public T Value { get; private set; } /// 
 /// List of all child nodes /// 
 public List<Node> ChildNodes { get; private set; } } 

这很简单。 方法：

 /// 
 /// Helper class for Node /// 
 /// Value of a node public static class NodeHelper { /// 
 /// Converts Directed Acyclic Graph to Tree data structure using recursion. /// 
 /// root of DAG /// keep track of child elements to find multiple connections (fe A connects with B and C and B also connects with C) /// root node of the tree public static Node DAG2TreeRec(this Node root, HashSet<Node> seenNodes) { if (root == null) { throw new ArgumentNullException("root"); } if (seenNodes == null) { throw new ArgumentNullException("seenNodes"); } var length = root.ChildNodes.Count; for (int i = 0; i < length; ++i) { var node = root.ChildNodes[i]; if (seenNodes.Contains(node)) { var nodeClone = new Node(node.Value, node.ChildNodes); node = nodeClone; } else { seenNodes.Add(node); } DAG2TreeRec(node, seenNodes); } return root; } /// 
 /// Converts Directed Acyclic Graph to Tree data structure using explicite stack. /// 
 /// root of DAG /// keep track of child elements to find multiple connections (fe A connects with B and C and B also connects with C) /// root node of the tree public static Node DAG2Tree(this Node root, HashSet<Node> seenNodes) { if (root == null) { throw new ArgumentNullException("root"); } if (seenNodes == null) { throw new ArgumentNullException("seenNodes"); } var stack = new Stack<Node>(); stack.Push(root); while (stack.Count > 0) { var tempNode = stack.Pop(); var length = tempNode.ChildNodes.Count; for (int i = 0; i < length; ++i) { var node = tempNode.ChildNodes[i]; if (seenNodes.Contains(node)) { var nodeClone = new Node(node.Value, node.ChildNodes); node = nodeClone; } else { seenNodes.Add(node); } stack.Push(node); } } return root; } } 

并测试：

  static void Main(string[] args) { // Jitter preheat Dag2TreeTest(); Dag2TreeRecTest(); Console.WriteLine("Running time "); Dag2TreeTest(); Dag2TreeRecTest(); Console.ReadKey(); } public static void Dag2TreeTest() { HashSet<Node> hashSet = new HashSet<Node>(); Node root = BulidDummyDAG(); Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); var treeNode = root.DAG2Tree(hashSet); stopwatch.Stop(); Console.WriteLine(string.Format("Dag 2 Tree = {0}ms",stopwatch.ElapsedMilliseconds)); } private static Node BulidDummyDAG() { Node node2 = new Node(2); Node node4 = new Node(4); Node node3 = new Node(3); Node node5 = new Node(5); Node node6 = new Node(6); Node node7 = new Node(7); Node node8 = new Node(8); Node node9 = new Node(9); Node node10 = new Node(10); Node root = new Node(1); //making DAG root.ChildNodes.Add(node2); root.ChildNodes.Add(node3); node3.ChildNodes.Add(node2); node3.ChildNodes.Add(node4); root.ChildNodes.Add(node5); node4.ChildNodes.Add(node6); node4.ChildNodes.Add(node7); node5.ChildNodes.Add(node8); node2.ChildNodes.Add(node9); node9.ChildNodes.Add(node8); node9.ChildNodes.Add(node10); var length = 10000; Node tempRoot = node10; for (int i = 0; i < length; i++) { var nextChildNode = new Node(11 + i); tempRoot.ChildNodes.Add(nextChildNode); tempRoot = nextChildNode; } return root; } public static void Dag2TreeRecTest() { HashSet<Node> hashSet = new HashSet<Node>(); Node root = BulidDummyDAG(); Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); var treeNode = root.DAG2TreeRec(hashSet); stopwatch.Stop(); Console.WriteLine(string.Format("Dag 2 Tree Rec = {0}ms",stopwatch.ElapsedMilliseconds)); } 

更重要的是，数据结构需要一些改进：

• 覆盖GetHash，toString，Equals，== operator
• 实施IComparable
• LinkedList可能是更好的选择

此外，在转换之前，需要检查certian thigs：

• 多重图
• 如果是DAG（周期）
• DAG的Diamnods
• DAG中有多个根

总而言之，它缩小为几个问题： 如何改善转换？ 由于这是一次复发，因此可能会炸毁堆栈。 我可以添加堆栈来记忆它。 如果我继续传递风格，我会更有效率吗？

我认为在这种情况下不可变的数据结构会更好。 这是对的吗？

Childs是正确的名字吗？ 🙂

Answer 1

算法：

• 如您所见，某些节点在输出中出现两次。 如果节点2有子节点，则整个子树将出现两次。 如果您希望每个节点只出现一次，请替换

   if (hashSet.Contains(node)) { var nodeClone = new Node(node.Value, node.Childs); node = nodeClone; } 

  同

   if (hashSet.Contains(node)) { // node already seen -> do nothing } 

• 我不会太担心堆栈的大小或递归的性能。 但是，您可以使用广度优先搜索替换深度优先搜索 ，这将导致节点更接近先前访问的根，从而产生更“自然”的树（在您的图片中，您已经按照BFS顺序编号了节点） ）。

    var seenNodes = new HashSet(); var q = new Queue(); q.Enqueue(root); seenNodes.Add(root); while (q.Count > 0) { var node = q.Dequeue(); foreach (var child in node.Childs) { if (!seenNodes.Contains(child )) { seenNodes.Add(child); q.Enqueue(child); } } 

  该算法处理钻石和周期。

• 多根

  只需声明一个包含所有顶点的类Graph

   class Graph { public List Nodes { get; private set; } public Graph() { Nodes = new List(); } } 

---

码：

• hashSet可以命名为seenNodes 。

• 代替

   var length = root.Childs.Count; for (int i = 0; i < length; ++i) { var node = root.Childs[i]; 

  写

   foreach (var child in root.Childs) 

• 在Traverse，访客是非常不必要的。 您可能更愿意拥有一个方法来生成树的所有节点（以遍历相同的顺序），并且用户可以对节点执行任何操作：

   foreach(var node in root.TraverseRecursive()) { Console.WriteLine(node.Value); } 

• 如果重写GetHashCode和Equals，算法将无法再区分具有相同值的两个不同节点，这可能不是您想要的。

• 我没有看到为什么LinkedList比List更好的原因，除了List在添加节点时所做的重新分配（容量2,4,8,16，...）。

Answer 2

1. 你最好在CodeReview中发布
2. 孩子是错的=>孩子

3. 你不必使用HashSet，你可以很容易地使用List>，因为这里只检查引用就足够了。 （因此不需要GetHashCode，Equals和运算符覆盖）

4. 更简单的方法是序列化您的类，然后使用XmlSerializer将其再次反序列化为第二个对象。 序列化和反序列化时，引用2次的1个对象将成为具有不同引用的2个对象。