Grafici e alberi con spanning minimo?

0

Ho difficoltà a trovare informazioni su come funzionano i grafici e lo spanning tree e su come costruirli / strutturarli. Il motivo è che sto usando un algoritmo Delaunay Triangulation all'interno di LibGDX framwork e questo mi ha dato una serie di indici. Posso disegnare i miei triangoli e punti, ma come configurare correttamente un grafico / struttura MST è un problema.

Fornisco i miei vertici come una serie di float:

float[] points = new float[6] {80, 30, 40, 45, 0, 10};

Ogni coppia si riferisce a un punto della mappa. Usando DelaunayTriangulator.computeTriangles ottengo una matrice di indici, in questo caso

ShortArray indices = triangulator.computeTriangles(points, false);
System.out.println(indices);
//Output [1, 0, 2, 1, 2, 3]

Ora posso disegnare tutti i bordi e sto facendo questo usando solo questi dati. Ma suppongo di creare una classe di nodi e grafici per aiutarmi qui, semplicemente non ho idea di come dovrebbe essere. Per esempio, dovrei avere multipli degli stessi punti con genitori diversi, o dovrei avere un singolo nodo per un punto con un elenco di punti a cui è collegato? Sono molto nuovo per i grafici e MST e ci sono molte informazioni sull'argomento, ma non riesco a trovare esempi pratici.

    
posta Madmenyo 13.06.2015 - 19:58
fonte

1 risposta

1

La tua idea di "nodo singolo per un punto con un elenco di punti a cui è collegato" dovrebbe funzionare, in quanto descrive un elenco di adiacenza. Due modi canonici per rappresentare i grafici sono tramite liste di adiacenza e matrici di adiacenza, per le quali le pagine di Wikipedia hanno alcuni semplici esempi:

link

link

Nel caso di un elenco di adiacenze, ha spesso senso usare una struttura di dati dizionario / mappatura, ad es. una HashMap in Java.

Un solo esempio per notare due ulteriori avvertimenti ... diciamo che il sotto rappresenta un grafico con quattro nodi e tre bordi:

(1) -- (2) -- (3)
        |
       (4)

Una lista di adiacenze potrebbe essere rappresentata in questo modo: {1: [2], 2: [1, 3, 4], 3: [2]}

Nota che:

  • Il grafico sopra non è pesato - se fosse pesato, i pesi del bordo dovrebbero essere rappresentati, ad es. come possibile implementazione che segue la lista di adiacenza precedente {1: [(2, 3)], 2: [(1, 5), (3, 2)...] ...} dove 1: (2, 3) significa che il confine tra il nodo 1 e il nodo 2 ha il peso di 3.
  • Il grafico sopraindicato non è diretto: se fosse diretto, l'elenco di adiacenza potrebbe potenzialmente contenere meno spigoli.

Gli MST sono sottoinsiemi di bordo di grafici, quindi di solito non è richiesta alcuna struttura aggiuntiva per rappresentarli.

    
risposta data 14.06.2015 - 09:42
fonte

Leggi altre domande sui tag