Grafik tuzilmasida tugunlar o'rtasidagi bog'lanishlar va o'zaro bog'liqliklarni qanday tasvirlash va ta'riflash mumkin?

Grafik strukturasida tugunlar o'rtasidagi bog'lanishlar va aloqalar odatda qirralar yordamida tavsiflanadi. Grafni ifodalashning asosiy usullari:

• Qo'shni ro'yxat: har bir tugun uchun, unga bog'langan qo'shni tugunlar ro'yxati saqlanadi. Bu kamyob grafiklar uchun samarali usul.

• Qo'shni matrisi: [i][j] element, i va j tugunlari orasida qirra mavjudligini (va ehtimol, og'irligini) ko'rsatadigan ikki o'lchovli massiv. To'liq grafiklar uchun qulay.

• Qirra ro'yxati: barcha qirralarning oddiy ro'yxati, har bir qirra boshlang'ich va oxirgi tugunlar (va og'irlik, agar bo'lsa) haqida ma'lumotlarni o'z ichiga oladi.

Masalan, Java'da grafik quyidagicha tasvirlanishi mumkin:

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

    void addEdge(int from, int to) {
        adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        // Yo'nalmagan grafik uchun, teskari qirra qo'shish
        // adjacencyList.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
    }
}

Shu tarzda, tugunlar o'rtasidagi bog'lanishlar qirralar yordamida modellashadi, va ma'lumotlar tuzilmasi vazifa va grafikning xususiyatlariga qarab tanlanadi.