Оптимизация для поиска всех слабосвязанных компонентов в наведенном графике с использованием алгоритма быстрого поиска (Java)

Question

Я хочу улучшить свое решение, чтобы найти все слабосвязанные компоненты в ориентированном графе, используя Быстрый поиск алгоритм.

Постановка задачи

Учитывая список DirectedGraphNode, найти все острова (то есть слабо связанные компоненты).

public class DirectedGraphNode { 
    String val; 
    List<DirectedGraphNode> neighbors; 
} 

Таким образом, учитывая следующие ориентированного графа:

A —> B —> <— C 
    ^
    | 
    E <— F —> D —> G 

X -> <- Y 

node : neighbors 
    A : [B] 
    B : [C, E] 
    C : [B] 
    D : [G] 
    E : [] 
    F : [E, D] 
    G : [] 
    X : [Y] 
    Y : [X] 

Выходной сигнал должен быть следующим (порядок не имеет значения):

[ 
    [A, B, C, E, D, F, G], 
    [X, Y] 
] 

Я решил это с помощью быстрой Найти алгоритм. Код ниже:

public static List<List<Node>> connectedComponents(List<Node> nodes) { 
    if (nodes == null || nodes.size() == 0) { 
     throw new IllegalArgumentException("List node is empty"); 
    } 

    // Maintain array with name for each element 
    String[] labels = new String[nodes.size()]; 
    // Initially, set the labels of each element to itself 
    // Use HashMap to memorize the index 
    Map<String, Integer> map = new HashMap<>(); 
    for (int i = 0; i < labels.length; i++) { 
     labels[i] = nodes.get(i).val; 
     map.put(nodes.get(i).val, i); 
    } 

    for (Node node : nodes) { 
     if (node.neighbors == null || node.neighbors.isEmpty()) { 
      continue; 
     } 

     int changerIdx = map.get(node.val); 
     for (Node nbr : node.neighbors) { 
      int changeeIdx = map.get(nbr.val); 
      String symbol = labels[changeeIdx]; 
      for (int i = 0; i < labels.length; i++) { 
       if (labels[i] == symbol) { 
        labels[i] = labels[changerIdx]; 
       } 
      } 
     } 
    } 
    return createIslandList(labels, nodes); 
} 

private static List<List<Node>> createIslandList(String[] labels, List<Node> nodes) { 
    List<List<Node>> res = new ArrayList<List<Node>>(); 
    if (labels == null || labels.length == 0) { 
     return res; 
    } 

    Map<String, List<Node>> map = new HashMap<String, List<Node>>(); 
    for (int i = 0; i < labels.length; i++) { 
     if (!map.containsKey(labels[i])) { 
      List<Node> island = new ArrayList<>(); 
      island.add(nodes.get(i)); 
      map.put(labels[i], island); 
     } else { 
      map.get(labels[i]).add(nodes.get(i)); 
     } 
    } 

    for (String key : map.keySet()) { 
     res.add(map.get(key)); 
    } 

    return res; 
} 

Однако этот алгоритм в худшем случае работает в O (N^3) поскольку каждый раз, когда он должен сделать линейный поиск союза. Мне очень любопытно, есть ли способ улучшить это.

Благодарим за предложение!

Answer 1

Это отредактированный ответ. Извините, что меня путают между слабосвязанными компонентами и сильно связанными компонентами.

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

Время выполнения будет O(|V| + |E|) где V - это набор вершин, а E - это набор ребер.