在 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和边权重为44的节点2

我需要按重量排序的边缘列表，我不知道如何去做。我正在尝试实施 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);

这只是将所有的Edgesadj放入一个列表中，然后根据它们的权重对它们进行排序（因为我们制作了Edgeextend Comparable<Edge>）。根据Javadoc onCollections.sort()，该sort()方法使用合并排序，它O(nlog(n))及时运行：

实现说明：此实现是一种稳定的、自适应的、迭代的归并排序，当输入数组部分排序时，它需要的比较次数远少于 n lg(n) 次，同时在输入数组随机排序时提供传统归并排序的性能。

获取所有Edges的列表adj.values需要O(n)时间（请参阅此），因此获取按权重排序的边列表的总时间复杂度为O(n) + O(nlog(n))=O(nlog(n))。

所以你去。我希望这有帮助:)