Mappe concettuali di Algoritmi e strutture dati

GRAFO

INSIEME DI ELEMENTI DETTI NODI o VERTICI CHE POSSONO ESSERE COLLEGATI TRA LORO DA ARCHI

LESSICO

• ALBERO: (N-1), N è IL NUMERO VERTICI
• GRADO DI UN VERTICE: NUMERO ARCHI INCIDENTI NEL VERTICE
• CAMMINO: SEQUENZA DI VERTICI
• LUNGHEZZA CAMMINO: NUMERO DI ARCHI CHE LO COMPONGONO
• CAMMINO SEMPLICE: VERTICI DIVERSI
• CICLO: CAMMINO CHE PARTE E FINISCE NELLO STESSO VERTICE
• GRADO USCENTE: NUMERO ARC DEST. IN VERTICE CONS.
• GRADO ENTRANTE: NUMERO ARC DEST. OUT A VERTICE CONS.
• FORMALE: CONTENUTO: [VEREXTEXT]

ALBERO?

ALBERO /> GRAFO

OUTPUT DI BFS / DFS

PERCHÉ AMPIEZZA?

TI SERVE DI SCORRERE UN 'ALBERO CHE NON HA GLI ELEMENTI DEST\\\DATA\\ES. I PIÙ 'LONTANI SONO INNANZITRACCIARE" TI SCAPPO LEGGI E STRONI LORO.

DFS

VISITA IN PROFONDITÀ

RAPPRESENTAZIONE DI UN GRAFO

• LISTE DI ADIACENZA

ORDINAMENTO TOPOLOGICO

TEOREMA DEGLI ORDINAMENTI

TOPOLOGICAL - SORT

ALGORITMO

Cosa è

Insieme di elementi detti nodi e vertici che possono essere collegati tra loro da archi.

G = (V,E)

L'essico

• Arco: intervallo (-1,1), a --> b = arco uscente, entrante nel vertice.
• Grado di un vertice: quantità di archi che hanno incidenza nel vertice.
• Cammino: successione ordinata di vertici.
• Lunghezza cammino: numero di archi nel cammino.
• Ciclo: cammino che parte da un nodo e termina allo stesso nodo.
• Grado uscente: numero di archi uscenti, contatore incrementato quando si parte, decrementato quando si ritorna.
• Grado entrante: numero di archi entranti, contatore decrementato quando arco entra.
• Grado completo: somma di entrante e uscente, vale in orientato che non orientato.

Albero?

? Albero = Grafo

Output di BFS / DFS

Rappresentazione di un Grafo

• Liste di adiacenza
• Matrici di adiacenza

O(n+2 * e)

Lista di adiacenza

V = 4 * V, E = O(n+e)

DFS

Depth First SearchVisita in profondità

Funzionamento

1. DFS analizza un nodo predecessore.
2. Al passo corrente, visita (go to deep).
3. Inserisce in una pila e visita (un nodo a caso).
4. Si prende una pila (struttura LIFO).
5. Resta nel branch, visita i nodi non marcati.
6. Ogni branca termina nel branch superiore o un'uscita (esamina).

O(n+e)

Algoritmo

In soggetto una FM. Rettore un arco back (di un nodo a se stesso o dei padri). Ogni arco del nodo sarà nel setting albero, avanti.

Obiettivo

Visita una sola volta detta origine, tutti i nodi raggiungibili.

• Difficoltà
• Passare ad oggi.

Perché ampiezza?

Per essere sicuro di trovare che c’erano dei nodi in quel punto era no buona, scorciatoia questi che si trovano lontani.

DFS con analisi

Sia un a prenassi e una. Si genera ordinamento topologico, se non parte da li, in un ciclo. Così è assente. Tempi per diagramma bianco. Nodo a quota a. Cerca in nodo precedente se fa una lunga abitudine.

DFS Classificazione degli archi

Arco (simbolo, freccia, orientamento) - tipo 0 (inizio) - tipo 1 (fine)

Ordinamento Topologico

• Cosa è?
• I nodi in ordine topologico
• Adatti a DFS, G aciclico.
• Si presenta una sequenza lineare, in cui ogni nodo si calcola come se ci fosse un call. (se aciclico)
• Problema tramite tutte unità ( uscita).

(Data per esecuzioni)

Tecnica delle opzioni B

Massimo n. archi cammino DFS. Rispetta ordinamento.

Tempo

Θ(n)

ALBERI DI CONNESSIONE MINIMI (MST)

COSA SIGNIFICA

• significa trovare un albero che connette tutti i vertici del grafo
• nessun albero deve essere il ciclo → dato che esisterebbe già una strada alternativa, dunque non può già di costruzione pesare di vari

MINIMUM SPANNING TREE

• ogni grafo modellabile un → nella miglior grafica MST
• ogni arco di come un MST
• nessun arco con peso maggiore → se il grafo non chinarà sofficho

PROPRIETÀ

• a ha |V|-1 archi
• non non c'è ciclo in un albero
• puoi non carica uno e non esiste parugli trovare oggi può trovarti una colonna per ogni MST

ALGORITMO GENERICO

IDEA

• costruire la soluzione partendo da un → inizialmente considerato il CICLO valore di tutti gli archi 0
• val