Come invertire un grafico in tempo lineare?

So che ci sono due modi per rappresentare il mio grafico: uno sta usando una matrice e l'altro sta usando una lista.Come invertire un grafico in tempo lineare?

Se utilizzo una matrice, devo capovolgere tutti i bit nella matrice. Non richiede O (V^2)?

Se utilizzo una lista, non dovrei attraversare ogni lista, uno per uno, e creare un nuovo set? Sembrerebbe prendere O (V + E) tempo che è lineare. Ho ragione?

Quindi, ho un'altra domanda qui. Si consideri, ad esempio, che io uso l'algoritmo Dijkstra sul mio grafico (una matrice o una lista), e usiamo una coda di priorità per la struttura dati dietro la scena. C'è qualche relazione tra rappresentazione grafica e uso della struttura dati? Influirà sulle prestazioni dell'algoritmo?

Supponiamo che dovessi usare un elenco per le rappresentazioni e una coda di priorità per l'algoritmo Dijkstra, ci sarebbe una differenza tra la matrice e usare la coda di priorità per Dijkstra?

Immagino che riguardi solo l'operazione makeQueue? O non hanno affatto diverso?

fonte

2013-04-23 Timothy Leung

Traversal di liste di adiacenza non avviene in tempo lineare in generale come E = O (V^2). – collapsar

@collapsar Si * sempre * avviene in tempo lineare in relazione ai vertici * e ai bordi *. Definire la complessità del tempo solo su una parte dell'ingresso (cioè solo i vertici) (senza specificarlo esplicitamente) sembra in qualche modo illogico, * specialmente * quando il tempo è direttamente correlato a un'altra parte dell'input (ma non posso sostenere che molti le persone possono definirlo come hai fatto tu). E E = O (V^2) è per grafici densi. I grafici sparsi sono E = O (V). – Dukeling

@dukeling hai ragione nel sottolineare che ridurre la 'dimensione' di un problema a un singolo scalare comporta una mancanza di precisione. otoh, big-Oh notation descrive il caso peggiore e, considerando i grafici, senza vincoli addizionali, il caso peggiore è E = O (V^2). essendo preciso, O (V^2) non è corretto per l'inversione del fronte su una matrice di adiacenza o - se la rappresentazione mette in mostra una riga di flag-major vs. col-major, la trasposizione è O (1). – collapsar

L'inversione degli elenchi di adiacenze di un grafico di direzione può essere eseguita in tempo lineare. Attraversiamo il grafico solo una volta. L'ordine di complessità sarà O (| V | + | E |).

Mantenere una HashMap di Elenchi di Adjaceny in cui la chiave è l'etichetta di vertice e il valore è una Lista di Array di vertici adiacenti del vertice chiave.
Per l'inversione, creare una nuova HashMap dello stesso tipo. Analizza la mappa hash originale e per ogni chiave che incontri, attraversa la lista corrispondente.
Per ogni vertice trovato nella lista valori, aggiungere una chiave nella nuova hashMap, inserendo la chiave della HashMap originale come una voce nella ArrayList corrispondente alla nuova chiave nella nuova 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; 
}

fonte

2013-07-06 02:46:52 Rama

Buona risposta. Inizialmente cercavo di farlo con un array 2D statico, ma la trasposizione di quella matrice (per realizzare l'inversione) è O (n^2) ne sono abbastanza sicuro. – scottyseus

Penso che invertire il grafico attraversando la lista ci vuole O (V), poiché per ogni vertice è necessario aggiungere o eliminare (V-1) i bordi.

Per quanto riguarda l'algoritmo di Dijkstra, se ho capito bene, se voi rappresentate il grafico come una matrice o l'elenco L'algoritmo prende O (V), ma alcune altre strutture di dati sono più veloci. Il più veloce conosciuto è un heap di Fibonacci, che dà O (E + VlogV).

fonte

2013-04-23 01:35:59 Beta

Che ne dici se tengo due liste? L'elenco dei bordi in entrata e l'elenco dei bordi in uscita, questa sembra essere una buona idea? –

@TimothyLeung: Perché? Non vedo come ciò darebbe alcun vantaggio su una lista di bordi in uscita. – Beta

@Beta Immagino che sarebbe solo O (V^2) quando il grafico è denso. Non considerare i bordi. Dovresti fare solo O (1) su ogni vertice, quindi O (V). Quindi i bordi devono entrare in gioco nella complessità. – Dukeling

Come invertire un grafico in tempo lineare?

risposta

Problemi correlati