Cos'è un grafo orientato e quali sono le sue caratteristiche principali?

Un grafo orientato (o digrafo) è una struttura dati composta da un insieme di vertici (nodi) e un insieme di archi orientati che collegano questi vertici. Ogni arco ha una direzione che indica quale vertice è quello iniziale e quale quello finale.

Caratteristiche principali:

• Vertici (Nodes / Vertici): Elementi del grafo rappresentati da punti. Possono rappresentare oggetti, stati o fasi.
• Archi (Edges / Arcs): Connessioni tra vertici. In un grafo orientato, l’arco ha una direzione che indica il passaggio da un vertice all’altro. Sono rappresentati come una coppia ordinata (u, v), dove u è il vertice iniziale e v quello finale.
• Orientamento: Caratteristica chiave che distingue un grafo orientato da uno non orientato. Il movimento è possibile solo lungo la direzione dell’arco. Un arco da A a B non implica che si possa muoversi da B a A, a meno che non esista un arco separato da B a A.
• Cicli (Loops): Archi che collegano un vertice a se stesso (v, v).
• Archi multipli (Multiple Edges): Più archi che collegano la stessa coppia di vertici nella stessa direzione. Nei grafi orientati semplici, gli archi multipli non sono ammessi.
• Vertici isolati: Vertici senza archi entranti o uscenti.
• Grado del vertice:
  • Grado in (In-degree): Numero di archi entranti in un vertice.
  • Grado out (Out-degree): Numero di archi uscenti da un vertice.

Applicazioni in QA:

• Grafi di stati per testare automi finiti.
• Grafi di flusso di controllo per analisi del codice e creazione di casi di test.
• Modellazione delle dipendenze nei sistemi (ad esempio, dipendenze tra servizi o moduli).
• Test di scenari d’uso con sequenze di azioni rigorose.