Cum se pot reprezenta și descrie conexiunile și relațiile dintre vârfuri într-o structură de graf?

Legăturile și relațiile dintre vârfuri într-o structură de graf sunt de obicei descrise cu ajutorul muchiilor. Principalele moduri de reprezentare a unui graf:

• Listă de adiacență: pentru fiecare vârf, se păstrează o listă a vârfurilor vecine cu care este conectat. Este o metodă eficientă pentru grafuri rare.

• Matrice de adiacență: un array bidimensional în care elementul [i][j] indică existența (și, posibil, greutatea) unei muchii între vârfurile i și j. Este util pentru grafuri dense.

• Listă de muchii: pur și simplu o listă a tuturor muchiilor, unde fiecare muchie conține informații despre vârfurile de început și de sfârșit (și greutatea, dacă există).

De exemplu, în Java, un graf poate fi reprezentat astfel:

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

    void addEdge(int from, int to) {
        adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        // Pentru un graf neorientat, adăugați muchia inversă
        // adjacencyList.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
    }
}

Astfel, legăturile între vârfuri sunt modelate prin muchii, iar structura de date este aleasă în funcție de sarcină și de caracteristicile grafului.