java - 在 Java 中对图的边进行排序(基于邻接列表表示)

Question

我有一个图，它使用 HashMap 存储它的边，如下所示:

HashMap<Integer,LinkedList<Node>> adj;

定义节点的地方；

class Node
{
   int number;
   int weight;
}

例如

• 0 : <1,55> -> <2,54>//节点0连接到边权重为55的节点1和边权重为54的节点2
• 1 : <0,43> -> <2,44>//节点 1 连接到边权重为 43 的节点 0 和边权重为 43 的节点 2 边重 44

我需要获取按重量排序的边列表，但我不知道该怎么做。我正在尝试实现 Kruskal 的 MST。

是否可以对我定义的图进行排序？如果不是，请建议一种更好的存储方式。

Answer 1

让我们从创建一个 Edge 开始类:

class Edge implements Comparable<Edge> { // Important: must implement Comparable. More on this later
    public Node first; // first connected node
    public Node second; // second connected node
    public int weight; // move edge weight to Edge class

    @Override
    public int compareTo(Edge e) {
        if (weight < e.weight) {
            return -1;
        } else if (weight > e.weight) {
            return 1;
        } else {
            return 0;
        }
    }
}

因为 weight变量在 Edge 中类，Node 不需要它, 所以你可以删除它:

class Node {
    public int number;
    // add more variables later is you need here
}

现在，对于您的程序(如果没有针对它的要求)，我会这样定义您的列表:

HashMap<Node, List<Edge>> adj; // use any list implementation you want

这将在您的程序中表示这样的图形(从您的示例中复制):

• 节点 0: 边(节点 0, 节点 1, 55), 边(节点 0, 节点 2, 54)
• 节点 1: 边(节点 1, 节点 0, 43), 边(节点 1, 节点 2, 44)

为了回答您的问题，让我们找出按边权重排序的边:

ArrayList<Edge> sortedEdges = new ArrayList<Edge>();
for (List<Edge> connectedEdges : adj.values()) {
    sortedEdges.addAll(connectedEdges);
}
Collections.sort(sortedEdges);

这只需要所有 Edge在adj并将它们全部放在一个列表中，然后根据它们的权重对它们进行排序(因为我们将 Edge 扩展为 Comparable<Edge> )。根据 Javadoc on Collections.sort() , sort()方法使用合并排序，它在 O(nlog(n)) 中运行时间:

Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered.

获取所有 Edge 的列表由 adj.values需要 O(n)时间(参见 this )，因此获取按权重排序的边列表的总时间复杂度将为 O(n) + O(nlog(n)) = <强> O(nlog(n)) .

就这样吧。我希望这对您有所帮助:)