java - Java 和 Bellman-Ford 中的加权有向图实现

Question

我试图找出在 Java 中实现加权有向图的最佳方法，以便我可以将 Bellman-Ford 上的运行时间保持在 |V|*|E|。基本上我的问题是如何表示图中的边缘。

我已经看到了邻接矩阵的使用，但我似乎无法弄清楚如何使用邻接矩阵同时保持运行时间低于 O(V^2)。我得到 V^2 作为运行时间的原因是因为 Bellman-Ford 要求我们遍历所有边，但它为了获取边列表，我需要遍历整个矩阵以获取所有边。无论如何，使用邻接矩阵可以获得比 O(V^2) 时间更快的边列表吗？

还是我需要使用邻接列表？

Answer 1

您可以轻松地为邻接列表实现一个类。以下是我经常用作邻接列表的类，它也很容易理解。它将 a 映射integer到 a linked list。

class Adjacencylist {

    private Map<Integer, List<Integer>> adjacencyList;

    public Adjacencylist(int v){    //Constructor
        adjacencyList = new HashMap<Integer,List<Integer>>();
        for(int i=0;i<v;++i){
            adjacencyList.put(i, new LinkedList<Integer>());
        }
    }

    public void setEdge(int a,int b){    //method to add an edge
        List<Integer> edges=adjacencyList.get(a);
        edges.add(b);
    }

    public List<Integer> getEdge(int a){
        return adjacencyList.get(a);
    }

    public boolean contain(int a,int b){
        return adjacencyList.get(a).contains(b);
    }

    public int numofEdges(int a){
        return adjacencyList.get(a).size();
    }

    public void removeEdge(int a,int b){
        adjacencyList.get(a).remove(b);
    }

    public void removeVertex(int a){
        adjacencyList.get(a).clear();
    }

    public void addVertex(int a){
        adjacencyList.put(a, new LinkedList<Integer>());
    }
}

在您抱怨我需要实现加权图之前，请考虑将 a 映射HashMap到 a Integer。您可以通过替换来相应地更改linked list功能hash map。这使您免于 O(n^2) 时间复杂度。

Answer 2

我的版本。在其中一个用例中，这对我来说效果很好。

public class DirectedWeightedGraph<E> {

// Map having Vertex as key and List of Edges as Value.
Map<Vertex<E>, List<Edge<E>>> adj = new HashMap<>();


public static class Vertex<E> {
    E value;

    public Vertex(E value) {
        this.value = value;
    }
}

public static class Edge<E> {
    E from;
    E to;
    double weight;

    public Edge(E from, E to, double weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

}

public void addVertex(E value) {
    Vertex<E> v = new Vertex<E>(value);
    List<Edge<E>> edges = new ArrayList<>();
    this.adj.put(v, edges);
}

public void addEdge(E from, E to, double weight) {
    List<Edge<E>> fromEdges =  this.getEdges(from);
    List<Edge<E>> toEdges =  this.getEdges(from);

    // Add source vertex and then add edge
    if(fromEdges == null) {
        this.addVertex(from);
    }
    if(toEdges == null) {
        this.addVertex(to);
    }

    fromEdges.add(new Edge<E>(from, to, weight));
}

}

Example:

DirectedWeightedGraph <Integer> graph = new DirectedWeightedGraph<>();
graph.addEdge(1, 2, 10.0);
graph.addEdge(2,3,15.0);