4

如何在 C# 中使用队列进行深度优先搜索？

以下是我的数据结构：

public class Node
{
  public string Name{get;set}
  public IEnumerable<Node> Children{get;set;}
}

现在我有一个 Node 对象的集合，每个对象都有孩子，它又有孩子，依此类推。

我想访问每个节点并将其转换为不同的形式。

如下所示：

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes)
        {
            var queue = new Queue<Node>(nodes);

            while (queue.Any())
            {
                var next = queue.Dequeue();
                yield return BuildContentFromSingle(next);

                foreach (var child in next.Children)
                {
                    queue.Enqueue(child);
                }
            }
        }

        public IContent BuildContentFromSingle(Node node)
        {
            var content = _contentFactory.Create(node);
            return content;
        }

由于某种原因，上述内容并没有首先给我深度。你能帮忙吗？

4

3 回答 3

8

深度优先搜索是使用 LIFO 数据结构实现的，因此您需要Queue将Stack. 使用像队列这样的 FIFO 结构可以为您提供BFS。

于 2013-02-20T09:15:29.450 回答
1

你可以递归地做

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes) {
     foreach(var node in nodes){
         yield node;
         foreach(var c in BuildContentFrom(node.children)){
             yield c;
         }
     }
}

当 n 很大和/或树很深时，这可能会成为 n 树的问题。在这种情况下，您可以使用累加器

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes) {
     if(!nodes.Any()) return Enumerable.Empty<IContent>();
     var acc = new List<IContent>();
     BuildContentFrom(nodes);
}

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes, 
                                              IList<IContent> acc) {
     foreach(var node in nodes){
         acc.Add(BuildContentFromSingle(node));
         if(node.children.Any()) BuildContentFrom(node.children, acc);
     }
}

现在是尾递归，如果编译器对此进行了优化（据我记得是 C# 的设置），即使使用大树，您也不会遇到堆栈问题。

或者，您可以使用堆栈来收集您仍需要执行的工作

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes)
{
    var stack= new Stack<Node>(nodes);

    while (stack.Any())
    {
        var next = stack.Pop();
        yield return BuildContentFromSingle(next);

        foreach (var child in next.Children)
        {
            stack.push(child);
        }
    }
}
于 2013-02-20T09:29:50.613 回答
0

作为替代方案，您可以考虑使用递归来展平结构。这是一个二叉树的例子。它演示了深度优先的展平遍历。

using System;
using System.Collections.Generic;

namespace Demo
{
    public static class Program
    {
        static void Main(string[] args)
        {
            var tree = buildTree(5, true);
            printTree1(tree);
            Console.WriteLine("---------------------------------------------");
            printTree2(tree);
        }

        // Print tree using direct recursion.

        static void printTree1<T>(Node<T> tree)
        {
            if (tree != null)
            {
                Console.WriteLine(tree.Value);
                printTree1(tree.Left);
                printTree1(tree.Right);
            }
        }

        // Print tree using flattened tree.

        static void printTree2<T>(Node<T> tree)
        {
            foreach (var value in flatten(tree))
            {
                Console.WriteLine(value);
            }
        }

        // Flatten tree using recursion.

        static IEnumerable<T> flatten<T>(Node<T> root)
        {
            if (root == null)
            {
                yield break;
            }

            foreach (var node in flatten(root.Left))
            {
                yield return node;
            }

            foreach (var node in flatten(root.Right))
            {
                yield return node;
            }

            yield return root.Value;
        }

        static Node<string> buildTree(int depth, bool left)
        {
            if (depth > 0)
            {
                --depth;
                return new Node<string>(buildTree(depth, true), buildTree(depth, false), "Node." + depth + (left ? ".L" : ".R"));
            }
            else
            {
                return new Node<string>(null, null, "Leaf." + (left ? "L" : "R"));
            }
        }
    }

    public sealed class Node<T>
    {
        public Node(Node<T> left, Node<T> right, T value)
        {
            _left  = left;
            _right = right;
            _value = value;
        }

        public Node<T> Left  { get { return _left;  } }
        public Node<T> Right { get { return _right; } }
        public T       Value { get { return _value; } }

        private readonly Node<T> _left;
        private readonly Node<T> _right;
        private readonly T       _value;
    }
}

对于您的具体示例，我认为（无需测试）您可以这样做：

public static IEnumerable<Node> Flatten(Node root)
{
    foreach (var node in root.Children)
    {
        foreach (var child in Flatten(node))
        {
            yield return child;
        }
    }

    yield return root;
}

根据您是否允许空节点，您可能需要添加一些空值检查：

public static IEnumerable<Node> Flatten(Node root)
{
    if (root != null)
    {
        foreach (var node in root.Children)
        {
            foreach (var child in Flatten(node))
            {
                if (child != null)
                {
                    yield return child;
                }
            }
        }

        yield return root;
    }
}
于 2013-02-20T09:26:23.437 回答