Language:
🇬🇧 English Version | 🇮🇹 Versione Italiana
During Harvard’s CS50 Introduction to AI with Python, I implemented a BFS solution to the classic Six Degrees of Separation problem. While analyzing the runtime behavior, I identified an inefficiency: the target node was always added to the frontier before being processed, causing an unnecessary extra iteration. This led me to implement a simple but impactful optimization.
The optimization introduces an early exit check that detects the target before adding it to the frontier, reducing the number of explored nodes and improving execution time while fully preserving BFS correctness and shortest-path guarantees.
This repository includes:
- A clear comparison between the standard BFS and the optimized BFS
- Optional DFS implementation for completeness
- A Jupyter notebook with benchmarks, analysis, and visualizations
- A clean, production-quality codebase reflecting professional engineering practices
| Metric | BFS Standard | BFS Optimized |
|---|---|---|
| Avg. Execution Time | 4582.94ms | 7.52ms |
| Nodes Explored | 631 | 11 |
| Path Length | Identical | Identical |
Performance Improvement: ~99.8%
The early-exit optimization checks whether a neighboring node is the target before adding it to the frontier:
if person_id == target:
return construct_path(child)
frontier.add(child)This small modification eliminates an extra cycle of the main BFS loop and avoids redundant operations, especially impactful in dense graphs.
degrees/
├── degrees_comparison.ipynb # Full benchmark and analysis notebook
├── degrees.py # Standard BFS implementation
├── degrees_optimized.py # Optimized BFS
├── util.py # Core data structures
├── large/ # IMDb dataset
│ ├── people.csv
│ ├── movies.csv
│ └── stars.csv
└── requirements.txt
git clone https://github.com/yourusername/degrees.git
cd degrees
pip install -r requirements.txt
jupyter notebook degrees_comparison.ipynbOpen the notebook directly in your browser:
Durante il corso CS50 Introduction to AI with Python di Harvard, ho implementato una soluzione BFS al classico problema dei Six Degrees of Separation. Analizzando il comportamento in esecuzione, ho identificato un'inefficienza: il nodo target veniva sempre aggiunto alla frontier prima di essere processato, causando un'iterazione extra non necessaria. Questo mi ha portato a implementare un'ottimizzazione semplice ma di impatto.
L'ottimizzazione introduce un early exit check che rileva il target prima di aggiungerlo al frontier, riducendo il numero di nodi esplorati e migliorando il tempo di esecuzione pur preservando completamente la correttezza della BFS e le garanzie del percorso più breve.
Questa repository include:
- Un confronto tra la BFS standard e la BFS ottimizzata
- Implementazione DFS opzionale per completezza
- Un notebook Jupyter con benchmark, analisi e visualizzazioni
- Una codebase pulita e di qualità professionale che riflette pratiche ingegneristiche professionali
| Metrica | BFS Standard | BFS Ottimizzato |
|---|---|---|
| Tempo Medio Esec. | 4582.94ms | 7.52ms |
| Nodi Esplorati | 631 | 11 |
| Lunghezza Percorso | Identica | Identica |
Miglioramento delle Prestazioni: ~99.8%
L'ottimizzazione early exit check verifica se un nodo vicino è il target prima di aggiungerlo al frontier:
if person_id == target:
return construct_path(child)
frontier.add(child)Questa piccola modifica elimina un ciclo extra del loop principale BFS ed evita operazioni ridondanti, con un impatto particolare nei grafi densi.
degrees/
├── degrees_comparison.ipynb # Notebook completo di benchmark e analisi
├── degrees.py # Implementazione BFS standard
├── degrees_optimized.py # BFS Ottimizzata
├── util.py # Strutture dati fondamentali
├── large/ # Dataset IMDb
│ ├── people.csv
│ ├── movies.csv
│ └── stars.csv
└── requirements.txt
git clone https://github.com/yourusername/degrees.git
cd degrees
pip install -r requirements.txt
jupyter notebook degrees_comparison.ipynbApri il notebook direttamente nel tuo browser:
Antonio Tamburello — Senior Lead Frontend Engineer LinkedIn: https://www.linkedin.com/in/antonio-tamburello/