Java & Bellman-Ford의 가중치 적용 그래프 구현

Question

벨 매먼 포드에서 실행 시간을 | V | * | E |로 유지할 수 있도록 가중치 적용 그래프를 Java로 구현하는 가장 좋은 방법을 찾으려고합니다. . 본질적으로 내 질문은 그래프의 가장자리를 나타내는 방법에 관한 것입니다.

인접 행렬의 사용을 보았습니다. 그러나 동시에 실행 시간을 O (V^2) 미만으로 유지하면서 인접 행렬을 사용하는 방법을 알아낼 수 없습니다. Bellman-Ford가 모든 가장자리를 통해 반복해야하기 때문에 V^2를 실행하는 이유는 모든 가장자리를 얻기 위해 전체 매트릭스를 반복해야하는 가장자리의 목록을 얻기 위해서입니다. 인접 행렬을 사용하여 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>()); 
    } 
} 

당신은 내가, 가중 그래프를 구현 Integer에 HashMap 매핑에 대해 생각해야한다는 것을 불평하기 전에. 따라서 linked list을 hash map으로 바꾸면 기능을 변경할 수 있습니다. 이렇게하면 O (n^2) 시간의 복잡성에서 벗어날 수 있습니다.