迭代遍历 BFS 或 DFS 时，如何获取当前访问级别的信息？

Question

我正在考虑创建自己的序列化程序，并且我需要一种简单的方法来为给定的 .NET 类型编写属性访问者，以便获取每个属性上的属性（公司嵌套的）。

看来最简单的方法是从DFS或BFS的迭代版本开始遍历所有属性，所以我开始写下面的代码：

public static class Algorithms
{
    public static IEnumerable<TNode> DfsIterativeTraverse<TNode>(this TNode node, Func<TNode, IEnumerable<TNode>> childNodeSelectors) 
    {
        if (node == null)
        {
            yield break;
        }

        var stack = new Stack<TNode>();
        stack.Push(node);

        while (stack.Any()) 
        {
            var top = stack.Pop();
            foreach (var child in childNodeSelectors(top)) 
            {
                stack.Push(child);
            }
            yield return top;
        }
    }
    public static IEnumerable<TNode> BfsIterativeTraverse<TNode>(this TNode node, Func<TNode, IEnumerable<TNode>> childNodeSelectors) 
    {
        if (node == null)
        {
            yield break;
        }

        var queue = new Queue<TNode>();
        queue.Enqueue(node);

        while (queue.Any()) 
        {
            var front = queue.Dequeue();
            foreach (var child in childNodeSelectors(front))
            {
                queue.Enqueue(child);
            }
            yield return front;
        }
    }
}

然后将其应用于一些匿名的类以获取不同的属性：

public static class Program
{
    public static void Main(params string[] args)
    {
        var stuff = new
        {
            A1 = new
            {
                B1 = new
                {
                    D1 = 42
                },
                C1 = new
                {
                    E1 = "Hello"
                }
            },
            A2 = new
            {
                B2 = new
                {
                    D2 = 42
                },
                C2 = new
                {
                    E2 = "Hello"
                }
            }
        };

        var properties = stuff.GetType().GetProperties();

        foreach (var property in properties)
        {
            var childProperties = property.DfsIterativeTraverse(x =>
            {
                if (x.PropertyType.IsPrimitive|| x.PropertyType == typeof(string))
                {
                    return Enumerable.Empty<PropertyInfo>();
                }

                return x.PropertyType.GetProperties();
            });

            var count = 0;
            foreach (var childProperty in childProperties)
            {
                Console.WriteLine($"{$"\t".Repeat(count)}{childProperty.Name}: {childProperty.PropertyType.Name}");
                count++;
            }
        }

        Console.ReadKey();
    }
}

public static class StringExtensions
{
    public static string Repeat(this string source, int count)
    {
        var stringBuilder = new StringBuilder(source.Length * count);
        for (var i = 0; i < count; i++)
        {
            stringBuilder.Append(source);
        }

        return stringBuilder.ToString();
    }
}

但是这段代码returns:

A1: <>f__AnonymousType1`2
        C1: <>f__AnonymousType3`1
                E1: String
                        B1: <>f__AnonymousType2`1
                                D1: Int32
A2: <>f__AnonymousType4`2
        C2: <>f__AnonymousType6`1
                E2: String
                        B2: <>f__AnonymousType5`1
                                D2: Int32

然后我意识到我需要有关当前级别的信息才能使 Bx 和 Cx 处于同一级别。

我想过加一个要递增的计数，结果发现没那么简单。

Answer 1

其实很简单。

interface ILevel
{
    int Level { get; set; }
}


public static IEnumerable<TNode> DfsIterativeTraverse<TNode>(this TNode node, Func<TNode, IEnumerable<TNode>> childNodeSelectors)
    where TNode : class, ILevel
{
    if (node == null)
    {
        yield break;
    }

    var currentLevel = 0;
    node.Level = 0;

    var stack = new Stack<TNode>();
    stack.Push(node);

    while (stack.Any())
    {
        var top = stack.Pop();
        foreach (var child in childNodeSelectors(top))
        {
            child.Level = top.Level + 1;
            stack.Push(child);
        }
        yield return top;
    }
}

该代码并不完美，因为它修改了节点，但如果您的情况需要，您可以以更安全的方式重构它。无论如何，问题应该解决了，因为现在你的每个节点都应该有 Level 属性和初始化值。

最后一点……我希望编写自己的序列化程序是纯粹的教育项目。否则我会建议你搜索现有的。

迭代遍历 BFS 或 DFS 时，如何获取当前访问级别的信息？

How to have information about the current visited level when doing BFS or DFS traversal iteratively?

c#

.net

depth-first-search

breadth-first-search

visitor-pattern