Jak można przedstawić i opisać połączenia i relacje między wierzchołkami w strukturze grafu?

Połączenia i relacje między wierzchołkami w strukturze grafu są zwykle opisywane za pomocą krawędzi. Główne sposoby reprezentacji grafu:

• Lista sąsiedztwa: dla każdego wierzchołka przechowywana jest lista sąsiednich wierzchołków, z którymi jest połączony. Jest to skuteczny sposób dla rzadkich grafów.

• Macierz sąsiedztwa: dwuwymiarowa tablica, gdzie element [i][j] wskazuje na obecność (i, ewentualnie wagę) krawędzi między wierzchołkami i i j. Przydatne dla gęstych grafów.

• Lista krawędzi: po prostu lista wszystkich krawędzi, gdzie każda krawędź zawiera informacje o wierzchołkach początkowych i końcowych (i wagę, jeśli jest).

Na przykład, w Java, graf można przedstawić tak:

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

    void addEdge(int from, int to) {
        adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        // Dla grafu nieskierowanego, dodaj odwrotną krawędź
        // adjacencyList.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
    }
}

W ten sposób, połączenia między wierzchołkami są modelowane za pomocą krawędzi, a struktura danych jest wybierana w zależności od zadania i cech grafu.