Jawaban:

Berikut adalah langkah-langkah pengerjaannya:

Breadth First Search (BFS):

1. Mulai dari simpul A.

2. Tandai simpul A sebagai simpul awal dan masukkan ke dalam antrian.

3. Selama antrian tidak kosong, lakukan hal berikut:

a. Keluarkan simpul dari depan antrian.

b. Jika simpul tersebut adalah simpul tujuan (G), maka solusi telah ditemukan. Kembali ke simpul awal dan ikuti garis-garis yang telah ditandai untuk menemukan lintasan.

c. Jika simpul tersebut bukan simpul tujuan, tandai simpul tersebut sebagai simpul yang telah dikunjungi.

d. Masukkan semua simpul tetangga yang belum dikunjungi ke dalam antrian.

4. Jika antrian kosong dan simpul tujuan belum ditemukan, maka tidak ada solusi yang ditemukan.

Uniform Cost Search (UCS):

1. Mulai dari simpul A.

2. Tandai simpul A sebagai simpul awal dan masukkan ke dalam antrian dengan biaya 0.

3. Selama antrian tidak kosong, lakukan hal berikut:

a. Keluarkan simpul dengan biaya terkecil dari depan antrian.

b. Jika simpul tersebut adalah simpul tujuan (G), maka solusi telah ditemukan. Kembali ke simpul awal dan ikuti garis-garis yang telah ditandai untuk menemukan lintasan.

c. Jika simpul tersebut bukan simpul tujuan, tandai simpul tersebut sebagai simpul yang telah dikunjungi.

d. Masukkan semua simpul tetangga yang belum dikunjungi ke dalam antrian dengan biaya yang sesuai.

4. Jika antrian kosong dan simpul tujuan belum ditemukan, maka tidak ada solusi yang ditemukan.

Dalam kedua algoritma ini, kita perlu menggunakan matriks atau daftar adjacency untuk merepresentasikan grafik dan menentukan simpul-simpul tetangga dari setiap simpul. Dalam kasus ini, kita dapat merepresentasikan diagram lintasan dengan matriks atau daftar adjacency seperti berikut:

-----------------------------------------------------------

Matriks adjacency:

  A   a   B   D   G

A  0   2   0   0   0

a  2   0   1   0   0

B  0   1   0   5   0

D  0   0   5   0   6

G  0   0   0   6   0

-----------------------------------------------------------

Daftar adjacency:

A: a

a: A, B

B: a, D

D: B, G

G: D

Kita dapat menghasilkan solusi yang sama dengan kedua algoritma, yaitu A - a - B - D - G dengan biaya total 13.