¿Cómo se pueden representar y describir las conexiones y relaciones entre los vértices en una estructura de grafo?

Las conexiones y relaciones entre vértices en una estructura de grafo generalmente se describen mediante aristas. Las principales formas de representar un grafo:

• Lista de adyacencia: para cada vértice se guarda una lista de vértices vecinos con los que está conectado. Es un método eficiente para grafos dispersos.

• Matriz de adyacencia: una matriz bidimensional donde el elemento [i][j] indica la existencia (y posiblemente el peso) de una arista entre los vértices i y j. Es útil para grafos densos.

• Lista de aristas: simplemente una lista de todas las aristas, donde cada arista contiene información sobre los vértices inicial y final (y peso, si lo hay).

Por ejemplo, en Java, un grafo puede representarse así:

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

    void addEdge(int from, int to) {
        adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        // Para un grafo no dirigido, agregar la arista inversa
        // adjacencyList.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
    }
}

De esta manera, las conexiones entre vértices se modelan mediante aristas, y la estructura de datos se elige según la tarea y las características del grafo.