使用Queue进行深度优先搜索

本文关键字：深度优先搜索 Queue 使用 | 更新日期: 2023-09-27 18:00:18

如何使用c#中的Queue进行深度优先搜索？

以下是我的数据结构：

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;
        }

出于某种原因，以上内容并没有给我深度。你能帮忙吗？

使用Queue进行深度优先搜索

深度优先搜索是使用LIFO数据结构实现的，因此您需要将Queue替换为Stack。使用像队列这样的FIFO结构会给您带来BFS。

您可以递归

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);
        }
    }
}

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

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;
    }
}
相关文章：