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

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

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

Сообщение Navigator_x 19 апр 2020, 08:35

В итоге реализовал на основе алгоритма обхода в ширину, не рекурсивным методом, возвращает только те вершины которые на заданном расстоянии.
Синтаксис:
Используется csharp
    List<NodeGraph> GetNodesInRadius(NodeGraph startNode, int radius)
    {
        List<NodeGraph> inRadiusResult = new List<NodeGraph>();
        List<NodeGraph> used = new List<NodeGraph>();
        Queue<NodeGraph> q = new Queue<NodeGraph>();
        q.Enqueue(startNode);
        used.Add(startNode);
        startNode.d = 0;
        while (q.Count > 0)
        {
            NodeGraph e = q.Dequeue();
            if (e.d == radius+1) break;
            if (e.d == radius) inRadiusResult.Add(e); //убрать if, если нужны все вершины в радиусе

            for (int i = 0; i < e.conectedNodes.Count; i++)
            {
                if (!used.Contains(e.conectedNodes[i]))
                {
                    e.conectedNodes[i].d = e.d + 1;
                    q.Enqueue(e.conectedNodes[i]);
                    used.Add(e.conectedNodes[i]);
                }
            }
        }
        return inRadiusResult;
    }
 
Navigator_x
UNец
 
Сообщения: 13
Зарегистрирован: 01 май 2016, 15:33

Пред.

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

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

Сейчас этот форум просматривают: GoGo.Ru [Bot] и гости: 6