代码之家 › 专栏 › 技术社区 › Dubby

在Java中排序图的边(基于相邻列表表示法)

minimum-spanning-tree graph data-structures sorting java

Dubby · 技术社区 · 12 年前

我有一个使用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

我需要得到一个按重量排序的边列表,我不知道该怎么做。我正在尝试实现Kruskal的MST。

是否可以对我定义的图形进行排序?如果没有,请建议更好的存储方式。

2 回复 | 直到 12 年前

Community Mohan Dere 9 年前

让我们从创建 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 变量位于 边 类,它在 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),边(节点2,节点0,54)
节点1:边(节点1,节点0,43),边(节点2,节点1,44)

回答您的问题 ,用于查找按边权重排序的边:

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

这只需要 边 s在 adj 并将它们放在一个列表中,然后根据它们的重量对它们进行排序(因为我们 边 延伸 Comparable<Edge> ). 根据 Javadoc on Collections.sort() 这个 sort() 方法使用合并排序,该排序在 O(nlog(n)) 时间:

实现说明:此实现是一种稳定、自适应的迭代合并排序,当输入数组被部分排序时,需要的比较远远少于n个lg(n),而当输入数组随机排序时,则提供传统合并排序的性能。

获取所有列表 边 s由 adj.values 拿 O(n) 时间(参见 this ),因此获取按权重排序的边列表的总时间复杂性将为 O(n) + O(nlog(n)) = O(nlog(n)) .

好了。我希望这有助于:)

Jae Heon Lee 12 年前

如果您可以自由更改节点的表示方式,我建议您进行更改 Node 类实际上表示一条边(节点由 Integer ,即 adj 变量

例如,以下内容似乎更自然:

Set<Node> nodes = new HashSet<>(); // The enclosing class keeps track of all nodes.

// Represents each node.
class Node {
    int nodeId = /* ... */;

    // The Node class keeps track of its neighbors, sorted by their weights.
    SortedMap<Integer,Node> edges = new TreeMap<>(Collections.reverseOrder());
}

然后,每当您需要按重量降序进行操作时,您可以执行以下操作:

void method(Node node) {
    Iterator<Integer> iter = node.edges.keySet().iterator(); // Iterates in descending order.
    while(iter.hasNext()) {
        int weight = iter.next();
        Node neighbor = node.edges.get(weight);

        doSomething( /* ... */ );
    }
}