pitchcontrol
2/27/2019 - 10:44 AM

Поиск в ширину (BFS)

public class BFS
{
    private static bool Search(string name, Dictionary<string, string[]> dict)
    {
        var searchQueue = new Queue<string>();
        foreach (string item in dict["you"])
        {
            searchQueue.Enqueue(item);
        }

        var searched = new HashSet<string>();
        while (searchQueue.Count != 0)
        {
            var person = searchQueue.Dequeue();
            if (!searched.Contains(person))
            {
                if (person == name)
                    return true;
                else
                    foreach (string item in dict[person])
                    {
                        searchQueue.Enqueue(item);
                        searched.Add(person);
                    }
            }
        }

        return false;
    }

    public static void Show()
    {
        var graph = new Dictionary<string, string[]>();

        graph.Add("you", new[] {"alice", "bob", "clarie"});
        graph.Add("bob", new[] {"anuj", "peggy"});
        graph.Add("alice", new[] {"peggy"});
        graph.Add("clarie", new[] {"thom", "jonny"});
        graph.Add("anuj", new String[0]);
        graph.Add("peggy", new String[0]);
        graph.Add("thom", new String[0]);
        graph.Add("jonny", new String[0]);


        Console.WriteLine(Search("thom", graph));
        Console.WriteLine(Search("anuj", graph));
        Console.WriteLine(Search("peggy", graph));
        Console.WriteLine(Search("somebody", graph));
    }
}