algorithm - 在熟人名单中查找姓名的复杂性是什么

例如，我有一个person类，它有name和熟人属性，name是string，熟人是persons数组。我想写一个方法，接收一个名字作为param，并找到它的名字在个人的熟人名单和熟人名单等熟人，深，直到个人熟人是无效的或名字被发现。
下面是代码。也可以有循环，如何避免。
提前感谢你对这个问题的关心。

class P
{
    public string Name;
    public P[] Acquaintances;
    public P(string name, P[] acquaintances)
    {
        if (String.IsNullOrWhiteSpace(name))
        {
            throw new ArgumentException("Name cannot be null or white space.",
             "name");
        }

        this.Name = name;
        this.Acquaintances = acquaintances;
    }
    public bool FindAcquaintance(string name)
    {
        if (String.IsNullOrWhiteSpace(name))
        {
            throw new ArgumentException("Name cannot be null or white space.",
             "name");
        }
        if (Name.Equals(name))
        {
            return true;
        }
        if (Acquaintances == null || Acquaintances.Length == 0)
        {
            return false;
        }
        foreach (P acquaintance in this.Acquaintances)
        {
            if (acquaintance.Name.Equals(name))
            {
                return true;
            }
            if (acquaintance.FindAcquaintance(name))
            {
                return true;
            }
        }
        return false;
    }
}

用法

P person = new P("Alex",
            new P[] {
                new P("Bob",   new P[] { new P("James", new P[] { }) }),
                new P("Kavin", new P[] { new P("Brent", null) })
            });


bool found = person.FindAcquaintance("Brent");

最佳答案

你可以在线性（O（n））时间内执行这种操作。
为此，您必须将图形保持为adjacency list
您可以转换树（使用dfs遍历）一次，也可以将图形最初保留为列表而不是树。
你可以很容易地在线性时间（如果你将使用hashMap/hashTable/dictionary，甚至是常数O（1）时间）的邻接列表中找到一个人，以及他的联系。
否则，必须执行DFS遍历并保存已访问节点的列表（集）以避免周期根据访问列表中使用的数据结构，可以有不同的复杂度，从O（n）到O（n ^ 2）。但在所有情况下，每次遍历都需要2n内存（例如，如果有多个并行搜索）。