Проблема с обходом графа c#

Question

Проблема с обходом графа c#

Рейтинг: 0Ответов: 1Опубликовано: 13.03.2023

У меня есть карта по сути это граф. Где у каждой клетки есть массив контактов с которыми она связана. И у меня есть одна клетка и мне надо так сказать обойти всю карту, пробовал много чего, но постоянно StackOverflow Exception или зависает всё, пробовал гуглить, но не нашёл чего-то адекватного.

В игре есть класс карты где можно получить все клетки в игре или регионе, но мне просто интересно сделать такой обход для себя и может на будущее пригодится для некоторых задач.

Вот один из не рабочих вариантов:

    private static void Walk(Province root)
    {
        var provs = new List<Province>();
        provs.Add(root);
        while (true)
        {
            var childs = new List<Province>();
            foreach (var p in provs)
            {
                childs.AddRange(p.Contacts.FindAll(p => !provs.Contains(p)));
            }
            if(childs.Count == 0)
            {
                break;
            }
            provs.AddRange(childs);
        }
        Debug.Log(provs.Count);
    }

c# unity3d

Источник: Stack Overflow на русском

Answer 1

▲ 4Принят

Класса вашего у меня нет, так что я предсавлю, что он выглядит как то так

public class Province
{   
    public List<Province> Contacts {get;set;} = new List<Province>();   
}

Вот простейщий вариант обхода в ширину.

public List<Province> BFS(Province root)
{
    var q = new Queue<Province>();
    var visited = new HashSet<Province>();
    
    q.Enqueue(root);
    visited.Add(root);
    
    while(q.Count > 0)
    {
        var node = q.Dequeue();
        foreach(var c in node.Contacts)
        {
            if (visited.Contains(c)) continue;
            q.Enqueue(c);
            visited.Add(c);
        }
    }
    
    return visited.ToList();    
}

Если поменять очередь на стек, получите обход в глубину.

Ссылки почитать

Поиск_в_ширину

Поиск_в_глубину

Проблема с обходом графа c#

Ответы