C# — поиск в глубину(DFS) с помощью списка.

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

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

namespace DefthFirst
{
    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 e)
            {
                EmployeesList.Add(e);
            }

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

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

        public class DepthFirstAlgorithm
        {
            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)
            {
                if (nameToSearchFor == root.name)
                    return root;

                Employee personFound = null;
                for (int i = 0; i < root.Employees.Count; i++)
                {
                    personFound = Search(root.Employees[i], nameToSearchFor);
                    if (personFound != null)
                        break;
                }
                return personFound;
            }

            public void Traverse(Employee root)
            {
                Console.WriteLine(root.name);
                for (int i = 0; i < root.Employees.Count; i++)
                {
                    Traverse(root.Employees[i]);
                }
            }
        }

        static void Main(string[] args)
        {
            DepthFirstAlgorithm b = new DepthFirstAlgorithm();
            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

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace DefthFirst

{

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 e)

{

EmployeesList.Add(e);

}

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

public override string ToString()

{

return name;

}

public class DepthFirstAlgorithm

{

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)

{

if (nameToSearchFor == root.name)

return root;

Employee personFound = null;

for (int i = 0; i < root.Employees.Count; i++)

{

personFound = Search(root.Employees[i], nameToSearchFor);

if (personFound != null)

break;

}

return personFound;

}

public void Traverse(Employee root)

{

Console.WriteLine(root.name);

for (int i = 0; i < root.Employees.Count; i++)

{

Traverse(root.Employees[i]);

}

static void Main(string[] args)

{

DepthFirstAlgorithm b = new DepthFirstAlgorithm();

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
Lisa
John
Brian
Tina
Mike

Поиск в графе

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

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