Graf
- Sebuah graf adalah kumpulan node (juga disebut titik/vertex) yang dihubungkan oleh sisi (koneksi).
- Graf memodelkan jaringan: teman, jalan antar kota, tautan antar halaman web.
- Pohon sebenarnya adalah graf khusus; graf umum dapat memiliki siklus dan banyak sisi per node.
Merepresentasikan graf: daftar ketetanggaan
- Salah satu cara umum adalah daftar ketetanggaan: sebuah kamus yang memetakan setiap node ke daftar tetangganya.
graph["A"]adalah daftar node yang terhubung langsung keA.- Ini efisien ketika setiap node hanya memiliki sedikit koneksi.
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
Menambahkan sisi
- Dalam graf tak berarah, sisi
A—Bberjalan dua arah. - Jadi menambahkannya berarti menambahkan
Bke daftarAdanAke daftarB. - Jika node baru, mulailah dengan daftar kosong terlebih dahulu.
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
Menelusuri tetangga
- Untuk menjelajahi dari suatu node, baca daftar tetangganya dan kunjungi setiap satuannya.
- Node yang tidak ada di graf memiliki tidak ada tetangga — kembalikan daftar kosong, bukan error.
- Pencarian tetangga ini merupakan langkah awal tugas-tugas besar seperti pencarian seluruh graf.
Berarah vs Tak Berarah
- Dalam graf tak berarah, sisi bekerja dua arah (persahabatan).
- Dalam graf berarah, sisi hanya menunjuk satu arah (jalan satu arah, tautan "mengikuti").
- Untuk sisi berarah Anda akan menambahkan dalam satu arah saja.
Kesalahan umum
- Graf adalah node yang terhubung oleh sisi; sisi bisa satu arah atau dua arah.
- Pohon adalah graf tanpa siklus — jangan tertukar keduanya.
Sekarang Anda coba
- Bangun operasi daftar ketetanggaan:
add_edge,neighbours, dancount_edges. - Setiap tugas memeriksa fungsi Anda pada graf kecil.
- Tekan Cek jawaban untuk mengujinya.
Kesulitan 5/5 · 400 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis add_edge(graph, a, b) untuk graf tak berarah yang disimpan sebagai dict daftar tetangga. Tambahkan b ke graph[a] dan a ke graph[b]. Jika node belum ada di graf, berikan daftar kosong [] terlebih dahulu. Ubah dict in place.
Klik Jalankan untuk melihat output di sini.
Kesulitan 5/5 · 400 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis neighbours(graph, node) yang mengembalikan daftar node yang terhubung langsung ke node. Jika node tidak ada di graf, kembalikan daftar kosong [] (jangan buatkan error).
Klik Jalankan untuk melihat output di sini.
Kesulitan 5/5 · 400 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis count_edges(graph) untuk graf tak berarah: hitung berapa banyak sisinya. Jumlahkan panjang setiap daftar tetangga, lalu bagi dengan 2 (setiap sisi disimpan di daftar kedua node). Contoh: segitiga A–B–C memiliki 3 sisi.
Klik Jalankan untuk melihat output di sini.