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

null ノードを許可するかどうかによっては、null チェックを追加する必要がある場合があります。

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 に答える