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