Lewati ke konten utama
Numekara
Konsultasi GratisKontak

K1 · Modul 12

Graf 1: menjelajah

47 langkah singkat, dari mudah sampai tantangan.

  1. Level 1

    Kenal

  2. Level 2

    Paham

  3. Level 3

    Terapkan

  4. Level 4

    Tantangan

  5. Level 5

    Pendalaman

Intinya

  • Graf = titik + sisi (berarah atau tidak, berbobot atau tidak); untuk graf jarang seperti peta jalan, pakai daftar ketetanggaan.
  • BFS menjelajah tingkat demi tingkat dengan antrean dan menemukan rute dengan jalan paling sedikit; DFS menyelam sedalam mungkin dengan tumpukan atau rekursi.
  • Keduanya O(V + E); tandai titik saat ditemukan, bukan saat diambil.
  • Urutan topologis ada tepat bila graf berarah tanpa siklus (DAG); Kahn dan DFS tiga warna sekaligus mendeteksi siklus.

Sebelum mulai

±4–5 jam.

Modul ini memakai materi di bawah. Belum yakin? Ulas dulu bagian yang disebut.

Hasil belajar: setelah modul ini kamu bisa memakai istilah graf dengan tepat; memilih antara daftar dan matriks ketetanggaan; menulis BFS dan membuktikan bahwa ia menemukan rute dengan jalan paling sedikit; menulis DFS rekursif dan berulang; menghitung komponen terhubung; menyusun urutan topologis dengan Kahn dan DFS; mendeteksi siklus dengan tiga warna; serta memakai graphlib.TopologicalSorter.

Proyek: Kurir Makmur langkah 12 (kontrak Proyek Kurir §3): bangun_graf(peta), bfs_rute(graf, dari, ke) untuk rute dengan jalan paling sedikit, dan komponen(graf) untuk menemukan bagian kelurahan yang terputus.

Istilah di modul ini (30)

Ketuk istilah untuk melihat penjelasannya. Di materi, istilah bergaris titik membuka kartu yang sama. Semua istilah course

Bahan modul

Semua kode, latihan, dan data modul ini dalam satu zip, untuk dijalankan di laptop atau Google Colab.

  • 32 contoh kode
  • 10 berkas latihan + tes
  • 1 berkas data
Semua data course (data-k1.zip) Cara menjalankan di laptop
Lihat isi zip
  • BACA-DULU.txt
  • contoh_k1_12_40.py
  • contoh_k1_12_73.py
  • contoh_k1_12_141.py
  • contoh_k1_12_258.py
  • contoh_k1_12_352.py
  • contoh_k1_12_393.py
  • contoh_k1_12_427.py
  • contoh_k1_12_606.py
  • contoh_k1_12_684.py
  • contoh_k1_12_737.py
  • contoh_k1_12_785.py
  • contoh_k1_12_989.py
  • contoh_k1_12_1058.py
  • contoh_k1_12_1103.py
  • contoh_k1_12_1140.py
  • contoh_k1_12_1290.py
  • contoh_k1_12_1313.py
  • contoh_k1_12_1354.py
  • contoh_k1_12_1525.py
  • contoh_k1_12_1598.py
  • contoh_k1_12_1621.py
  • contoh_k1_12_1650.py
  • contoh_k1_12_1708.py
  • contoh_k1_12_2180.py
  • contoh_k1_12_2228.py
  • contoh_k1_12_2261.py
  • contoh_k1_12_2287.py
  • contoh_k1_12_2316.py
  • contoh_k1_12_2662.py
  • contoh_k1_12_2735.py
  • contoh_k1_12_2803.py
  • contoh_k1_12_2860.py
  • test_k1_12_1.py
  • test_k1_12_2.py
  • test_k1_12_7.py
  • test_k1_12_3.py
  • test_k1_12_6.py
  • test_k1_12_4.py
  • test_k1_12_5.py
  • test_k1_12_8.py
  • test_k1_12_9.py
  • test_k1_12_10.py
  • peta.json