在Java和Bellman-Ford中加權定向圖的實現

Question

我想找出在Java中實現加權定向圖的最佳方法，這樣我就可以將Bellman-Ford上的運行時間保持爲| V | * | E | 。基本上我的問題是如何表示圖中的邊。

我已經看到使用鄰接矩陣，但我似乎無法弄清楚如何使用鄰接矩陣，同時保持運行時間低於O（V^2）。我得到V^2作爲運行時間的原因是因爲Bellman-Ford要求我們循環遍歷所有邊，但爲了得到我需要遍歷整個矩陣以獲得所有邊的邊的列表。無論如何，通過使用鄰接矩陣來獲得比O（V^2）更快的邊界列表？

或者我需要使用鄰接列表嗎？

Answer 1

您可以輕鬆實現鄰接列表的類。以下是我常常用作鄰接列表的類，它也容易理解。它將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）的時間複雜度。