Как создать ребра, распространяющиеся от одного узла относительно расстояния в графе

Question

У меня есть график, на котором мне нужно создать направленные ребра от одного узла ко всем узлам, которые находятся на определенном расстоянии от этого узла, направленные от начального узла к узлам, которые находятся на расстоянии. Затем он создает ребра из узлов, которые были на расстоянии от начального узла, до узлов, которые находятся на расстоянии от этих узлов, и продолжает работать, пока у каждого узла не будет хотя бы одного ребра.

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

//create patient zero
    graphVer.get(0).getValue().setInfected(true);
    graphVer.get(0).getValue().setRecentlyInfected(true);
    graphVer.get(0).getValue().setLevel(0);
    for(int i = 0; i < graphVer.size();i++) {
        for(int j = 0; j < graphVer.size();j++) {
            //checks each vertex against every other vertex, and if their distance is within limits and they aren't equal to each other, then create an edge between them
            if(distance(graphVer.get(i).getValue().getX(), graphVer.get(i).getValue().getY(),graphVer.get(j).getValue().getX(),graphVer.get(j).getValue().getY()) < dis.getRange()) {
                if(i != j) {
                    //makes sure that there is only one edge between two nodes and directs it based on where patient zero is
                    if(graphVer.get(i).getValue().getLevel() <= i && graphVer.get(j).getValue().getLevel() > graphVer.get(i).getValue().getLevel()) {
                        graphEdge.add(new Edge<>(0,graphVer.get(i),graphVer.get(j)));
                        graphVer.get(j).getValue().setLevel(i+1);
                    }
                }
            }
        }
    }

Я не включил код создания вершины, который просто случайным образом создает вершины в пределах квадратной границы, чтобы никто не перекрывался. graphVer - это массив всех вершин графа, а graphEdge - это список всех ребер графа.

Какой лучший способ сделать это, чтобы он каждый раз работал правильно?

Answer 1

Я указал на недостатки вашей спецификации в комментариях.

То, что я думаю , что вы хотите, концептуально, это начать с графа G из всех ребер (v, w), где dist (v, w) <=DIST.Это будет содержать много циклов.В этом графе вы хотите найти дерево T, обнаруженное путем поиска ширины сначала по начальной вершине. </p>

Чтобы достичь этого, вам не нужно строить G. Как вы уже поняли, вы можете выполнить итерациювсе пары вершин и проверьте их с помощью dist (v, w) <= DIST, чтобы обнаружить ребра в G по мере необходимости. </p>

BFS использует очередь.В итоге вы получите такой алгоритм:

Let x be the start vertex
Let N be a set initially containing all vertices (not yet infected)
Let Q be a queue for vertices
Let T be the initially empty set of tree edges
Add x to Q and remove it from N // Infect x.
while Q is not empty
  Pop vertex v from the head of Q
  for each vertex w in N // Iterate through all non-infected vertices
    if dist(v, w) < DIST
      Add edge v->w to T // w is now infected
      add w to the tail of Q
      remove w from N
return T

Это переводит почти строку за строкой в ​​Java.

Обратите внимание, что на выходе должно быть дерево, потому что каждая вершина w может быть удалена из N только один раз.Следовательно, в T может быть только одно ребро формы v-> w. Это означает, что каждая вершина имеет не более одного родителя, что является определением ориентированного дерева.

Как я уже говорил в комментариях, нетгарантируйте, что это будет включать все вершины в дереве, если промежутки между ними слишком велики.

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

Обратите внимание, что вершины не включены, потому что они слишком далеко от любого источника инфекции.Это правильно.

Answer 2

Ваша формулировка немного сбивает с толку, разве вы не пытаетесь достичь только узлов, которые находятся на заданном расстоянии от исходного узла? Если это так, то «иногда узлы, расположенные дальше от исходного узла, не получают ребер», - это то, чего вы хотите.