Jak odwrócić wykres w czasie liniowym?

Wiem, że istnieją dwa sposoby reprezentowania mojego wykresu: jeden używa macierzy, a drugi używa listy.Jak odwrócić wykres w czasie liniowym?

Jeśli używam matrycy, muszę odwrócić wszystkie bity w macierzy. Czy to nie zajmuje czasu O (V^2)?

Jeśli użyję listy, czy nie będę musiał przechodzić przez każdą listę, jeden po drugim, i utworzyć nowy zestaw? Wydaje się, że zajmuje to czas O (V + E), który jest liniowy. Mam rację?

Mam tu kolejne pytanie. Rozważmy na przykład, że używam algorytmu Dijkstra na moim wykresie (albo macierzy lub listy), i używamy kolejki priorytetowej dla struktury danych za sceną. Czy istnieje jakaś relacja reprezentacji wykresu i wykorzystania struktury danych? Czy wpłynie to na działanie algorytmu?

Załóżmy, że mam użyć listy dla reprezentacji i kolejki priorytetowej dla algorytmu Dijkstra, czy istnieje różnica między macierzą a kolejką priorytetową dla Dijkstra?

Podejrzewam, że dotyczy tylko operacji makeQueue? Czy w ogóle nie mają innych?

Źródło

2013-04-23 Timothy Leung

przemierzania list przylegania nie zdarza się w czasie liniowej ogólnie jako E = V^O (2). – collapsar

@collapsar To * zawsze * dzieje się w czasie liniowym względem wierzchołków * i krawędzi *. Aby zdefiniować złożoność czasu tylko na części danych wejściowych (tj. Tylko wierzchołkach) (bez wyraźnego jej podawania) wydaje się nieco nielogiczne, * szczególnie * gdy czas jest bezpośrednio związany z inną częścią danych wejściowych (ale nie mogę twierdzić, że wiele ludzie mogą definiować to tak, jak ty). A E = O (V^2) jest dla gęstych wykresów. Rzadkie wykresy to E = O (V). – Dukeling

@dukeling masz rację wskazując, że zmniejszenie "rozmiaru" problemu do pojedynczego skalara wiąże się z brakiem precyzji. Otoh, notacja big-Oh opisuje najgorszy przypadek i, biorąc pod uwagę wykresy, bez dodatkowych ograniczeń najgorszy przypadek oznacza E = O (V^2). będąc dokładnym, O (V^2) nie jest poprawne dla odwrócenia krawędzi na macierzy sąsiedztwa - jeśli reprezentacja ma flagę rząd-major vs. col-dur, transpozycja to O (1). – collapsar

Odwracanie list przylegających do wykresu ukierunkowanego można wykonać w czasie liniowym. Przechodzimy przez wykres tylko raz. Kolejność złożoności będzie O (| V | + | E |).

Utrzymuj mapę HashMap z listami adjaceny, w której kluczem jest etykieta wierzchołków, a wartością jest ArrayList sąsiadujących wierzchołków wierzchołka klucza.
Aby odwrócić, utwórz nową mapę HashMap tego samego rodzaju. Zeskanuj oryginalną mapę skrótów i dla każdego napotkanego klucza przejdź przez odpowiednią listę.
Dla każdego wierzchołka znalezionego na liście wartości dodaj klucz w nowej tablicy skrótów, umieszczając klucz oryginalnego HashMap jako wpis w tablicy ArrayList odpowiadający nowemu kluczowi w nowej mapie HashMap.

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; 
}

Źródło

2013-07-06 02:46:52 Rama

Dobra odpowiedź. Początkowo próbowałem to zrobić za pomocą statycznej tablicy 2D, ale transpozycja tej macierzy (w celu odwrócenia) to O (n^2). Jestem prawie pewien. – scottyseus

Myślę, że cofnięcie wykresu poprzez przechodzenie przez listę zajmuje O (V), ponieważ dla każdego wierzchołka należy dodać lub usunąć krawędzie (V-1).

Jeśli chodzi o algorytm Dijkstry, jak rozumiem, jeśli reprezentujesz wykres jako macierz lub listę, algorytm zajmuje O (V), ale niektóre inne struktury danych są szybsze. Najszybciej znany jest stert Fibonacciego, który daje O (E + VlogV).

Źródło

2013-04-23 01:35:59 Beta

A może zostawię dwie listy? Lista przychodzących zboczy i list wypadających brzegów wydaje się dobrym pomysłem? –

@TymothyLeung: Dlaczego? Nie rozumiem, w jaki sposób dałoby to przewagę nad jedną listą wychodzących krawędzi. – Beta

@ Beta Wyobrażam sobie, że byłby to tylko O (V^2), gdy wykres jest gęsty. Rozważ brak krawędzi. Robiłbyś tylko O (1) przy każdym wierzchołku, a więc O (V). Tak więc krawędzie muszą wchodzić w grę w złożoności. – Dukeling

Jak odwrócić wykres w czasie liniowym?

Odpowiedz

Powiązane problemy