TES PEMAHAMAN GRAPH

Struktur data graph paling tepat digunakan untuk merepresentasikan apa?

• Daftar nilai siswa dalam urutan tertentu.

• Hubungan hierarkis antara karyawan dan manajer dalam sebuah perusahaan.

• Koleksi item unik tanpa urutan atau hubungan eksplisit.

• Jaringan jalan antar kota atau pertemanan di media sosial.

• Tumpukan buku yang akan dibaca.

Dalam representasi Adjacency Matrix untuk sebuah graph tidak berarah dengan V jumlah vertex dan E jumlah edge, berapakah kompleksitas ruang (space complexity) yang dibutuhkan?

• O(V)

• O(E)

• O(V+E)

Algoritma traversal graph yang menggunakan prinsip Last-In, First-Out (LIFO) dan cocok untuk menemukan jalur atau mendeteksi siklus adalah:

• Breadth-First Search (BFS)

• Dijkstra's Algorithm

• Depth-First Search (DFS)

• Prim's Algorithm

• Kruskal's Algorithm

Sebuah graph tak berarah dikatakan connected (terhubung) jika:

• Setiap vertex memiliki setidaknya satu edge.

• Terdapat siklus yang melewati setiap vertex.

• Ada jalur antara setiap pasangan vertex.

• Setiap edge memiliki bobot yang berbeda.

• Jumlah edge sama dengan jumlah vertex dikurangi satu.

Dalam sebuah graph berbobot, algoritma manakah yang digunakan untuk menemukan jalur terpendek dari satu sumber ke semua vertex lainnya, asalkan tidak ada bobot edge yang negatif?

• Bellman-Ford Algorithm

• Floyd-Warshall Algorithm

• Prim's Algorithm

• Kruskal's Algorithm

• Dijkstra's Algorithm