0

У меня есть карта по сути это граф. Где у каждой клетки есть массив контактов с которыми она связана. И у меня есть одна клетка и мне надо так сказать обойти всю карту, пробовал много чего, но постоянно 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);
    }
4
  • Поясните зачем вам этот обход, чего вы от него хотите? И покажите код класса Province
    – tym32167
    Commented 13 мар. 2023 в 1:32
  • @tym32167 как не странно просто хочу обойти и написать такой код чисто для себя, мне интересно как бы это выглядело код Province не скину он довольно большой(не влезет в ограничения сайта) и там нет ничего полезного для этой задачи кроме поля public List<Province> Contacts; Commented 13 мар. 2023 в 1:45
  • Ну идентификатор там есть? Equals/Gethashcode перегрузили? Вам результат в каком то порядке нужен?
    – tym32167
    Commented 13 мар. 2023 в 1:56
  • Порядок не важен, порядок наверное сам допишу если понадобится, Equals/Gethashcode не перегружал. Мне главное принцип Commented 13 мар. 2023 в 2:15

1 ответ 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();    
}

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

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

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

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

1
  • да этот класс примерно так и выглядит, если убрать всякий код который там двигает войска по клеткам и за дипломатию отвечает. А так спасибо большое, попробую Commented 13 мар. 2023 в 2:12

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.