Graphs · Graf
Graphs
- A graph is a set of nodes (also called vertices) joined by edges (connections).
- Graphs model networks: friends, roads between cities, links between web pages.
- A tree is really a special graph; a general graph can have cycles and many links per node.
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.
Representing a graph: adjacency list
- One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
graph["A"]is the list of nodes directly connected toA.- This is compact when each node has only a few connections.
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']
Adding an edge
- In an undirected graph, an edge
A—Bgoes both ways. - So adding it means appending
BtoA's list andAtoB's list. - If a node is new, start it with an empty list first.
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']}
Walking the neighbours
- To explore from a node, you read its neighbour list and visit each one.
- A node that is not in the graph has no neighbours — return an empty list, not an error.
- This neighbour lookup is the first step of bigger jobs like searching the whole graph.
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.
Directed vs undirected
- In an undirected graph an edge works both ways (a friendship).
- In a directed graph an edge points one way only (a one-way street, a "follows" link).
- For directed edges you would append in one direction only.
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.
Common mistakes
- A graph is nodes joined by edges; an edge can be one-way or two-way.
- A tree is a graph with no cycles — do not confuse the two.
Kesalahan umum
- Graf adalah node yang terhubung oleh sisi; sisi bisa satu arah atau dua arah.
- Pohon adalah graf tanpa siklus — jangan tertukar keduanya.
Now you try
- Build the adjacency-list operations:
add_edge,neighbours, andcount_edges. - Each task checks your function on a small graph.
- Press Check answer to test it.
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.
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b to graph[a] and a to graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Write neighbours(graph, node) that returns the list of nodes directly connected to node. If node is not in the graph, return an empty list [] (do not raise an error). · 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).
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Write count_edges(graph) for an undirected graph: count how many edges it has. Add up the lengths of every neighbour list, then divide by 2 (each edge is stored in both nodes' lists). Example: a triangle A–B–C has 3 edges. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.