BreadthFirstSearch/Program.cs - master - MarkMuzyka/Algorithms

BreadthFirstSearch/Program.cs
98 строк2 KB
Музыка Марк
[feat] Добавление алгоритма поиска в ширину
28 авг 2025, 22:00
28 авг 2025, 22:004de5699
using System;
using System.Collections.Generic;

namespace BreadthFirstSearch;

internal class Program
{
    public static void Main(string[] args)
    {
        var a = new Node { Level = 0 };
        var b = new Node();
        var c = new Node();
        var d = new Node();
        var e = new Node();
        var f = new Node { IsFinish = true };

        var dic = new Dictionary<Node, Node[]>()
        {
            { a, [b, c] },
            { b, [d, f] },
            { c, [d, e] },
            { d, [] },
            { e, [f] },
            { f, [] },
        };

        var cab = new Node { Level = 0 };
        var cat = new Node();
        var car = new Node();
        var mat = new Node();
        var bat = new Node { IsFinish = true };
        var bar = new Node();

        var dic2 = new Dictionary<Node, Node[]>()
        {
            { cab, [cat, car] },
            { cat, [mat, bat] },
            { car, [cat, bar] },
            { mat, [bat] },
            { bat, [] },
            { bar, [bat] },
        };

        var result = IsGotRoute(a, dic);
        Console.WriteLine($"IsGotRoute: {result.Item1}\nMin Route: {result.Item2}");

        var result2 = IsGotRoute(cab, dic2);
        Console.WriteLine($"IsGotRoute 2: {result2.Item1}\nMin Route 2: {result2.Item2}");
    }

    public static (bool, int?) IsGotRoute(Node first, Dictionary<Node, Node[]> dic)
    {
        var queue = new Queue<Node>();

        queue.Enqueue(first);

        while (true)
        {
            if (queue.Count == 0)
            {
                return (false, null);
            }

            var node = queue.Dequeue();

            if (node.IsChecked)
            {
                continue;
            }

            node.IsChecked = true;

            if (node.IsFinish)
            {
                return (true, node.Level);
            }

            foreach (var connection in dic[node])
            {
                if (!connection.Level.HasValue)
                {
                    connection.Level = node.Level + 1;
                }

                queue.Enqueue(connection);
            }
        }
    }
}

public class Node
{
    public bool IsFinish { get; set; }

    public bool IsChecked { get; set; }

    public int? Level { get; set; }
}