Come si possono rappresentare e descrivere le connessioni e le relazioni tra i vertici in una struttura a grafo?

Le connessioni e le relazioni tra i vertici in una struttura di grafo sono generalmente descritte tramite archi. I principali modi di rappresentare un grafo:

• Lista di adiacenza: per ogni vertice si conserva una lista dei vertici vicini con cui è collegato. È un metodo efficiente per grafi sparsi.

• Matrice di adiacenza: un array bidimensionale in cui l'elemento [i][j] indica la presenza (e possibilmente il peso) di un arco tra i vertici i e j. Utile per grafi densi.

• Lista di archi: semplicemente una lista di tutti gli archi, dove ogni arco contiene informazioni sui vertici iniziali e finali (e peso, se presente).

Ad esempio, in Java, un grafo può essere rappresentato così:

class Graph {
    private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

    void addEdge(int from, int to) {
        adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        // Per un grafo non orientato, aggiungere l'arco inverso
        // adjacencyList.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
    }
}

In questo modo, le connessioni tra vertici sono modellate tramite archi, e la struttura dati viene scelta in base al compito e alle caratteristiche del grafo.