Cos'è grafi?

Grafi: Concetti Fondamentali

Un grafo è una struttura dati non lineare composta da un insieme di nodi (o vertici) e un insieme di archi (o spigoli) che collegano coppie di nodi. I grafi sono utilizzati per modellare relazioni tra oggetti.

Tipi di Grafi:

• Grafi Diretti (Digrafi): Gli archi hanno una direzione specifica, indicando una relazione unidirezionale tra i nodi. In questo caso, si parla di arco orientato.
• Grafi Indiretti: Gli archi non hanno una direzione specifica, indicando una relazione bidirezionale tra i nodi.
• Grafi Pesati: Ad ogni arco è associato un peso (o costo), che rappresenta, ad esempio, la distanza o il costo di spostamento tra due nodi.
• Grafi Non Pesati: Gli archi non hanno pesi associati.
• Grafi Connessi: Esiste un percorso tra ogni coppia di nodi nel grafo.
• Grafi Disconnessi: Esistono coppie di nodi nel grafo per le quali non esiste un percorso tra di loro.
• Grafi Ciclici: Contengono uno o più cicli (percorsi che iniziano e finiscono nello stesso nodo).
• Grafi Aciclici: Non contengono cicli. Un esempio importante è l' albero.
• Grafi Bipartiti: I nodi possono essere divisi in due insiemi disgiunti tali che ogni arco collega un nodo di un insieme a un nodo dell'altro insieme.

Rappresentazioni di Grafi:

• Matrice di Adiacenza: Una matrice quadrata in cui l'elemento (i, j) indica se esiste un arco tra il nodo i e il nodo j.
• Lista di Adiacenza: Un array di liste, dove ogni elemento dell'array rappresenta un nodo, e la lista corrispondente contiene i nodi adiacenti a quel nodo.

Algoritmi sui Grafi:

Esistono numerosi algoritmi per risolvere problemi sui grafi, tra cui:

• Ricerca in Ampiezza (BFS): Utilizzata per esplorare un grafo a partire da un nodo sorgente, visitando prima tutti i nodi adiacenti e poi i loro vicini, e così via.
• Ricerca in Profondità (DFS): Esplora un grafo visitando prima un ramo in profondità fino alla fine, per poi tornare indietro ed esplorare altri rami.
• Algoritmi di Cammino Minimo: Trovano il percorso più breve tra due nodi in un grafo pesato (es. Algoritmo di Dijkstra, Algoritmo di Bellman-Ford).
• Albero Ricoprente Minimo (MST): Trova un sottoinsieme degli archi di un grafo connesso, pesato e non diretto che collega tutti i nodi insieme, senza cicli e con il peso totale minimo. (es. Algoritmo di Kruskal, Algoritmo di Prim).
• Ordinamento Topologico: Ordina i nodi di un grafo diretto aciclico (DAG) in modo tale che per ogni arco diretto (u, v), il nodo u venga prima del nodo v nell'ordinamento.

Applicazioni dei Grafi:

I grafi sono ampiamente utilizzati in diversi campi, tra cui:

• Reti Sociali: Modellazione delle connessioni tra utenti.
• Reti di Trasporto: Rappresentazione di strade, ferrovie, rotte aeree.
• Informatica: Rappresentazione di algoritmi, circuiti elettronici, database.
• Biologia: Modellazione di interazioni tra proteine e geni.
• Chimica: Rappresentazione di molecole e reazioni chimiche.