Как найти связанные элементы дороги в дереве

Question

У меня есть список линий и точек, и мне нужно получить список связанных линий на основе точек.

Ввод - Линия и его 2 точки, поэтому в приведенном выше примере ввод -

В табличном формате

А на выходе должно быть 2 списка [1,2,3,4,5,6,7] и [8]

Я создавал карту от точки к списку линий, которым она принадлежит

А - 1

B - 1,2,3

С - 2 ...

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

Answer 1

Одним из решений является создание смежной карты точек к точкам-линиям.

Вы определяете, какие соседние точки данной точки и какие линии:

class PointAdj {
    String point;
    String line;//Or int
}

Определить карту как:

Map<String, List<PointAdj>> pontAdjMap = new HashMap<>();

Начните читать со стола и заполните карту:

(я полагаю, что вход представляет собой двумерный массив с именем input)

for (int i =0; i < input.length; i++) {

    String[] row = input[i];
    List<PointAdj>> adj = pontAdjMap.putIfAbsent(row[1], new ArrayList<>());
    if(adj == null) {
        adj = pontAdjMap.get(row[1]);
    }
    adj.add(new PointAdj(row[2], row[0]));
    //Also put the reverse side
}

Теперь pontAdjMap содержит все точки с соседними точками.

Теперь определите список Set, чтобы добавить линии, зациклить карту и как можно больше добавлять линий.

использовать очередь для непрерывного прохождения смежных точек;

List<Set<String>> lines = new ArrayList<>();
final Set<String> calculated = new HashSet();//Takes care of redundant processing of points;
pontAdjMap.keySet().foreach(pointInMap->{
    Set<String> lineSet = new HashSet();
    Queue<String> queue = new LinkedList<String>();
    queue.offer(pointInMap);
    while(!queue.isEmpty()) {
        String point = queue.poll();
        if(calculated.add(point)) {
            for(PointAdj pa: pontAdjMap.get(point)) {
                lineSet.add(pa.line);
                queue.offer(pa.point);
            }
        }
    }
    if(lineSet.size() > 0) {
        lines.add(lineSet);
    }
});

Теперь строки должны быть конечным результатом.

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

Answer 2

3 и 5 разные линии? Если да, то очевидно, что каждая линия может иметь не более 2 баллов. Если нет, то табличный формат не подходит.

На вашем месте я бы сделал одну карту со строкой в ​​качестве ключа и списком точек в качестве значения. Затем создайте интерфейс, чтобы определить, принадлежит ли точка нескольким линиям одновременно.