Ricerca in profondità - Algoritmi su grafi

Impara l’ordinamento topologico: ordina un grafo diretto aciclico in modo che ogni arco punti in avanti. Calcola i gradi entranti, costruisci un ordinamento con l’algoritmo di Kahn nel linguaggio che preferisci, rileva i cicli e trova il cammino più lungo in un DAG.

Algoritmi sui grafi

Certificato al completamento

• 9
• 3
• 1
• 55

Padroneggia la ricerca in ampiezza (BFS), l’attraversamento dei grafi livello per livello alla base dei cammini minimi. Crea una mappa dei vicini, implementa una BFS iterativa con una coda nel linguaggio che preferisci e usala per trovare le distanze dei cammini minimi nei grafi non pesati.

Algoritmi sui grafi

Certificato al completamento

• 9
• 3
• 1
• 54

In questo corso imparerai a conoscere la struttura dati dei grafi, creerai da zero un grafo non orientato nel linguaggio che preferisci e ti eserciterai con sfide di programmazione!

Certificato al completamento

• 14
• 12

Padroneggia l'algoritmo di Dijkstra, un metodo greedy per trovare i cammini minimi da una singola sorgente nei grafi con pesi non negativi. Leggi gli archi pesati, implementa il calcolo completo delle distanze nel linguaggio che preferisci e rispondi a query sui percorsi tra due vertici e sul vertice più lontano.

Algoritmi sui grafi

Certificato al completamento

• 9
• 3
• 1
• 54

Padroneggia l'algoritmo di Kruskal per trovare alberi ricoprenti minimi. Implementa una struttura union-find, costruisci un albero ricoprente minimo aggiungendo l'arco più economico che non crea cicli, usando il linguaggio che preferisci, e rispondi a query sulla connettività e sugli archi collo di bottiglia.

Algoritmi sui grafi

Certificato al completamento

• 9
• 3
• 1
• 57