La ricerca di un Minimo Spanning Tree da un'Adiacenza Lista di Adiacenza Elenco è in una matrice di stringhe utilizzando Algoritmo di Prim

StackOverflow https://stackoverflow.com/questions/9449967

Domanda

Quindi ho bisogno di qualche aiuto, fino a venire con un modo per trovare un Minimo spanning tree.Supponiamo che io sono il mio grafico in forma di lista di adiacenza:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

La prima lettera indica che il nodo che si sta guardando, e il numero indica quante connessioni di qualsiasi altro nodo ci sono.Per esempio, Una ha due connessioni una per ogni a B e I.Dopo di che, il numero che segue le lettere basta dire il peso di un bordo.B ha un peso di 12 e l'ho peso 25.Quindi avevo in mente di rappresentare questa cosa come una matrice di stringhe chiamato Graph[8].Ogni linea dovrebbe essere uno slot diverso nella matrice.Sto avendo difficoltà a capire come realizzare questo con Prims o Kruskalls algoritmo.

È stato utile?

Soluzione

Supponiamo che io sono il mio albero in forma di lista di adiacenza

È importante (per la vostra comprensione) notare che hai collegato grafico in questo tipo di adiacenza lista, ma penso che sia stato solo un errore di battitura.Propongo questo come una modifica, ma voglio solo che tu sia a conoscenza di esso.Il fatto che si tratta di un grafico e non un albero può essere visto da queste linee:

A 2 B 12 I 25
B 3 C 10 H 40 I 8

Qui si ha un cerchio già a-B-I:

     A
  12/_\25
   B 8 I

Avendo un cerchio, per definizione, significa che non può essere un albero!C'è una cosa che si può vedere dal modo in cui ho presentato questo sottografi:i bordi hanno pesi, non i nodi.

Ora diamo un'occhiata a un esempio: 

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

Prima di tutto, possiamo vedere che questa lista di adiacenza è errato o già ottimizzato per le tue esigenze.Questo può per esempio essere visto dalle linee

E 2 F 60 G 38
F 0

La prima riga mostra un bordo da E a F, ma la seconda riga dice che F aveva un grado di 0, ma il grado è definito dai bordi incidente ad esso!

Questo è ciò che il adiacenza elenco sarebbe come se fosse "completo":

A 2 B 12 I 25
B 4 A 12 C 10 H 40 I 8
C 3 B 10 D 18 G 55
D 2 C 18 E 44
E 3 D 44 F 60 G 38
F 1 E 60
G 3 C 55 E 38 H 35
H 3 B 40 G 35 I 35

Siamo in grado di vedere un sacco di ridondanza, perché ogni bordo si verifica due volte, questo è il motivo per cui il vostro 'ottimizzato' adiacenza lista meglio si adatta alle vostre esigenze - sarebbe questo 'completa' esempio si potrebbe fare tanti inutili controlli.Tuttavia, si dovrebbe solo si basano su questo, se si può essere sicuri che tutti i dati forniti per il vostro codice è gia 'ottimizzati' (o meglio in questo formato)!Io prenderò questo come un dato di fatto ormai.

Parliamo di una struttura di dati.Ovviamente si può usare la tua proposta di array di stringhe, ma ad essere onesti, avrei preferito qualcosa di simile consiglia di @AmirAfghani proposta di struttura di dati.Utilizzando il suo approccio potrebbe rendere il vostro lavoro più facile (in quanto - come ha già sottolineato - sarebbe più vicino al tuo rappresentazione mentale e ancor di più efficiente (credo, non fare affidamento su questa ipotesi ;)) come si potrebbe fare molti operazioni sulle stringhe altrimenti.Nel titolo hai chiesto dopo l'algoritmo di Prim, ma nella tua domanda hai detto sia Prim o del test di Kruskal.Io andrò con il test di Kruskal semplicemente perché il suo algoritmo è il modo più facile e ti sembra di non accettare entrambi.

L'algoritmo di Kruskal

L'algoritmo di Kruskal è abbastanza semplice, si tratta fondamentalmente di:

  • Iniziare con ogni nodo, ma senza bordi

Ripetere la seguente, come spesso possibile:

  • Da tutte le inutilizzati/coabitazione non scelta bordi scegliere quello con il minor peso (se ci sono più di una:basta scegliere uno di loro)
  • Verificare se questo bordo possano causare un cerchio, se del caso, contrassegnare come scelta e 'scartare' di esso.
  • Se non provoca un cerchio, utilizzare e segnare come impiegato/scelto.

Questo è tutto.È davvero semplice.Tuttavia, vorrei ricordare una cosa a questo punto, penso che meglio si adatta qui:non c'è "il minimo spanning tree" in generale, ma "un minimo spanning tree", come ci possono essere molte, in modo che i risultati possono variare!

Torna a i dati della tua struttura!Si può ora vedere perché sarebbe una cattiva idea di utilizzare un array di stringhe come una struttura di dati.È necessario ripetere molte operazioni sulle stringhe (ad esempio controllando il peso di ogni bordo) e le stringhe sono immutabili, che significa non si può semplicemente 'buttare via' uno dei bordi o marchio di uno dei bordi in qualunque modo.Utilizzando un approccio diverso, si può solo impostare il peso a -1 o addirittura rimuovere la voce per il bordo!

Depth-First Search

Da quello che ho visto penso che il tuo problema principale è decidere se un bordo possano causare un cerchio o no, giusto?Per decidere questo, si avrà probabilmente bisogno di chiamare un Depth-First algoritmo di Ricerca e di utilizzare il suo valore di ritorno.L'idea di base è questa:iniziare da uno dei nodi (chiamerò questo nodo radice) e cercare di trovare un modo per il nodo all'altra estremità del bordo (chiamerò questo nodo il nodo di destinazione).(ovviamente nel grafico che non hanno questo margine di sicurezza)

  • Scegliere uno non visitati bordo incidente di root del vostro
  • Segno di questa scelta bordo visitato (o qualcosa di simile, quello che vuoi)
  • ripetere gli ultimi due passaggi per il nodo sull'altro lato della visitato bordo
  • ogni volta che ci sono stato i bordi, tornare indietro di un bordo
  • se si torna alla radice e non non visitati bordi incidente a rimanere, si è fatto.return false.
  • se in qualsiasi punto di visitare il vostro nodo di destinazione, si è fatto.restituisce true.

ora, se questo metodo restituisce true questo bordo possano causare un cerchio.

Altri suggerimenti

Questa non è una risposta diretta alla tua domanda per-dire (sembra che tu stia facendo il lavoro scolastico), ma penso che ti aiuterà a iniziare.Perché non creare una struttura dati che corrisponde più da vicino il tuo modello mentale e si accumula da lì? 

class GraphNode { 

    final String name;
    final List<GraphEdge> adjacentNodes;

    public GraphNode(String name) { 
        this.name = name;
        adjacentNodes = new ArrayList<GraphEdge>();
    }

    public void addAdjacency(GraphNode node, int weight) { 
        adjacentNodes.add(new GraphEdge(node, weight));
    }

}

class GraphEdge {

    final GraphNode node;
    final int weight;

    public GraphEdge(GraphEdge node, int weight) {
        this.node = node;
        this.weight = weight;
    }

}
.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top