CODEWITHSUNDEEP
javaalgorithmgraphconnected-componentsunion-find
gyoho
gyoho

Reputation: 899

Optimization for Find All Weakly Connected Components in Directed Graph Using Quick-Find Algorithm (Java)

I'm seeking to improve my solution to find all weakly connected components in a directed graph using Quick-Find algorithm.

Problem Statement

Given a list of DirectedGraphNode, find all islands (i.e weakly connected components). 

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

Thus, given following directed graph:

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]

The output should be as follows (order doesn't matter):

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

I solved this using Quick-Find algorithm. Code below:

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;
}

However, this algorithm in the worst case runs in O(N^3) since each time it needs to do linear search for union. I'm very curious if there is any way to improve this.

Thank you for your suggestion!

Upvotes: 4

Views: 888

Answers (1)

wookie919
wookie919

Reputation: 3134

This is an edited answer. Sorry that I was confused between weakly connected components and strongly connected components.

It's actually very straightforward to determine weakly connected components. Just convert all edges to be undirected and perform BFS or DFS.

The run time will be O(|V| + |E|) where V is the set of vertices and E is the set of edges.

Upvotes: 2

Related Questions