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

Question

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

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

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

Answer 1

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

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) 的时间复杂度。