algorithm - 在熟人列表中查找姓名的复杂性如何

Question

例如我有一个 person 类，它有 name 和 acquaintance 属性，name 是字符串，而 acquaintance 是人员数组。我想写一个方法，它接收一个名字作为参数，并在 person's acquaintance list 和 acquaintances of acquaintance list 等中找到它的名字，直到 person acquaintance 为 null 或找到名字。

代码如下。也可以有循环，如何避免。预先感谢您对这个问题的兴趣。

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

Answer 1

您可以在线性 (O(n)) 时间内执行此类操作。为此，您必须将图表保持为 adjacency list。

您可以对树进行一次转换(使用 DFS 遍历)，也可以将图最初保留为列表而不是树。

您可以在线性时间(如果您将使用 hashMap/hashTable/字典，甚至是恒定的 O(1) 时间)以及他的联系中轻松地在邻接列表中找到一个人。

否则你将不得不执行 DFS 遍历并保存访问节点的列表(集合)以避免循环。根据您将用于访问列表的数据结构，您可以有不同的复杂性 - 从 O(n) 到 O(n^2)。但是在所有情况下，每次遍历都需要 2n 个内存(例如，如果您有多个并行搜索)。