post test strukdat kelompok 9

Apa fungsi insert_edge(u, v, x=None) dalam metode ADT Graf?

• Membuat dan mengembalikan sisi baru dari simpul u ke v dan menyimpan elemen x

• Membuat dan mengembalikan simpul baru yang menyimpan elemen x.

• Menghapus simpul v dan semua sisi yang terhubung dengannya.

• Mengembalikan jumlah sisi pada graf.

Compressed trie untuk koleksi S string dengan alfabet ukuran d memiliki properti berikut, kecuali :

• Setiap simpul internal T memiliki setidaknya dua anak dan paling banyak d anak.

• T tidak memiliki s simpul daun.

• Jumlah simpul T adalah O(s).

• T memiliki s simpul daun

Dalam implementasi kelas graph, apa peran dictionary _outgoing?

• Menyimpan semua sisi dalam graf

• Menyimpan semua simpul dan daftar sisi yang terhubung ke masing-masing simpul

• Menyimpan semua jalur yang ditemukan dalam graf

• Menyimpan simpul awal dan tujuan dari semua sisi

Pada traversal BFS, apa yang terjadi ketika suatu simpul baru ditemukan?

• Simpul tersebut dihapus dari graf.

• Simpul tersebut ditambahkan ke tumpukan.

• Simpul tersebut ditambahkan ke antrian dan diberi tanda telah dikunjungi.

• Simpul tersebut langsung dihubungkan ke simpul awal.

Apa kelebihan utama Adjacency Map Structure dibandingkan Adjacency List Structure?

• Lebih hemat ruang untuk graf padat.

• Mendukung akses cepat ke sisi tertentu dengan peta berbasis hash.

• Mengurangi kompleksitas waktu menjadi O(n^2).

• Tidak membutuhkan penyimpanan sisi yang eksplisit.

Apa kekurangan utama dari Adjacency Matrix Structure dibandingkan metode lain?

• Tidak dapat digunakan untuk graf tak berarah.

• Memiliki kompleksitas waktu tinggi untuk operasi pencarian sisi.

• Membutuhkan lebih banyak ruang untuk graf yang jarang.

• Tidak mendukung pencarian sisi dengan waktu konstan.