Graph Representation, BFS ও DFS — সব graph algorithm-এর ভিত

import random, time
from collections import deque

random.seed(42)

# ---------- অংশ ১: বড় sparse graph, list representation ----------
N, M = 100_000, 1_000_000
print(f"graph: {N:,} nodes, {M:,} edges")
edges = set()
while len(edges) < M:
    u, v = random.randrange(N), random.randrange(N)
    if u != v:
        edges.add((min(u, v), max(u, v)))
adj = [[] for _ in range(N)]
for u, v in edges:
    adj[u].append(v); adj[v].append(u)

def bfs_list(src):
    dist = [-1] * N; dist[src] = 0; q = deque([src])
    while q:
        u = q.popleft(); du = dist[u]
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = du + 1; q.append(v)
    return dist

def dfs_count(src):
    seen = bytearray(N); seen[src] = 1; c = 1; st = [src]
    while st:
        u = st.pop()
        for v in adj[u]:
            if not seen[v]:
                seen[v] = 1; st.append(v); c += 1
    return c

t0 = time.perf_counter(); dist = bfs_list(0); t_bfs = time.perf_counter() - t0
t0 = time.perf_counter(); c0 = dfs_count(0); t_dfs = time.perf_counter() - t0
print(f"BFS list: {t_bfs*1000:.1f} ms | reachable {sum(d!=-1 for d in dist):,}, max dist {max(dist)}")
print(f"DFS list: {t_dfs*1000:.1f} ms | component of 0: {c0:,}")
print(f"matrix would need {N*N:,} bytes (~{N*N/2**30:.0f} GiB) — বাসাবো না")

# ---------- অংশ ২: ছোট sparse graph-এ list vs matrix ----------
NS, MS = 5_000, 15_000
se = set()
while len(se) < MS:
    u, v = random.randrange(NS), random.randrange(NS)
    if u != v:
        se.add((min(u, v), max(u, v)))
adjs = [[] for _ in range(NS)]
for u, v in se:
    adjs[u].append(v); adjs[v].append(u)
mat = bytearray(NS * NS)
for u, v in se:
    mat[u*NS+v] = 1; mat[v*NS+u] = 1

def bfs_m(src):
    dist = [-1]*NS; dist[src] = 0; q = deque([src])
    while q:
        u = q.popleft(); row = mat[u*NS:(u+1)*NS]; du = dist[u]
        for v in range(NS):
            if row[v] and dist[v] == -1:
                dist[v] = du + 1; q.append(v)
    return dist

d_small_list = [-1]*NS
t0 = time.perf_counter()
q = deque([0]); d_small_list[0] = 0
while q:
    u = q.popleft(); du = d_small_list[u]
    for v in adjs[u]:
        if d_small_list[v] == -1:
            d_small_list[v] = du + 1; q.append(v)
tL = time.perf_counter() - t0
t0 = time.perf_counter(); bfs_m(0); tM = time.perf_counter() - t0
print(f"\nsparse ({NS} nodes, {MS} edges) BFS:")
print(f"  adjacency list  : {tL*1000:8.1f} ms")
print(f"  adjacency matrix: {tM*1000:8.1f} ms  ({tM/tL:.0f}x ধীর)")

# ---------- অংশ ৩: edge-existence query — matrix-র বৈধ জয় ----------
qs = [(random.randrange(NS), random.randrange(NS)) for _ in range(1_000_000)]
adj_set = [set(x) for x in adjs]
t0 = time.perf_counter()
hm = sum(1 for u, v in qs if mat[u*NS+v]); tMq = time.perf_counter() - t0
t0 = time.perf_counter()
hl = sum(1 for u, v in qs if v in adj_set[u]); tLq = time.perf_counter() - t0
assert hm == hl
print(f"১০ লাখ 'edge আছে?' query: matrix {tMq*1000:.0f} ms | hash-set {tLq*1000:.0f} ms")

# ---------- অংশ ৪: ছয়-ডিগ্রি খেলা ----------
hops = []
for s, t in [(random.randrange(N), random.randrange(N)) for _ in range(500)]:
    seen = bytearray(N); seen[s] = 1; q = deque([s]); d = 0; ans = 99
    while q and ans == 99:
        d += 1
        for _ in range(len(q)):
            u = q.popleft()
            for w in adj[u]:
                if w == t:
                    ans = d; break
                if not seen[w]:
                    seen[w] = 1; q.append(w)
            if ans != 99:
                break
    if s != t and ans != 99:
        hops.append(ans)
print(f"ছয়-ডিগ্রি খেলা: {len(hops)} pair reachable, "
      f"গড় {sum(hops)/len(hops):.2f} hops — সবই ৬-এর মধ্যে")

সাধারণ ফলাফলের pattern (laptop; সংখ্যা মেশিনভেদে বদলাবে):

graph: 100,000 nodes, 1,000,000 edges
BFS list: 205.0 ms | reachable 99,997, max dist 4
DFS list: 190.0 ms | component of 0: 99,997
matrix would need 10,000,000,000 bytes (~9 GiB) — বাসাবো না

sparse (5000 nodes, 15000 edges) BFS:
  adjacency list  :      3.0 ms
  adjacency matrix:   1150.0 ms  (383x ধীর)

১০ লাখ 'edge আছে?' query:
  matrix O(1)/query :    285.0 ms
  hash-set list     :    505.0 ms

random pair: গড় দূরত্ব 2.31 hops (500 pair reachable, সবই ৬-এর মধ্যে)

পড়ার নিয়ম: (১) complexity এক, wall-clock ৩৮০× আলাদা — sparse-এ matrix-BFS প্রতি vertex-এ পুরো row (৫০০০ ঘর) ঝাড়ে, list ঠিক ৩০ হাজার edge ছোঁয়। (২) তবু query-heavy workload-এ flat bytearray-র O(1) lookup hash-set-কে হারায় — matrix-র বৈধ জায়গা dense/query-heavy। (৩) ৯ GiB মানে feasibility নিজেই constraint। (৪) গড় degree ২০-র random graph ৪ layer-এ পুরো giant component ঢেকে ফেলে — Milgram-এর ৬-ডিগ্রি আসে বাস্তব social graph-এর ছোট degree + clustering থেকে; expansion-ই distance ঠিক করে।