C# — поиск в ширину (BFS) с использованием очереди.

В этом примере мы напишем программу на языке C# для реализации поиска в ширину (BFS) с помощью Queue

Поиск в ширину (BFS) — это алгоритм для обхода или поиска структур данных дерева или графа. Он начинается с корня дерева (или некоторого произвольного узла графа) и сначала исследует соседние узлы, прежде чем перейти к соседям следующего уровня.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BreadthFirst
{
    class Program
    {
        public class Employee
        {
            public Employee(string name)
            {
                this.name = name;
            }

            public string name { get; set; }
            public List<Employee> Employees
            {
                get
                {
                    return EmployeesList;
                }
            }

            public void isEmployeeOf(Employee p)
            {
                EmployeesList.Add(p);
            }

            List<Employee> EmployeesList = new List<Employee>();

            public override string ToString()
            {
                return name;
            }
        }

        public class BreadthFirstAlgorithm
        {
            public Employee BuildEmployeeGraph()
            {
                Employee Eva = new Employee("Eva");
                Employee Sophia = new Employee("Sophia");
                Employee Brian = new Employee("Brian");
                Eva.isEmployeeOf(Sophia);
                Eva.isEmployeeOf(Brian);

                Employee Lisa = new Employee("Lisa");
                Employee Tina = new Employee("Tina");
                Employee John = new Employee("John");
                Employee Mike = new Employee("Mike");
                Sophia.isEmployeeOf(Lisa);
                Sophia.isEmployeeOf(John);
                Brian.isEmployeeOf(Tina);
                Brian.isEmployeeOf(Mike);

                return Eva;
            }

            public Employee Search(Employee root, string nameToSearchFor)
            {
                Queue<Employee> Q = new Queue<Employee>();
                HashSet<Employee> S = new HashSet<Employee>();
                Q.Enqueue(root);
                S.Add(root);

                while (Q.Count > 0)
                {
                    Employee e = Q.Dequeue();
                    if (e.name == nameToSearchFor)
                        return e;
                    foreach (Employee friend in e.Employees)
                    {
                        if (!S.Contains(friend))
                        {
                            Q.Enqueue(friend);
                            S.Add(friend);
                        }
                    }
                }
                return null;
            }

            public void Traverse(Employee root)
            {
                Queue<Employee> traverseOrder = new Queue<Employee>();

                Queue<Employee> Q = new Queue<Employee>();
                HashSet<Employee> S = new HashSet<Employee>();
                Q.Enqueue(root);
                S.Add(root);

                while (Q.Count > 0)
                {
                    Employee e = Q.Dequeue();
                    traverseOrder.Enqueue(e);

                    foreach (Employee emp in e.Employees)
                    {
                        if (!S.Contains(emp))
                        {
                            Q.Enqueue(emp);
                            S.Add(emp);
                        }
                    }
                }

                while (traverseOrder.Count > 0)
                {
                    Employee e = traverseOrder.Dequeue();
                    Console.WriteLine(e);
                }
            }
        }

        static void Main(string[] args)
        {
            BreadthFirstAlgorithm b = new BreadthFirstAlgorithm();
            Employee root = b.BuildEmployeeGraph();
            Console.WriteLine("Граф пересечения\n------");
            b.Traverse(root);

            Console.WriteLine("\nПоиск в графе\n------");
            Employee e = b.Search(root, "Eva");
            Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name);
            e = b.Search(root, "Brian");
            Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name);
            e = b.Search(root, "Soni");
            Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name);
            Console.ReadKey();
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace BreadthFirst

{

class Program

{

public class Employee

{

public Employee(string name)

{

this.name = name;

}

public string name { get; set; }

public List<Employee> Employees

{

get

{

return EmployeesList;

}

public void isEmployeeOf(Employee p)

{

EmployeesList.Add(p);

}

List<Employee> EmployeesList = new List<Employee>();

public override string ToString()

{

return name;

}

public class BreadthFirstAlgorithm

{

public Employee BuildEmployeeGraph()

{

Employee Eva = new Employee("Eva");

Employee Sophia = new Employee("Sophia");

Employee Brian = new Employee("Brian");

Eva.isEmployeeOf(Sophia);

Eva.isEmployeeOf(Brian);

Employee Lisa = new Employee("Lisa");

Employee Tina = new Employee("Tina");

Employee John = new Employee("John");

Employee Mike = new Employee("Mike");

Sophia.isEmployeeOf(Lisa);

Sophia.isEmployeeOf(John);

Brian.isEmployeeOf(Tina);

Brian.isEmployeeOf(Mike);

return Eva;

}

public Employee Search(Employee root, string nameToSearchFor)

{

Queue<Employee> Q = new Queue<Employee>();

HashSet<Employee> S = new HashSet<Employee>();

Q.Enqueue(root);

S.Add(root);

while (Q.Count > 0)

{

Employee e = Q.Dequeue();

if (e.name == nameToSearchFor)

return e;

foreach (Employee friend in e.Employees)

{

if (!S.Contains(friend))

{

Q.Enqueue(friend);

S.Add(friend);

}

return null;

}

public void Traverse(Employee root)

{

Queue<Employee> traverseOrder = new Queue<Employee>();

Queue<Employee> Q = new Queue<Employee>();

HashSet<Employee> S = new HashSet<Employee>();

Q.Enqueue(root);

S.Add(root);

while (Q.Count > 0)

{

Employee e = Q.Dequeue();

traverseOrder.Enqueue(e);

foreach (Employee emp in e.Employees)

{

if (!S.Contains(emp))

{

Q.Enqueue(emp);

S.Add(emp);

}

while (traverseOrder.Count > 0)

{

Employee e = traverseOrder.Dequeue();

Console.WriteLine(e);

}

static void Main(string[] args)

{

BreadthFirstAlgorithm b = new BreadthFirstAlgorithm();

Employee root = b.BuildEmployeeGraph();

Console.WriteLine("Граф пересечения\n------");

b.Traverse(root);

Console.WriteLine("\nПоиск в графе\n------");

Employee e = b.Search(root, "Eva");

Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name);

e = b.Search(root, "Brian");

Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name);

e = b.Search(root, "Soni");

Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name);

Console.ReadKey();

}

Вывод:

Граф пересечения

Eva
Sophia
Brian
Lisa
John
Tina
Mike

Поиск в графе

Eva
Brian
Сотрудник, не найден

Вывод:

Добавить комментарий Отменить ответ