Как на графе, выделить все вершины в заданном радиусе?

Программирование на Юнити.

Как на графе, выделить все вершины в заданном радиусе

Сообщение Navigator_x 17 апр 2020, 13:53

Как на графе, выделить все вершины в заданном радиусе?
Попробовал прикинуть так, но гдет ошибаюсь в логике, потому что бывает в одну сторону 4 вершины обходит в другую 3
Может кто знает не рекурсивный способ для таких маневров?
Синтаксис:
Используется csharp
 
    [SerializeField] List<NodeGraph> used = new List<NodeGraph>();
    private void Build(NodeGraph node, int och )
    {
        if (used.Find(x => x == node) != null)
        {
            return;
        }
        if (och == 4) { return; }
        och++;
        used.Add(node);

        for (int i = 0; i < node.conectedNodes.Count; i++)
        {
            if (node.conectedNodes[i] != node) { Build(node.conectedNodes[i], och); }
        }
    }
 
Navigator_x
UNец
 
Сообщения: 13
Зарегистрирован: 01 май 2016, 15:33

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Cr0c 18 апр 2020, 02:40

Что значит радиус у графа и чем плох рекурсивный способ?
Аватара пользователя
Cr0c
Адепт
 
Сообщения: 3035
Зарегистрирован: 19 июн 2015, 13:50
Skype: cr0c81

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Navigator_x 18 апр 2020, 06:16

Под радиусом подразумеваю:
допустим все ребра у нас имеют одинаковый вес и нужно получить все вершины, которые удалены от стартовой на 2 вершины.
Рекурсивный метод не плох, но чет застрял, не пойму как обойти именно на заданном расстоянии вершины.
Изображение
Navigator_x
UNец
 
Сообщения: 13
Зарегистрирован: 01 май 2016, 15:33

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Cr0c 18 апр 2020, 12:55

Navigator_x писал(а):Под радиусом подразумеваю:
допустим все ребра у нас имеют одинаковый вес и нужно получить все вершины, которые удалены от стартовой на 2 вершины.
Рекурсивный метод не плох, но чет застрял, не пойму как обойти именно на заданном расстоянии вершины.

Вызываешь поиск с параметром расстояния, внутри вызываешь с уменьшенным расстоянием. В корне расстояние 2, в связанных расстояние 1 будет, в следующем - 0.
Аватара пользователя
Cr0c
Адепт
 
Сообщения: 3035
Зарегистрирован: 19 июн 2015, 13:50
Skype: cr0c81

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Navigator_x 18 апр 2020, 13:32

Cr0c писал(а):Вызываешь поиск с параметром расстояния, внутри вызываешь с уменьшенным расстоянием. В корне расстояние 2, в связанных расстояние 1 будет, в следующем - 0.

Чёт не особо понятно, откуда вызывать список с параметром расстояния, внутри чего вызывать с уменьшенным.
В приведённом коде такая же локика только плюсовался праметр, но так не работает.
Если есть возможность, распишите пожалуйста подробней идею
Navigator_x
UNец
 
Сообщения: 13
Зарегистрирован: 01 май 2016, 15:33

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение 1max1 18 апр 2020, 14:14

Синтаксис:
Используется csharp
class Node
{
    public string identificator = string.Empty;
    public List<Node> conectedNodes = new List<Node>();
}

class XXX : MonoBehaviour
{
    List<Node> GetNodesWithDistance(Node startNode, int distance)
    {
        List<Node> result = new List<Node>();

        if (distance != 0)
        {
            for (int i = 0; i < startNode.conectedNodes.Count; ++i)
            {
                var node = startNode.conectedNodes[i];

                result.Add(node);

                result.AddRange(GetNodesWithDistance(node, distance - 1));
            }
        }

        return result;
    }

    void Start()
    {
        var rootNode = new Node() { identificator = "root" };

        var rootNodes = new List<Node>();
        rootNodes.Add(new Node() { identificator = "root_0" });
        rootNodes.Add(new Node() { identificator = "root_1" });
        rootNodes.Add(new Node() { identificator = "root_2" });

        rootNode.conectedNodes = rootNodes;

        var otherNodes1 = new List<Node>();
        otherNodes1.Add(new Node() { identificator = "root_0_0" });
        otherNodes1.Add(new Node() { identificator = "root_0_1" });
        otherNodes1.Add(new Node() { identificator = "root_0_2" });

        rootNode.conectedNodes[0].conectedNodes = otherNodes1;

        var otherNodes2 = new List<Node>();
        otherNodes2.Add(new Node() { identificator = "root_0_0_0" });
        otherNodes2.Add(new Node() { identificator = "root_0_0_1" });
        otherNodes2.Add(new Node() { identificator = "root_0_0_2" });

        rootNode.conectedNodes[0].conectedNodes[0].conectedNodes = otherNodes2;

        foreach (var node in GetNodesWithDistance(rootNode, 1))
            print(node.identificator);

        print("---");

        foreach (var node in GetNodesWithDistance(rootNode, 2))
            print(node.identificator);

        print("---");

        foreach (var node in GetNodesWithDistance(rootNode, 3))
            print(node.identificator);
    }
}
Аватара пользователя
1max1
Адепт
 
Сообщения: 5505
Зарегистрирован: 28 июн 2017, 10:51

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Navigator_x 18 апр 2020, 16:55

Результат выдает с дублями в листе, но работает как надо, логику понял.
Большое спасибо.
Navigator_x
UNец
 
Сообщения: 13
Зарегистрирован: 01 май 2016, 15:33

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Navigator_x 18 апр 2020, 18:18

Следующий вопрос, а как получить только крайние вершины, то есть только те, которые на удалении в 2 вершины, не пробегая по всем вершинам в полученном результате измеряя расстояние до стартовой вершины?
Navigator_x
UNец
 
Сообщения: 13
Зарегистрирован: 01 май 2016, 15:33

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение 1max1 18 апр 2020, 18:30

не пробегая

Наверное никак.
В коде добавь условие:
Синтаксис:
Используется csharp
        if (distance != 0)
        {
            for (int i = 0; i < startNode.conectedNodes.Count; ++i)
            {
                var node = startNode.conectedNodes[i];

                 if (distance == 1)
                     result.Add(node);

                result.AddRange(GetNodesWithDistance(node, distance - 1));
            }
        }
Аватара пользователя
1max1
Адепт
 
Сообщения: 5505
Зарегистрирован: 28 июн 2017, 10:51

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Navigator_x 18 апр 2020, 19:02

1max1 писал(а):
не пробегая

Наверное никак.
В коде добавь условие:

Вот да, тоже так сделал, но например если вершины связанны, допустим
*****
*****
*****
вот так вершины стоят и все связанны, то он соответственно все выделит в радиусе.
Потому что считает, что если в вершину можно попасть например за 2 хода, любыми путями, то она подходит под условие, что в принципе не достигается поиском расстояния, так что в некоторых кейсах так даже лучше.
Navigator_x
UNец
 
Сообщения: 13
Зарегистрирован: 01 май 2016, 15:33

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Cr0c 18 апр 2020, 22:15

Запоминай пройденные и потом игнорируй их
Аватара пользователя
Cr0c
Адепт
 
Сообщения: 3035
Зарегистрирован: 19 июн 2015, 13:50
Skype: cr0c81

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Tolking 18 апр 2020, 22:25

:D Изучайте алгоритмы поиска пути!!!
Ковчег построил любитель, профессионалы построили Титаник.
Аватара пользователя
Tolking
Адепт
 
Сообщения: 2714
Зарегистрирован: 08 июн 2009, 18:22
Откуда: Тула

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Cr0c 18 апр 2020, 23:07

Тут скорее построение волновой карты :-B
Аватара пользователя
Cr0c
Адепт
 
Сообщения: 3035
Зарегистрирован: 19 июн 2015, 13:50
Skype: cr0c81

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Tolking 18 апр 2020, 23:19

Это один из алгоритмов поиска пути (волновой)... Алгоритм Дейкстры заточен под графы...
Ковчег построил любитель, профессионалы построили Титаник.
Аватара пользователя
Tolking
Адепт
 
Сообщения: 2714
Зарегистрирован: 08 июн 2009, 18:22
Откуда: Тула

Re: Как на графе, выделить все вершины в заданном радиусе?

Сообщение Cr0c 19 апр 2020, 00:48

Tolking писал(а):Это один из алгоритмов поиска пути (волновой)... Алгоритм Дейкстры заточен под графы...

Дейкстра - оптимизация волнового (совмещение с жадным)
Аватара пользователя
Cr0c
Адепт
 
Сообщения: 3035
Зарегистрирован: 19 июн 2015, 13:50
Skype: cr0c81

След.

Вернуться в Скрипты

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10