What would be the complexity of finding a name in acquaintance list

user_4176599 0
Viewed 183

For example i have a person class, it has name and acquaintance properties, name is string while acquaintance is array of persons. I would like to write a method which receives a name as param and find it the name in person's acquaintance list and acquaintances of acquaintance list and so on, deep until person acquaintance is null or name is found.

Following is the code. Also there can be circular loop, how to avoid that. Thanks in advance for your interest in the question.

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

Usage

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");
data-structures algorithm
1 Answers

You can perform that kind of operation in a linear (O(n)) time. To do that you have to keep your graph as an adjacency list

You can either transform the tree (using DFS traversal) once or just keep the graph initially as the list rather than the tree.

You can easily find a person in adjacency list in linear time (or even constant O(1) time if you'll be using hashMap/hashTable/dictionary) as well as he's connections.

Otherwise you'll have to perform DFS traversal and save a list (set) of visited nodes to avoid cycles. Depending on what data structure you'll be using for visited list you can have different complexities - from O(n) to O(n^2). But in all cases you'll require 2n of memory IN EACH TRAVERSAL (e.g. if you have several searches that will happen in parallel).

user_12665000
Related