Infant name [adjacency matrix and DFS of connected components]

Preface

One of the basic skills of graph , Given nodes and edges ( Node pair ), Count the number of connected components , Of course, it can also be given in other forms , For example, the baby's name . It can be used to practice the physical structure of common graphs – Adjacency matrix .

One 、 Baby's name

Two 、 Adjacency matrix and DFS

package everyday;

import java.util.*;

//  Baby's name 
public class TrulyMostPopular {
    
    /* target: The frequencies with similar names add up , Take the smallest name in the dictionary as a representative .  How to deal with similar names ？ The adjacency table can be used to handle , Then traverse each connected component . */
    Map<String, Set<String>> graph = new HashMap<>();

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
    
        //  according to synonyms To build a map 
        buildGraph(synonyms);
        //  Record the frequency of each word .
        Map<String, Integer> val = new HashMap<>();
        for (String name : names) {
    
            int idx = getRealNameIdx(name);
            String key = name.substring(0, idx);
            int value = Integer.parseInt(name.substring(idx + 1, name.length() - 1));
            val.put(key, value);
            // bug1:graph There are no such isolated points in 
            addNode(key);
        }
        //  Traverse all connected components 
        List<String> ans = new ArrayList<>();
        for (String name : names) {
    
            name = name.substring(0, getRealNameIdx(name));
            if (graph.containsKey(name)) {
    
                min = (char) ('z' + 1) + "";
                int total = dfs(name, val);
                ans.add(min + '(' + total + ')');
            }
        }
        return ans.toArray(new String[0]);
    }

    String min;

    private int dfs(String name, Map<String, Integer> val) {
    
        //  Get the smallest name 
        if (val.containsKey(name) && min.compareTo(name) > 0) min = name;
        //  The result is itself , Add all adjacent nodes .
        int rs = val.getOrDefault(name, 0);
        //  Get all the next node 
        Set<String> next = graph.get(name);
        //  Don't go through the nodes .
        graph.remove(name);
        if (null == next) return rs;
        for (String s : next) {
    
            //  Only the UN calculated node values are calculated .
            if (graph.containsKey(s))
                rs += dfs(s, val);
        }
        return rs;
    }

    private int getRealNameIdx(String name) {
    
        int n = name.length();
        for (int i = name.length() - 1; i >= 0; i--) {
    
            if (Character.isLetter(name.charAt(i))) break;
            --n;
        }
        return n;
    }

    private void buildGraph(String[] synonyms) {
    
        for (String synonym : synonyms) {
    
            String[] strs = synonym.split(",");
            addEdge(strs[0].substring(1), strs[1].substring(0, strs[1].length() - 1));
        }
    }

    private void addEdge(String node, String another) {
    
        //  Add a node 
        addNode(node);
        addNode(another);
        //  Set the edge 
        graph.get(node).add(another);
        graph.get(another).add(node);
    }

    private void addNode(String node) {
    
        if (!graph.containsKey(node)) graph.put(node, new HashSet<>());
    }
}

summary

1） Find the connected component variant .
2） The concrete implementation of adjacency matrix .
notes ： Connected components and union search sets （ initialization / Merge / Find the root node ） Precise connection , We can use the union search set solution .

reference

[1] LeetCode Baby's name