Блог

Я собираюсь предложить другое решение. Первое наблюдение, которое нам нужно сделать, это то, что мы на самом деле не хотим получать Map<Integer, Set<Integer>> . Ключ, например, 5, ничем не отличается от любого другого узла. Причина, по которой это ключ, заключается только в том, что он предшествует в списке. Поэтому я собираюсь построить:

 Set<Set<Integer>> map
 

Где для каждых 2 наборов в этом наборе они имеют пустое пересечение.

Алгоритм

1. Для каждого ребра:
   1. Извлеките 2 вершины.
   2. создайте набор с этими 2 узлами.
   3. Перебрать все существующие наборы:
      1. Объедините все множества, которые имеют одну из двух вершин, в новый набор.
      2. Удалите все наборы из предыдущего шага.
      3. Добавьте агрегированный набор.

Реализация

 public static void process(List<String> input) {
    Set<Set<Integer>> map = new HashSet<>();
    for (String in : input) {
        String[] arr = in.split(" ");
        int a1 = Integer.parseInt(arr[0]);
        int a2 = Integer.parseInt(arr[1]);

        Set<Integer> aggregatedSet = new HashSet<>();
        Set<Set<Integer>> setsToRemove = new HashSet<>();
        aggregatedSet.add(a1);
        aggregatedSet.add(a2);
        for (Iterator<Set<Integer>> it = map.iterator(); it.hasNext(); ) {
            Set<Integer> currentNodes = it.next();
            if (currentNodes.contains(a1) || currentNodes.contains(a2)) {
                aggregatedSet.addAll(currentNodes);
                setsToRemove.add(currentNodes);
            }
        }

        map.removeAll(setsToRemove);
        map.add(aggregatedSet);
    }
    System.out.println(map);
}
 

Следующее:

 List<String> edges = Arrays.asList("6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16");
process(edges);
 

Будет выводить:

 [[12, 14], [16, 1, 5, 6, 9, 11, 13, 15]]
 

И следующее:

 List<String> edges = Arrays.asList("40 22","60 6","22 39","43 40","22 55","48 57","42 41","22 57","6 42","33 74","70 46","4 11","6 28","22 79","61 34","77 40","4 8","72 26","62 50","72 51","1 79","34 29","77 41","2 48","43 2","62 45","43 17","19 33","76 4","35 54");
process(edges);
 

Будет выводить:

 [[1, 2, 6, 39, 40, 41, 42, 43, 77, 79, 48, 17, 22, 55, 57, 28, 60], [4, 8, 11, 76], [70, 46], [51, 72, 26], [35, 54], [34, 29, 61], [50, 45, 62], [33, 19, 74]]
 

Я довольно смущен вашим кодом. Разумным графическим представлением является отображение от узла к набору смежных узлов, т. Е. Связанных направленным ребром. Если граф неориентированный, то будут зеркальные отображения: из A -> {..B..} и B -> {..A ..} для каждого ребра A, B.

Для реализации этого вам нужно что-то вроде:

 class GraphForFun {
 static void addDirectedEdge(Map<Integer, Set<Integer>> graph, int a, int b) {
    Set<Integer> adjacent = graph.get(a);
    if (adjacent == null) {
      adjacent = new HashSet<>();
      graph.put(a, adjacent);
    }
    adjacent.add(b);
  }

  static Map<Integer, Set<Integer>> getGraph(List<String> edges) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for (String edge : edges) {
      String vertexNumbers[] = edge.split("\s ");
      int a = Integer.parseInt(vertexNumbers[0]);
      int b = Integer.parseInt(vertexNumbers[1]);
      addDirectedEdge(graph, a, b);
      addDirectedEdge(graph, b, a); // Remove if graph is directed.
    }
    return graph;
  }

  public static void main(String[] args) {
    String[] edges = {"6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16"};
    Map<Integer, Set<Integer>> graph = getGraph(Arrays.asList(edges));
    System.out.println(graph);
  }
}
 

Это выводит

 {16=[1, 15], 1=[16], 5=[9], 6=[11], 9=[5, 11, 15], 11=[6, 9], 12=[14], 13=[15], 14=[12], 15=[16, 9, 13]}
 

Из того, что я понял, вы в основном отслеживаете острова в своем графике. Поскольку я не владею Java, я напишу простой алгоритм для решения вашей цели.

1. Создайте a graph[] , где каждый ключ сопоставляется со списком смежности. Для каждого i j из ваших входных данных добавьте j to graph[i] и i to graph[j] .
2. Создайте карту output , которую мы сейчас заполним.
3. Запустите DFS с первого узла (или любого узла, который вы предпочитаете). Функция DFS будет выглядеть так

 dfs (node, source):
    if not visited node:
        visited[node] = true
        append node to output[source]
        for neighbour in graph[node]:
            dfs(neighbour, source)
 

4. Проверьте, не посещен ли какой-либо узел. Если вы найдете такое node , вам просто нужно позвонить dfs (node, node) .

Это даст вам желаемую карту островов, которая вам нужна.

Что вы хотите, так это найти связанные компоненты (точнее, по-видимому, только их размер)

Вы можете искать лучшие алгоритмы.

После обучения давайте заново откроем некоторое колесо:

• Если между двумя узлами есть ребро, свяжите их
• При связывании двух узлов один является пожирателем, а другой — съеденным: свяжите каждый узел съеденных ссылок с пожирателем

например

 a1    b1
|     |
a2    b2
|     |
A     B
 

• a1,...a2 связаны ли узлы с узлом A
• b1,...b2 связаны ли узлы с узлом B

при слиянии A и B , (например) скажем A , является пожирателем, B съеденный затем ссылается b1, b2, B на A

 a1    
|     
a2 - b1 - b2 - b // notice B lowercase since belongs to "group" A
|     
A
 

Ниже приведена реализация js (java заняла бы у меня слишком много времени). Надеюсь, это достаточно близко к псевдокоду?

 /*
  strToGroupId     groupIdToGroup 
  _____________________________________
  strA ------> gA -----> { strA }
  strB --v
  strC -- ---> gB -----> { strB, strC }

*/
strToGroupId = new Map // str -> int
groupIdToGroup = new Map // int -> Set<str>
const link = ([strA, strB]) => {
  // assign a group if new node
  if (!strToGroupId.has(strA)) {
    strToGroupId.set(strA, strA),
    groupIdToGroup.set(strA, new Set([strA]))
  }
  if (!strToGroupId.has(strB)) {
    strToGroupId.set(strB, strB),
    groupIdToGroup.set(strB, new Set([strB]))
  }

  const gA = strToGroupId.get(strA)
  const gB = strToGroupId.get(strB)

  if (gA === gB) return
  // need to merge
  const eaters = groupIdToGroup.get(gA)
  const eatens = groupIdToGroup.get(gB)
  for (const n of eatens) {
    eaters.add(n)
    strToGroupId.set(n, gA) // the eateN now links to gA instead of gB
  }
  groupIdToGroup.delete(gB) // gB does not exist anymore
}
const data = ["6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16"]
data.map(x => x.split(' ')).forEach(link)
console.log([...groupIdToGroup.values()].map(aSet => [...aSet])) 

Интересная проблема. Я решил создать список смежности (карта идентификаторов узлов и их непосредственных дочерних элементов), а затем выполнить поиск, чтобы найти общие пути. Карта visitedAndGroupId (уродливое имя!) Используется как для отслеживания посещенных узлов, так и для того, к какой группе они принадлежат. Ключ — это исходный узел, а значение — идентификатор группы. Наконец, мы перебираем посещенную карту и создаем группы и их содержимое, чтобы подготовить выходные данные.

 private static HashMap<Integer,Set<Integer>> adjacencyList;
    private static Map<Integer, Integer> visitedAndGroupId = new HashMap<>();
    private static int groupId = 0;

    public static void main(String[] args) {
        List<String> pairs = Arrays.asList("6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16");
        adjacencyList = buildAdjacencyList(pairs);

        // find the groups
        // visit each node then its children then their children etc,
        // populate map of visited ids along with group id.
        for (Map.Entry<Integer,Set<Integer>> entry: adjacencyList.entrySet()){
            if(!visitedAndGroupId.containsKey(entry.getKey())) {
                search(entry.getKey(), entry.getValue());
                groupId  ;
            }
        }

        // build groups container
        final List<Group> groups = new ArrayList<>(groupId-1);
        for (int i = 0; i < groupId; i  ) {
            groups.add(new Group(i));
        }

        // populate groups
        // each key is our original id and the associated value is the group it belongs to
        visitedAndGroupId.forEach((id,groupId)->groups.get(groupId).addItem(id));

        // print output
        System.out.print("{ ");
        groups.forEach(System.out::print);
        System.out.print("} ");
    }

    private static void search(int parent, Set<Integer> children) {
        if(!visitedAndGroupId.containsKey(parent)){
            visitedAndGroupId.put(parent, groupId);
            for (int c:children){
                search(c, adjacencyList.get(c));
            }
        }
    }
 

Построение списка смежности:

 private static HashMap<Integer,Set<Integer>> buildAdjacencyList(List<String> vertexPairs) {

        // build adjacency list
        HashMap<Integer,Set<Integer>> adjacencyList = new HashMap<>();
        int group = -1;
        for(String s:vertexPairs){
            String[] pair = s.split(" ");
            int v1 = Integer.parseInt(pair[0]);
            int v2 = Integer.parseInt(pair[1]);

            if(!adjacencyList.containsKey(v1) amp;amp; !adjacencyList.containsKey(v2)){
                // new pair
                adjacencyList.put(v1, new HashSet<>(Arrays.asList(v2)));
                adjacencyList.put(v2, new HashSet<>(Arrays.asList(v1)));
                continue;
            } else if (!adjacencyList.containsKey(v1) amp;amp; adjacencyList.containsKey(v2)){
                // one vertex is new, one vertex exists
                addAndUpdate(v1,v2,adjacencyList);
                continue;
            } else if (adjacencyList.containsKey(v1) amp;amp; !adjacencyList.containsKey(v2)){
                // one vertex is new, one vertex exists
                addAndUpdate(v2,v1,adjacencyList);
                continue;
            } else {
                // vertices already in hashset but this is a new edge between the two
                adjacencyList.get(v1).add(v2);
                adjacencyList.get(v2).add(v1);
            }
        }

        return adjacencyList;
    }

    private static void addAndUpdate(int newV, int existingV, HashMap<Integer, Set<Integer>> adjacencyList) {
        Set<Integer> t = adjacencyList.get(existingV);
        Set<Integer> newSet = new HashSet<>();
        newSet.add(existingV);
        adjacencyList.put(newV,newSet);
        t.add(newV);
    }
 

Вот класс Group: (геттеры / сеттеры не используются для краткости)

 private static class Group {
        public int GroupId;
        public int Count=0;
        public List<Integer> Contents;

        public Group(int groupId) {
            GroupId = groupId;
            Contents = new ArrayList<>();
        }

        public void addItem(int n){
            Count  ;
            Contents.add(n);
        }

        @Override
        public String toString() {
            return  " "   Count  
                    "="   Contents ", ";
        }
    }
 

Вывод:
для ввода («6 11», «9 5», «11 9», «15 9», «13 15», «12 14», «15 16», «1 16») является

 {  8=[16, 1, 5, 6, 9, 11, 13, 15],  2=[12, 14], } 
 

и
для ввода («40 22″,»60 6″,»22 39″,»43 40″,»22 55″,»48 57″,»42 41″,»22 57″,»6 42″,»33 74″,»70 46″,»4 11″,»6 28″,»22 79″,»61 34″,»77 40″,»4 8″,»72 26″,»62 50″,»72 51″,»1 79″,»34 29″,»77 41″,»2 48″,»43 2″,»62 45″,»43 17″,»19 33″,»76 4″,»35 54») является

 {  17=[1, 2, 6, 77, 79, 17, 22, 28, 39, 40, 41, 42, 43, 48, 55, 57, 60],  4=[4, 8, 11, 76],  2=[70, 46],  3=[72, 26, 51],  3=[74, 19, 33],  3=[29, 34, 61],  2=[35, 54],  3=[45, 50, 62], } 
 

Хорошо, пара наблюдений.

• Порядок данных представляется важным. Если вы переместитесь [6,11] сразу после [11,9] того, как он будет работать так, как вы ожидаете. На самом деле, я изменил ваш входной массив на a List , чтобы я мог его перетасовать. Каждый раз ваш результат существенно отличается от предыдущей итерации. Это может дать подсказку о том, в чем заключается проблема.
• Я рекомендую вам щедро разбрызгивать некоторые операторы печати в ключевых местах, чтобы выполнять state проверки как path, чтобы понять, что он делает.
• Это не имеет никакого отношения к вашей проблеме, но вот пример вашего кода. У вас уже есть set, поэтому нет необходимости получать его снова, чтобы добавить значение. Просто используйте set то, что у вас уже есть.

 Set<Integer> set = map.get(k);
 
if (set.contains(first)) {
        map.get(k).add(second);
        found = true;
        break;
}
 

Это также помогло бы другим помочь вам, если бы вы объяснили, как вы ожидаете, что это будет работать. Не все свободно владеют теорией графов.