Gestore pacchetti: approfondisci prima la ricerca o allarga la prima ricerca?

Question

Gestore pacchetti: approfondisci prima la ricerca o allarga la prima ricerca?

#1 da (4 voti)
#2 da (1 voti)

1

Sto appena iniziando a capire la struttura dei dati del grafico e l'ampiezza degli algoritmi di prima ricerca e profondità. Per un gestore di pacchetti come npm , in cui un pacchetto potrebbe avere dipendenze e quelle dipendenze potrebbero avere più dipendenze, se si volesse verificare se si disponessero già di quelle dipendenze, si tratta di una ricerca in profondità?

Esempio:

Voglio installare il pacchetto Top
Top ha due dipendenze, Middle1 e Middle2
Middle1 ha una dipendenza, Bottom1 e Middle2 ha una dipendenza, Bottom2

Ora prima di installare Top, voglio controllare se ho Middle1, Bottom1, Middle2, Bottom2. È una ricerca approfondita?

algorithms package-managers

posta Crystal 02.10.2017 - 07:13

fonte

2 risposte

4

Non importa. BFS vs DFS cambia solo l'ordine dei nodi visitati (è per questo che si chiama "depth / bread first ", dopotutto), non cambia il set dei nodi. (A meno che il tuo albero non sia infinito, ovviamente.)

Dato che devi comunque conoscere l'intero set di dipendenze per controllarle, non importa in che direzione vai.

risposta data 02.10.2017 - 08:39

fonte

Leggi altre domande sui tag algorithms package-managers

Come generare più "mostri" da una singola classe [chiuso] Double Dispatch è un pattern anti?

score 1 · Accepted Answer

In una ricerca / iterazione in larghezza di un albero, prima visita tutti i nodi sul "livello" corrente nell'albero prima di passare al livello successivo. Visitare i pacchetti nell'ordine Top, Middle1, Middle2, Bottom1, Bottom2 sarebbe una iterazione di ampiezza dell'albero delle dipendenze.

In una ricerca / iterazione in profondità, seguirai un link di dipendenza non appena ne incontri uno. Ciò comporterebbe la visualizzazione dei pacchetti nell'albero delle dipendenze nell'ordine Top, Middle1, Bottom1, Middle2, Bottom2.

Per camminare su un albero delle dipendenze e installare le dipendenze mancanti, nessuno dei due metodi per percorrere l'albero è intrinsecamente migliore, poiché è comunque necessario visitare tutti i nodi.