Làm cách nào để đảo ngược biểu đồ trong thời gian tuyến tính?

Question

Tôi biết có hai cách để biểu diễn biểu đồ của tôi: một cách sử dụng ma trận và một cách khác là sử dụng danh sách.

Nếu tôi sử dụng ma trận, tôi phải lật tất cả các bit trong ma trận. Không phải mất thời gian O (V^2) sao?

Nếu tôi sử dụng danh sách, tôi sẽ không phải duyệt qua từng danh sách, từng cái một và tạo một bộ mới? Điều đó dường như có thời gian O (V + E) là tuyến tính. Tôi có đúng không?

Vì vậy, tôi có một câu hỏi khác tại đây. Hãy xem xét, ví dụ, tôi sử dụng thuật toán Dijkstra trên đồ thị của tôi (ma trận hoặc danh sách), và chúng tôi sử dụng hàng đợi ưu tiên cho cấu trúc dữ liệu đằng sau hiện trường. Có mối quan hệ nào về biểu diễn biểu đồ và việc sử dụng cấu trúc dữ liệu không? Nó có ảnh hưởng đến hiệu suất của thuật toán không?

Giả sử tôi sử dụng danh sách đại diện và hàng đợi ưu tiên cho thuật toán Dijkstra, liệu có sự khác biệt giữa ma trận và xếp hàng ưu tiên sử dụng cho Dijkstra không?

Tôi đoán nó chỉ liên quan đến hoạt động makeQueue? Hoặc họ không có khác nhau ở tất cả?

Answer 1

Đảo ngược danh sách kề của Đồ thị được chỉ định có thể được thực hiện trong thời gian tuyến tính. Chúng tôi chỉ duyệt qua biểu đồ một lần. Thứ tự phức tạp sẽ là O (| V | + | E |).

1. Duy trì HashMap của danh sách Adjaceny trong đó khóa là nhãn đỉnh và giá trị là một ArrayList của các đỉnh liền kề của đỉnh khóa.
2. Để đảo ngược, hãy tạo HashMap mới cùng loại. Quét bản đồ băm ban đầu và cho mỗi phím bạn đi qua, duyệt qua danh sách tương ứng.
3. Đối với mỗi đỉnh được tìm thấy trong danh sách giá trị, thêm khóa trong hashMap mới, đặt khóa của HashMap gốc làm mục nhập trong ArrayList tương ứng với khóa mới trong HashMap mới.

public static HashMap<Character,ArrayList <Character>> getReversedAdjLists(RGraph g) 
{ 
    HashMap <Character, ArrayList<Character>> revAdjListMap = new HashMap <Character, ArrayList<Character>>(); 
    Set <Character> oldLabelSet = g.adjListMap.keySet(); 

    for(char oldLabel:oldLabelSet) 
    { 
     ArrayList<Character> oldLabelList = g.adjListMap.get(oldLabel); 

     for (char newLabel : oldLabelList) 
     { 
      ArrayList<Character> newLabelList = revAdjListMap.get(newLabel); 

      if (newLabelList == null) 
      { 
       newLabelList = new ArrayList<Character>(); 
       newLabelList.add(oldLabel); 
      } 
      else if (! newLabelList.contains(oldLabel)) 
      { 
       newLabelList.add(oldLabel); 
      } 

      revAdjListMap.put(newLabel, newLabelList); 
     } 
    } 

    return revAdjListMap; 
} 

Answer 2

Tôi nghĩ việc đảo ngược biểu đồ bằng cách duyệt qua danh sách sẽ là O (V), vì mỗi đỉnh bạn phải thêm hoặc xóa cạnh (V-1). Đối với thuật toán Dijkstra, như tôi hiểu, nếu bạn đại diện cho đồ thị dưới dạng ma trận hoặc danh sách thuật toán lấy O (V), nhưng một số cấu trúc dữ liệu khác sẽ nhanh hơn. Nhanh nhất được biết đến là một đống Fibonacci, cung cấp cho O (E + VlogV).