# ====== Setup Graph (Grid) ======
# Membuat graf grid 2D dan menghapus sebagian edge sebagai "dinding" sederhana.

import random, time
import networkx as nx
import matplotlib.pyplot as plt

W, H = 10, 8
start = (0,0)
goal  = (H-1, W-1)

G = nx.grid_2d_graph(H, W)  # node: (r,c)

random.seed(42)
remove_ratio = 0.15
edges = list(G.edges())
random.shuffle(edges)
for e in edges[:int(len(edges)*remove_ratio)]:
    G.remove_edge(*e)

# Pastikan ada jalur; kalau tidak, sambungkan lagi sebagian edge
if not nx.has_path(G, start, goal):
    for e in edges[int(len(edges)*remove_ratio)//2:]:
        G.add_edge(*e)
        if nx.has_path(G, start, goal):
            break

pos = {(r,c):(c,-r) for r,c in G.nodes()}  # tata letak grid

plt.figure(figsize=(6,4))
nx.draw(G, pos, node_size=60, width=1, with_labels=False)
plt.title("Graf Grid (dataset lab)")
plt.show()

Jika networkx belum ada: jalankan !pip install networkx di sel terpisah.

# ====== Implementasi BFS, DFS, dan UCS ======
from collections import deque
import heapq, math, time

# Helper: reconstruct path dari parent map
def reconstruct(goal, parent):
    path = []
    cur = goal
    while cur is not None:
        path.append(cur)
        cur = parent.get(cur)
    return list(reversed(path))

# BFS (unweighted)
def bfs(G, start, goal):
    q = deque([start])
    visited = {start}
    parent = {start: None}
    expanded = 0
    t0 = time.perf_counter()
    while q:
        u = q.popleft()
        expanded += 1
        if u == goal:
            dt = time.perf_counter() - t0
            return reconstruct(goal, parent), expanded, dt
        for v in G.neighbors(u):
            if v not in visited:
                visited.add(v)
                parent[v] = u
                q.append(v)
    dt = time.perf_counter() - t0
    return None, expanded, dt

# DFS (limit sederhana agar tidak looping terlalu dalam)
def dfs(G, start, goal, depth_limit=10_000):
    stack = [(start, 0)]
    visited = set([start])
    parent = {start: None}
    expanded = 0
    t0 = time.perf_counter()
    while stack:
        u, depth = stack.pop()
        expanded += 1
        if u == goal:
            dt = time.perf_counter() - t0
            return reconstruct(goal, parent), expanded, dt
        if depth < depth_limit:
            for v in G.neighbors(u):
                if v not in visited:
                    visited.add(v)
                    parent[v] = u
                    stack.append((v, depth+1))
    dt = time.perf_counter() - t0
    return None, expanded, dt

# UCS (biaya seragam = 1 per edge → setara shortest path unweighted)
def ucs(G, start, goal, cost=lambda u,v: 1):
    pq = [(0, start)]  # (g, node)
    parent = {start: None}
    best = {start: 0}
    expanded = 0
    t0 = time.perf_counter()
    while pq:
        g, u = heapq.heappop(pq)
        expanded += 1
        if u == goal:
            dt = time.perf_counter() - t0
            return reconstruct(goal, parent), expanded, dt, g
        for v in G.neighbors(u):
            ng = g + cost(u,v)
            if v not in best or ng < best[v]:
                best[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng, v))
    dt = time.perf_counter() - t0
    return None, expanded, dt, math.inf

# === Jalankan & Bandingkan ===
path_bfs, exp_bfs, t_bfs = bfs(G, start, goal)
path_dfs, exp_dfs, t_dfs = dfs(G, start, goal)
path_ucs, exp_ucs, t_ucs, cost_ucs = ucs(G, start, goal)

print("Hasil:")
print(f"BFS : langkah={len(path_bfs)-1 if path_bfs else None}, expanded={exp_bfs}, waktu={t_bfs:.6f}s")
print(f"DFS : langkah={len(path_dfs)-1 if path_dfs else None}, expanded={exp_dfs}, waktu={t_dfs:.6f}s")
print(f"UCS : langkah={len(path_ucs)-1 if path_ucs else None}, expanded={exp_ucs}, waktu={t_ucs:.6f}s, cost={cost_ucs}")

# Visualisasi jalur BFS & UCS
import matplotlib.pyplot as plt
pos = {(r,c):(c,-r) for r,c in G.nodes()}
plt.figure(figsize=(6,4))
nx.draw(G, pos, node_size=60, width=1, with_labels=False)
if path_bfs:
    nx.draw_networkx_nodes(G, pos, nodelist=path_bfs, node_size=80)
    nx.draw_networkx_edges(G, pos, edgelist=list(zip(path_bfs, path_bfs[1:])), width=3)
plt.title("Jalur BFS")
plt.show()

plt.figure(figsize=(6,4))
nx.draw(G, pos, node_size=60, width=1, with_labels=False)
if path_ucs:
    nx.draw_networkx_nodes(G, pos, nodelist=path_ucs, node_size=80)
    nx.draw_networkx_edges(G, pos, edgelist=list(zip(path_ucs, path_ucs[1:])), width=3)
plt.title("Jalur UCS (biaya seragam)")
plt.show()

Ubah W,H,remove_ratio,seed dan bandingkan metrik (langkah, expanded, waktu).

# ====== Kuis 3 (cek mandiri) ======
qs = [
  ("Struktur data utama BFS adalah...", {"a":"stack","b":"queue","c":"priority queue","d":"hashmap"}, "b"),
  ("UCS pada graf dengan semua edge berbobot 1 setara dengan...", {"a":"DFS","b":"BFS","c":"A*","d":"Hill climbing"}, "b"),
  ("Kerugian utama DFS adalah...", {"a":"Butuh memori besar","b":"Selalu menemukan jalur optimal","c":"Tersesat di cabang dalam","d":"Tidak bisa digunakan di graf"}, "c"),
]
print("Kunci jawaban:")
for i, (_, __, ans) in enumerate(qs,1):
    print(f"Q{i}: {ans}")