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

Question

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

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

或者我需要使用邻接表吗？

Answer 1

您可以轻松实现邻接表的 class。以下是 class ，我经常将其用作邻接列表，这也很容易理解。它将 integer 映射到 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>());
    }
}

在你抱怨我需要实现加权图之前，请考虑将 HashMap 映射到 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);

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

Weighted Directed Graph Implementation in Java & Bellman-Ford

java

algorithm

graph

time-complexity

bellman-ford