婴儿名字[连通分量之邻接矩阵与DFS]

前言

图的基本功之一，给定节点和边(节点对)，统计连通分量的个数，当然也可以以其他形式给出，例如婴儿名字。通过其可练习常见图物理结构实现–邻接矩阵。

一、婴儿名字

二、邻接矩阵与DFS

package everyday;

import java.util.*;

// 婴儿名字
public class TrulyMostPopular {
    
    /* target:有类似名字的频数加起来，取一个在字典上最小的名字作为代表。 如何处理类似名字？可用邻接表处理好，然后遍历每个连通分量。 */
    Map<String, Set<String>> graph = new HashMap<>();

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
    
        // 根据synonyms来建图
        buildGraph(synonyms);
        // 记录每个单词的频数。
        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中没有这些孤立的点
            addNode(key);
        }
        // 遍历所有连通分量
        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) {
    
        // 获取最小名字
        if (val.containsKey(name) && min.compareTo(name) > 0) min = name;
        // 结果为自身，再加所有相邻节点。
        int rs = val.getOrDefault(name, 0);
        // 得到所有next节点
        Set<String> next = graph.get(name);
        // 走过的节点就不要。
        graph.remove(name);
        if (null == next) return rs;
        for (String s : next) {
    
            // 只算未计算的节点值。
            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) {
    
        // 添加节点
        addNode(node);
        addNode(another);
        // 设置边
        graph.get(node).add(another);
        graph.get(another).add(node);
    }

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

总结

1）求连通分量变体。
2）邻接矩阵具体实现方式。
注：连通分量和并查集（初始化/合并/查找根节点）精密联系，可采用并查集解。

参考文献

[1] LeetCode 婴儿名字