如何将Java整数型拓扑排序类修改为支持字符串节点？

嘿，我完全懂你这几周的困扰——原本好好的整数型拓扑排序类，想改成支持"a"、"b"这类字符串节点，结果类型转换错误像甩不掉的尾巴，哪怕把所有整数类型都删了也没用对吧？别愁，我给你两种实用的解决方案，应该能彻底搞定这个问题。

方案一：用泛型重构，直接支持任意类型节点 #

这种方法最彻底，把整个类改成泛型，让它能兼容字符串、整数甚至自定义对象。核心思路是把原来依赖整数索引的集合（比如ArrayList存邻接表、数组存入度）换成HashMap，用节点本身作为键来存储关系，彻底摆脱对整数的依赖。

修改后的完整代码示例：

import java.util.*;

public class TopologicalSort<T> {
    // 邻接表：键是节点，值是该节点指向的所有节点
    private final Map<T, List<T>> adjacencyList;
    // 入度表：键是节点，值是该节点的入度数值
    private final Map<T, Integer> inDegree;

    public TopologicalSort() {
        adjacencyList = new HashMap<>();
        inDegree = new HashMap<>();
    }

    public void addEdge(T from, T to) {
        // 确保两个节点都在集合中存在，避免空指针
        adjacencyList.computeIfAbsent(from, k -> new ArrayList<>());
        adjacencyList.computeIfAbsent(to, k -> new ArrayList<>());
        inDegree.putIfAbsent(from, 0);
        inDegree.putIfAbsent(to, 0);

        // 添加边并更新目标节点的入度
        adjacencyList.get(from).add(to);
        inDegree.put(to, inDegree.get(to) + 1);
    }

    public List<T> sort() {
        Queue<T> queue = new LinkedList<>();
        List<T> result = new ArrayList<>();

        // 把所有入度为0的节点加入队列
        for (Map.Entry<T, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
            }
        }

        while (!queue.isEmpty()) {
            T currentNode = queue.poll();
            result.add(currentNode);

            // 遍历当前节点的邻接节点，减少它们的入度
            for (T neighbor : adjacencyList.get(currentNode)) {
                int updatedDegree = inDegree.get(neighbor) - 1;
                inDegree.put(neighbor, updatedDegree);
                if (updatedDegree == 0) {
                    queue.add(neighbor);
                }
            }
        }

        // 检查是否存在环（结果长度不等于节点总数说明有环）
        if (result.size() != inDegree.size()) {
            throw new IllegalStateException("图中存在环，无法完成拓扑排序");
        }

        return result;
    }

    // 测试用例
    public static void main(String[] args) {
        TopologicalSort<String> ts = new TopologicalSort<>();
        ts.addEdge("a", "b");
        ts.addEdge("a", "c");
        ts.addEdge("b", "d");
        ts.addEdge("c", "d");

        List<String> sortedNodes = ts.sort();
        System.out.println("拓扑排序结果：" + sortedNodes);
        // 输出可能是 [a, b, c, d] 或 [a, c, b, d]，都是合法的拓扑序
    }
}

方案二：保留原有整数逻辑，用HashMap做字符串到整数的映射 #

如果不想大改原有代码的核心逻辑，这种方法更省心：在类里加一个映射表，把每个字符串节点对应到唯一的整数ID，对外暴露的方法接收字符串，内部自动转换成整数处理，原有拓扑排序的逻辑几乎不用动。

修改后的代码示例：

import java.util.*;

public class TopologicalSort {
    private final List<List<Integer>> adjacencyList;
    private final int[] inDegree;
    // 字符串节点 -> 整数ID的映射
    private final Map<String, Integer> nodeToId;
    // 整数ID -> 字符串节点的反向映射，用于最终结果转换
    private final Map<Integer, String> idToNode;
    private int nodeCount;

    public TopologicalSort() {
        adjacencyList = new ArrayList<>();
        inDegree = new int[100]; // 可以根据需求调整初始大小，或者用动态数组
        nodeToId = new HashMap<>();
        idToNode = new HashMap<>();
        nodeCount = 0;
    }

    // 内部方法：获取字符串节点对应的整数ID，不存在则新建
    private int getNodeId(String node) {
        if (!nodeToId.containsKey(node)) {
            nodeToId.put(node, nodeCount);
            idToNode.put(nodeCount, node);
            adjacencyList.add(new ArrayList<>());
            inDegree[nodeCount] = 0;
            nodeCount++;
        }
        return nodeToId.get(node);
    }

    // 对外暴露的addEdge方法，接收字符串参数
    public void addEdge(String from, String to) {
        int fromId = getNodeId(from);
        int toId = getNodeId(to);

        adjacencyList.get(fromId).add(toId);
        inDegree[toId]++;
    }

    public List<String> sort() {
        Queue<Integer> queue = new LinkedList<>();
        List<String> result = new ArrayList<>();

        // 入度为0的节点加入队列
        for (int i = 0; i < nodeCount; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        int processedNodes = 0;
        while (!queue.isEmpty()) {
            int currentId = queue.poll();
            result.add(idToNode.get(currentId));
            processedNodes++;

            for (int neighborId : adjacencyList.get(currentId)) {
                inDegree[neighborId]--;
                if (inDegree[neighborId] == 0) {
                    queue.add(neighborId);
                }
            }
        }

        if (processedNodes != nodeCount) {
            throw new IllegalStateException("图中存在环，无法完成拓扑排序");
        }

        return result;
    }

    // 测试用例
    public static void main(String[] args) {
        TopologicalSort ts = new TopologicalSort();
        ts.addEdge("a", "b");
        ts.addEdge("a", "c");
        ts.addEdge("b", "d");
        ts.addEdge("c", "d");

        List<String> sortedNodes = ts.sort();
        System.out.println("拓扑排序结果：" + sortedNodes);
    }
}

为什么你之前会遇到类型转换错误？ #

大概率是你还在试图用字符串去适配原来依赖整数索引的集合（比如直接把字符串当成ArrayList的索引），或者没有完全替换掉所有存储整数节点的结构。上面两种方法都彻底解决了这个问题：第一种直接用节点本身作为键，第二种把字符串转换成整数ID后再用原有逻辑处理。

内容的提问来源于stack exchange，提问作者Marky_rick