Domande aperte Algoritmi e strutture dati

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

QUESITO 24 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA SIMMETRICA (DETTA ANCHE VISITA IN-

ORDER) C D F G H L M S V ORDINE ALFABETICO

QUESITO 25 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA SIMMETRICA (DETTA ANCHE VISITA IN-

ORDER)

A B C D F G H U Z ORDINE ALFABETICO

QUESITO 26 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA SIMMETRICA (DETTA ANCHE VISITA IN-

ORDER) A E F I N O R S T Z ORDINE ALFABETICO

24

QUESITO 27 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA

DI NODI RISULTATO DI UNA VISITA SIMMETRICA (DETTA ANCHE VISITA IN-

ORDER) A B D E F M N S T ORDINE ALFABETICO

QUESITO 28 -DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA PER LIVELLI (DETTA ANCHE VISITA IN

AMPIEZZA) G E K B F M D R

QUESITO 29 -DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA PER LIVELLI (DETTA ANCHE VISITA IN

AMPIEZZA) F D S A E M T B N

25

QUESITO 30 -DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA PER LIVELLI (DETTA ANCHE VISITA IN

AMPIEZZA) H F M C G L V D S

QUESITO 31 -DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA PER LIVELLI (DETTA ANCHE VISITA IN

AMPIEZZA) H D U B F Z A C G

QUESITO 32 -DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA PER LIVELLI (DETTA ANCHE VISITA IN

AMPIEZZA) N E T A I R Z F O S 26

QUESITO 33 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA

DI NODI RISULTATO DI UNA VISITA SIMMETRICA (DETTA ANCHE VISITA IN-

ORDER) B D E F G K M R

QUESITO 34 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA

DI NODI RISULTATO DI UNA VISITA POSTICIPATA (DETTA ANCHE VISITA

POST-ORDER O POSTFISSA) POSTICIPATA VISITA:

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

RADICE

D C G F L S V M H

QUESITO 35 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA ANTICIPATA (DETTA ANCHE VISITA PRE-

ORDER O PREFISSA)

H F C D G M L V S ANTICIPATA VISITA:

RADICE

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

27

QUESITO 36 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA ANTICIPATA (DETTA ANCHE VISITA PRE-

ORDER O PREFISSA) H D B A C F G U Z ANTICIPATA VISITA:

RADICE

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

QUESITO 37 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA ANTICIPATA (DETTA ANCHE VISITA PRE-

ORDER O PREFISSA) F D A B E S M N T ANTICIPATAVISITA:

RADICE

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

QUESITO 38 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA POSTICIPATA (DETTA ANCHE VISITA POST-

ORDER O POSTFISSA)

D B F E R M K G POSTICIPATA VISITA:

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

RADICE

28

QUESITO 39 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA POSTICIPATA (DETTA ANCHE VISITA POST-

ORDER O POSTFISSA) B A E D N M T S F POSTICIPATA VISITA:

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

RADICE

QUESITO 40 - DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA POSTICIPATA (DETTA ANCHE VISITA POST-

ORDER O POSTFISSA)

A C B G F D Z U H POSTICIPATA VISITA:

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

RADICE

QUESITO 41- ILLUSTRARE LE DIFFERENZE QUALIFICANTI DI UNA

ESPLORAZIONE IN PROFONDITÀ E IN AMPIEZZA DI UN GRAFO

La ricerca in profondità (DFS) imita l’esplorazione di un labirinto di Tremaux. Si può pensare come

un modello in cui l’esploratore prosegue la sua marcia fino ad un vicolo cieco e quindi ritorna sui

suoi passi. La ricerca in ampiezza (BFS) invece procede in turni suddividendo i vertici in livelli. E’

come avere una squadra di esploratori che esplorano un livello o passo per volta e quando è tutto

esplorato passano al livello successivo.

QUESITO 42- DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI NODI

RISULTATO DI UNA VISITA POSTICIPATA (DETTA ANCHE VISITA POST-ORDER O

POSTFISSA) A F I E O S R Z T N POSTICIPATA VISITA:

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

RADICE

29

QUESITO 43 -DATO L’ALBERO BINARIO IN FIGURA, ELENCARE LA SEQUENZA DI

NODI RISULTATO DI UNA VISITA ANTICIPATA (DETTA ANCHE VISITA PRE-

ORDER O PREFISSA) G E B D F K M R ANTICIPATA VISITA:

RADICE

SOTTO ALBERO SINISTRO

SOTTO ALBERO DESTRO

LEZIONE 30- QUESITO 23 DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO,

IN FIGURA, ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST

DEL GRAFO DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL

NODO C CD -CF -AF -AB -EF

QUESITO 24 DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO, IN FIGURA,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO D

–EF

BD -AB -BC -DE

QUESITO 25 DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO, IN FIGURA,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO C

–CD

CE -BE -AB

30

QUESITO 26 DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO, IN FIGURA,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO C

–EF

BC -AB -BD -DE

QUESITO 27 DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO, IN FIGURA,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO D

CD -CE -BE -AB

QUESITO 28 DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO, IN FIGURA,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO B

–EF

AB -AF -CF -CD

QUESITO 29 DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO, IN FIGURA,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO F

–BC

EF -DE -BD -AB

QUESITO 30 – SI FACCIA UN ESEMPIO DI ALGORITMO SU GRAFO CHE UTILIZZA

LA STRATEGIA ALGORITMICA GOLOSA (GREEDY)

L’algoritmo Prim e l’algoritmo Kruskal sono entrambi esempi di algoritmi che utilizzano una

strategia Greedy. Entrambi questo algoritmi permettono di determinare un MST (Minimo albero

ricoprente) di un grafo che si assume connesso e i cui pesi degli archi siano positivi. Sono ancora in

grado di sfruttare bene le moderne strutture dati. 31

Sono, facili da capire e da implementare. L'algoritmo di Prim costruisce (accrescendo) un minimo

albero ricoprente a partire da un nodo arbitrario s (radice), includendo s in una "nuvola di vertici" che

cresce. Quindi, ad ogni iterazione, sceglie un arco di minimo peso e = (u, v) che collega un vertice u

già nella "nuvola" ad un vertice v, esterno alla nuvola. Il vertice v viene quindi incluso nella nuvola,

e il processo viene ripetuto fino a quando si forma un albero di copertura.

QUESITO 31 – QUANTI ARCHI CONTIENE UN MINIMO ALBERO RICOPRENTE DI

UN GRAFO CONNESSO?

Un minimo albero ricoprente di un grafo connesso G=(V,E) contiene n-1 archi dove n è il numero di

vertici appartenenti a V.

QUESITO 32- DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL

GRAFO DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL

NODO B BE -CE -AB -CD

QUESITO 33- DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO IN FIGURA ,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO E

–CD

EF -AF -AB -CF

QUESITO 34- DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO IN FIGURA ,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO E

EF -DE -BD -AB -BC

32

QUESITO 35- DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO IN FIGURA ,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO E

–CD

BE -CE -AB

QUESITO 36- DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO IN FIGURA,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO D

–EF

CD -CF -AF -AB

QUESITO 37- DATO IL GRAFO CONNESSO, PESATO E NON ORIENTATO IN FIGURA,

ELENCARE LA SEQUENZA ORDINATA DEGLI ARCHI APPARTENENTI ALL’MST DEL GRAFO

DATO, COME CALCOLATO DALL’ALGORITMO DI PRIM, PARTENDO DAL NODO B

–EF

AB -BD -BC -DE

QUESITO 38- ILLUSTRARE LE DIFFERENZE FRA ALGORITMO DI PRIM E

ALGORITMO DI KRUSKAL?

L’algoritmo Prim e l’algoritmo Kruskal sono entrambi esempi di algoritmi che utilizzano una

strategia Greedy. Entrambi questo algoritmi permettono di determinare un MST (Minimo albero

ricoprente) di un grafo che si assume connesso e i cui pesi degli archi siano positivi. Nell' algoritmo

di Prim: l'insieme A forma un singolo albero, l'arco sicuro che viene incluso in A è sempre l'arco di

minimo peso che collega un vertice già nell'albero A, con un vertice non ancora nell'albero A.

Nell'algoritmo di Kruskal: l'insieme A è una foresta. L'arco sicuro che viene aggiunto ad A è sempre

l'arco del grafo a minimo peso (l'algoritmo è greedy) che collega due componenti distinti.

L'algoritmo di Prim costruisce (accrescendo) un minimo albero ricoprente a partire da un nodo

arbitrario s (radice), includendo s in una "nuvola di vertici" che va via via crescendo. L'algoritmo di

Kruskal mantiene molti piccoli alberi in una foresta, e fonde di volta in volta coppie di alberi finché

un solo albero si estenderà sull'intero grafo originale (tale albero è proprio l'MST del grafo

originale). 33

QUESITO 39 – CHE PROBLEMA RISOLVE L’ALGORITMO DI KRUSKAL?

L’algoritmo di Kruskal è un algoritmo Greedy che permette di individuare un MST (Albero ricoprente

di peso minimo