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

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

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

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

來源

2016-12-27 Peter Siqueiros

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

來源

2016-12-27 20:01:07

謝謝你的回答！有了你的代碼，我確實看到它可以用鄰接列表，但是你知道鄰接列表是否可行嗎？ –

如果您的意思是2D矩陣，它們也可以很好地服務於相鄰數組，您可以將當前邊設置爲權重並將其設置爲默認值。在那一箇中獲得體重會更容易。當你有稀疏圖，當你不能有N^2數組時，這將會非常有用。（N意味着頂點的數量） –

是的，我想使用鄰接數組的原因是因爲您可以比列表更快地訪問權重，但是我遇到的問題是與Bellman-Ford以及使用鄰接陣列。如果我使用鄰接數組（二維數組是N×N），那麼我認爲無論如何得到小於O（N^2）時間的邊的列表是正確的嗎？ Bellman-Ford要求遍歷所有邊N次，但如果首先需要O（N^2）次來查找所有邊，那麼Bellman-Ford不再是O（M * N），其中M是數邊，N是頂點數。 –

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

回答

相關問題