图：TreeSet 未添加所有边

Question

我正在研究一个无向图问题。我有一个 Node class，其中包含 nodeName 和 List<Edge>。然后我有 Edge class，其中包含 Node start、Node end 和 weight。最后我有一个 Graph class 有一个实例变量 Map<String, Node>.

我想将所有不同的边添加到一个集合中，并根据边的权重以升序排列它们。因此，我选择 TreeSet 以独特的排序方式存储所有边。但是当我调用 addAllEdges() 时，它并没有添加所有的边。该图有 9 个顶点和 14 条边。然而，treeSet 只保存了其中的 10 个。

代码结构：

图表：

class Graph {
    private Map<String, Node> verticesMap = new HashMap<>();

    public void addEdge(String src, String dest, int weight) {
        Node srcNode = verticesMap.get(src) == null ? new Node(src) : verticesMap.get(src);
        Node destNode = verticesMap.get(dest) == null ? new Node(dest) : verticesMap.get(dest);
        Edge edge = new Edge(srcNode, destNode, weight);
        srcNode.getEdgeList().add(edge);
        verticesMap.put(src, srcNode);
        verticesMap.put(dest, destNode);
    }

    public Set<Edge> addAllEdges() {
        Set<Edge> allEdgesSet = new TreeSet<>(getComparatorBasedOnEdgeWeight());
        for (Node node : verticesMap.values()) {
            for (Edge edge : node.getEdgeList()) {
            // sysout for debugging purpose only
                if(allEdgesSet.add(edge)) {
                    System.out.println("Added edge: " + edge);
                } else {
                    System.out.println("Did not add edge: " + edge);
                }
            }
        }
        return allEdgesSet;
    }

    private Comparator<Edge> getComparatorBasedOnEdgeWeight() {
        return (e1, e2) -> Integer.compare(e1.getWeight(), e2.getWeight());
    }
}

节点：

class Node {
    private String name;
    private List<Edge> edgeList;

    public Node(String name) {
        this.name = name;
        edgeList = new ArrayList<>();
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Node other = (Node) obj;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return name;
    }
}

边缘：

class Edge {
    private Node src;
    private Node dest;
    private int weight;

    public Edge(Node src, Node dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((dest == null) ? 0 : dest.hashCode());
        result = prime * result + ((src == null) ? 0 : src.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Edge other = (Edge) obj;
        if (dest == null) {
            if (other.dest != null)
                return false;
        } else if (!dest.equals(other.dest))
            return false;
        if (src == null) {
            if (other.src != null)
                return false;
        } else if (!src.equals(other.src))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return src + "-->" + dest + "[" + weight + "]";
    }
}

测试：

 public class Test {
        public static void main(String[] args) {
            Graph graph = new Graph();
            graph.addEdge("A", "B", 4);
            graph.addEdge("B", "A", 4);
            graph.addEdge("A", "I", 8);
            graph.addEdge("I", "A", 8);
            graph.addEdge("B", "C", 8);
            graph.addEdge("C", "B", 8);
            graph.addEdge("B", "I", 11);
            graph.addEdge("I", "B", 11);
            graph.addEdge("C", "H", 2);
            graph.addEdge("H", "C", 2);
            graph.addEdge("C", "D", 7);
            graph.addEdge("D", "C", 7);
            graph.addEdge("C", "F", 4);
            graph.addEdge("F", "C", 4);
            graph.addEdge("H", "I", 7);
            graph.addEdge("I", "H", 7);
            graph.addEdge("H", "G", 6);
            graph.addEdge("G", "H", 6);
            graph.addEdge("I", "G", 1);
            graph.addEdge("G", "I", 1);
            graph.addEdge("G", "F", 2);
            graph.addEdge("F", "G", 2);
            graph.addEdge("F", "D", 14);
            graph.addEdge("D", "F", 14);
            graph.addEdge("F", "E", 10);
            graph.addEdge("E", "F", 10);
            graph.addEdge("E", "D", 9);
            graph.addEdge("D", "E", 9);
            graph.addAllEdges();
        }
    }

输出：

Added edge: A-->B[4]
Added edge: A-->I[9]
Did not add edge: B-->A[4]
Added edge: B-->C[8]
Added edge: B-->I[11]
Did not add edge: C-->B[8]
Added edge: C-->H[2]
Added edge: C-->D[7]
Did not add edge: C-->F[4]
Did not add edge: D-->C[7]
Added edge: D-->F[14]
Did not add edge: D-->E[9]
Added edge: E-->F[10]
Did not add edge: E-->D[9]
Did not add edge: F-->C[4]
Did not add edge: F-->G[2]
Did not add edge: F-->D[14]
Did not add edge: F-->E[10]
Added edge: G-->H[6]
Added edge: G-->I[1]
Did not add edge: G-->F[2]
Did not add edge: H-->C[2]
Did not add edge: H-->I[7]
Did not add edge: H-->G[6]
Did not add edge: I-->A[9]
Did not add edge: I-->B[11]
Did not add edge: I-->H[7]
Did not add edge: I-->G[1]

Edges in the TreeSet:
[G-->I[1], C-->H[2], A-->B[4], G-->H[6], C-->D[7], B-->C[8], A-->I[9], E-->F[10], B-->I[11], D-->F[14]]

上面的输出显示它正在迭代 28 条边（14 个顶点 * 2）。我无法弄清楚为什么 treeSet 为那些甚至不存在于集合中的边返回 false。

Answer 1

TreeSet 使用 Comparator 进行排序，但也用于对象的唯一性。它不使用 equals() 或 hashCode().

您的 Comparator 也需要比较节点，例如使用节点名称。

此外，如果您的图表确实是 undirected，则您不需要执行 graph.addEdge("A", "B", 4) 和 graph.addEdge("B", "A", 4)，因为它们代表相同的无向边。无向边没有 "source" 或 "destination".

我建议您更改 Edge，将 src 和 dest 重命名为 node1 和 node2，并确保 [=21] 的名称=] 小于 node2.

的名称

这样，您的 Comparator 就可以简单地比较 weight、node1.name 和 node2.name:

private Comparator<Edge> getComparatorBasedOnEdgeWeight() {
    return (e1, e2) -> {
        int cmp = Integer.compare(e1.getWeight(), e2.getWeight());
        if (cmp == 0)
            cmp = e1.getNode1().getName().compareTo(e2.getNode1().getName());
        if (cmp == 0)
            cmp = e1.getNode2().getName().compareTo(e2.getNode2().getName());
        return cmp;
    };
}

图：TreeSet 未添加所有边

Graph: TreeSet is not adding all the edges

java

graph

set

treeset