Esiste una struttura dati ad albero con più nodi radice?

Question

Esiste una struttura dati ad albero con più nodi radice?

#1 da (17 voti)
#2 da (2 voti)

3

Ho letto questo post Nome dei dati struttura simile a un albero con più nodi radice . Quello che sto chiedendo non è una foresta.

Vorrei darti un semplice esempio che descrive facilmente il mio caso.

Hai una normale fonte di energia da EB e un inverter (fonte di alimentazione alternativa) nella tua casa. Considera questi come nodi radice. E il livello successivo sono i misuratori di monitoraggio in ogni stanza. E al livello successivo hai le tue attrezzature come Fan, AC, Frigo ecc.

In questo albero il primo livello è l'elenco delle fonti di energia e il secondo-ennesimo livello avrà il flusso di energia fino alle apparecchiature di consumo.

Esiste una struttura dati adeguata per rappresentare questo albero che ha più nodi radice?

Modifica:

Immagine della struttura richiesta

data-structures trees

posta Vivek 26.09.2017 - 13:45

fonte

2 risposte

2

Ci sono strutture dati chiamate multitree o polytree, grafici aciclici indirizzati con più nodi radice.

Dal tuo esempio riguardante il flusso di energia, puoi controllare anche il teorema del taglio minimo del flusso massimo (teorema del flusso di s-t).

risposta data 26.09.2017 - 13:58

fonte

Leggi altre domande sui tag data-structures trees

Classi o spazi dei nomi annidati foreach su più elenchi contemporaneamente

score 17 · Accepted Answer

Stai cercando una specie di Grafico Aciclico Diretto (DAG). Questi grafici non hanno un nodo radice. Tuttavia, i nodi hanno un ordine parziale . Cioè quando guardiamo due nodi possiamo a volte dire quale nodo è "più alto". Nel tuo esempio, potremmo dire che le fonti di energia sono più alte dei metri che sono più alte dei consumatori.

Gli alberi sono un tipo speciale di DAG in cui ogni nodo ha esattamente un nodo genitore (eccetto per la radice che non ha genitori).

Un Multitree è un DAG in cui esiste un solo percorso non ambiguo tra due nodi. Cioè tutti i nodi raggiungibili da qualsiasi nodo (radice) formano un albero.