BFS/DFS কমপ্লেক্সিটি ও সঠিকতা

১ · গ্রাফ রিপ্রেজেন্টেশন ও কমপ্লেক্সিটি ডেরিভেশন

এই মডিউল জুড়ে আমরা একটি গ্রাফ $G=(V,E)$-কে একটি adjacency list হিসেবে প্রতিনিধিত্ব করব — Python-এ এটি একটি dict, যেখানে প্রতিটি key একটি ভার্টেক্স এবং value হলো তার প্রতিবেশী ভার্টেক্সগুলোর একটি লিস্ট। BFS ও DFS উভয়ই এই রিপ্রেজেন্টেশনে একই মৌলিক কাঠামো অনুসরণ করে: প্রতিটি ভার্টেক্স ঠিক একবার "আবিষ্কৃত" (discovered) হয় এবং তারপর তার সম্পূর্ণ প্রতিবেশী লিস্ট ঠিক একবার স্ক্যান করা হয়।

যেহেতু প্রতিটি ভার্টেক্স $O(1)$ কাজে প্রসেস হয় (queue/stack push-pop) এবং প্রতিটি এজ ঠিক একবার (ডাইরেক্টেড গ্রাফে) স্ক্যান করা হয় (adjacency list-এ প্রতিটি এজ ঠিক একটি ভার্টেক্সের লিস্টে থাকে), মোট কাজ:

$$T(V,E) = \underbrace{O(V)}_{\text{প্রতিটি ভার্টেক্স আবিষ্কার + প্রসেস}} + \underbrace{O(E)}_{\text{প্রতিটি এজ স্ক্যান}} = \Theta(V+E)$$

লক্ষ্য করুন এটি adjacency matrix রিপ্রেজেন্টেশনের $\Theta(V^2)$ কমপ্লেক্সিটির চেয়ে ভিন্ন — স্পার্স গ্রাফে ($E \ll V^2$, যেমন বাস্তব-জীবনের নেটওয়ার্ক), adjacency list উল্লেখযোগ্যভাবে দ্রুত, কারণ আমরা অস্তিত্বহীন এজের জন্য সময় ব্যয় করি না। এই কোর্সে M7-এর সব অ্যালগরিদম adjacency list ব্যবহার করবে (কোনো তৃতীয়-পক্ষের গ্রাফ লাইব্রেরি নয় — শুধু plain dict/list এবং প্রয়োজনে heapq)।

২ · BFS-এর সঠিকতা প্রোপার্টি — নন-ডিক্রিজিং দূরত্বের ক্রম

ধরি $G=(V,E)$ একটি আনওয়েটেড গ্রাফ (ডাইরেক্টেড বা আনডাইরেক্টেড, যেকোনোটি হতে পারে) এবং $d(s,v)$ হলো সোর্স $s$ থেকে $v$-এ প্রকৃত শর্টেস্ট-পাথ দূরত্ব (এজ সংখ্যায়)। BFS-এর মূল সঠিকতা দাবি:

$$\textbf{দাবি: } \text{BFS ভার্টেক্সগুলোকে dequeue করে এমন ক্রমে } v_1, v_2, \ldots \text{ যেখানে } d(s,v_1) \le d(s,v_2) \le \cdots$$ এবং প্রতিটি $v$-এর জন্য BFS-এর নির্ণয় করা dist[v] ঠিক $d(s,v)$-এর সমান।

প্রমাণ (ইনডাকশন অন লেয়ার সংখ্যা $i$): ধরি $L_i = \{v \in V : d(s,v) = i\}$।

Base case ($i=0$): $L_0 = \{s\}$। BFS শুরুতেই dist[s] = 0 নির্ধারণ করে এবং $s$-কে queue-তে রাখে — সঠিক।

Inductive hypothesis: ধরি নিলাম $L_0, L_1, \ldots, L_i$-এর প্রতিটি ভার্টেক্স সঠিক দূরত্বসহ আবিষ্কৃত হয়েছে এবং queue-তে ঠিক এই ক্রমে (লেয়ার অনুযায়ী, প্রতি লেয়ারের ভিতরে যেকোনো ক্রমে) সাজানো আছে — অর্থাৎ $L_i$-এর সব ভার্টেক্স $L_{i+1}$-এর যেকোনো ভার্টেক্সের আগে queue-তে ছিল।

Inductive step: যখন BFS $L_i$-এর কোনো ভার্টেক্স $u$-কে dequeue করে তার প্রতিবেশী $v$ পরীক্ষা করে, দুটো সম্ভাবনা: (ক) $v$ ইতিমধ্যে আবিষ্কৃত (visited) — তাহলে কিছু করার নেই। (খ) $v$ নতুন — যেহেতু গ্রাফের একটি এজ দূরত্বকে সর্বোচ্চ ১ পরিবর্তন করতে পারে ($|d(s,u) - d(s,v)| \le 1$ যেকোনো এজ $(u,v)$-এর জন্য), এবং $v$ যদি $L_0,\ldots,L_i$-এর কোনোটাতে থাকত তবে ইনডাক্টিভ হাইপোথিসিস অনুযায়ী এটি ইতিমধ্যে আবিষ্কৃত হয়ে যেত (কারণ $L_i$ পর্যন্ত সব ভার্টেক্স ইতিমধ্যে queue-তে ঢুকে গেছে $u$ dequeue হওয়ার আগেই) — তাই $v$ অবশ্যই $L_{i+1}$-এ, অর্থাৎ $d(s,v) = i+1$। BFS ঠিক এই মুহূর্তেই dist[v] = dist[u] + 1 = i+1 নির্ধারণ করে এবং $v$-কে queue-তে রাখে — এবং যেহেতু queue FIFO, $L_i$-এর সব ভার্টেক্স $L_{i+1}$-এর সব ভার্টেক্সের আগে enqueue হয়েছিল, তাই তারা আগেই dequeue হবে। এভাবে ইনডাকশন সম্পূর্ণ হয়। $\blacksquare$

এই প্রমাণের মূল অন্তর্দৃষ্টি হলো — queue-এর FIFO ধর্ম এবং "একটি এজ দূরত্ব ১-এর বেশি পরিবর্তন করতে পারে না" এই দুটো তথ্য একসাথে গ্যারান্টি দেয় যে dequeue ক্রম কখনো দূরত্বে "পিছিয়ে" যেতে পারে না।

৩ · একটি সত্যিকারের যাচাই — BFS বনাম স্বাধীন ব্রুট-ফোর্স

উপরের প্রমাণটি বিশ্বাসযোগ্য হলেও, আমরা এটি একটি সম্পূর্ণ স্বাধীন পদ্ধতিতে কম্পিউটেশনালিও যাচাই করব — অর্থাৎ এমন একটি ফাংশন লিখব যা BFS ব্যবহার করে না, বরং সোর্স থেকে প্রতিটি ভার্টেক্সে যাওয়ার সব সিম্পল পাথ (কোনো ভার্টেক্স পুনরাবৃত্তি ছাড়া) রিকার্সিভভাবে এক্সপ্লোর করে সবচেয়ে ছোট পাথের দৈর্ঘ্য বের করে। যেহেতু একটি আনওয়েটেড গ্রাফে শর্টেস্ট পাথ কখনোই কোনো ভার্টেক্স পুনরাবৃত্তি করে না (তা করলে সেই অংশ কেটে ফেলে আরও ছোট পাথ পাওয়া যেত), তাই এই ব্রুট-ফোর্স সার্চ থেকে পাওয়া মিনিমাম দৈর্ঘ্যই প্রকৃত $d(s,v)$-এর সমান হতে বাধ্য — এটি BFS-এর নিজস্ব লজিকের উপর নির্ভর করে না, তাই একটি জেনুইন, স্বাধীন ক্রস-চেক।

from collections import deque

def bfs_distances(graph, source):
    # প্রমিত BFS: queue (FIFO) ব্যবহার করে দূরত্ব লেয়ার-বাই-লেয়ার নির্ণয়
    dist = {source: 0}
    queue = deque([source])
    dequeue_order = []
    while queue:
        u = queue.popleft()
        dequeue_order.append(u)
        for v in graph.get(u, []):
            if v not in dist:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist, dequeue_order

def brute_force_distances(graph, source):
    # সম্পূর্ণ স্বাধীন পদ্ধতি: BFS ব্যবহার না করে, সোর্স থেকে প্রতিটি ভার্টেক্সে
    # যাওয়ার সব সিম্পল পাথ রিকার্সিভভাবে এক্সপ্লোর করে সবচেয়ে ছোট দৈর্ঘ্য বের করা
    best = {source: 0}
    def explore(u, visited, depth):
        for v in graph.get(u, []):
            if v not in visited:
                if v not in best or depth + 1 < best[v]:
                    best[v] = depth + 1
                visited.add(v)
                explore(v, visited, depth + 1)
                visited.remove(v)
    explore(source, {source}, 0)
    return best

# টেস্ট গ্রাফ (আনডাইরেক্টেড, adjacency list হিসেবে দুই দিকেই এজ রাখা হয়েছে)
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3, 4],
    3: [1, 2, 5],
    4: [2, 5],
    5: [3, 4, 6],
    6: [5],
}

source = 0
dist_bfs, order = bfs_distances(graph, source)
dist_brute = brute_force_distances(graph, source)

print(f"{'vertex':>6} | {'BFS dist':>8} | {'brute-force dist':>17} | match")
all_match = True
for v in sorted(graph):
    match = dist_bfs.get(v) == dist_brute.get(v)
    all_match = all_match and match
    print(f"{v:>6} | {dist_bfs.get(v):>8} | {dist_brute.get(v):>17} | {match}")

print("\nBFS dequeue order:      ", order)
print("দূরত্ব dequeue ক্রমে:      ", [dist_bfs[v] for v in order])
is_nondecreasing = all(
    dist_bfs[order[i]] <= dist_bfs[order[i + 1]] for i in range(len(order) - 1)
)
print("dequeue ক্রম নন-ডিক্রিজিং:  ", is_nondecreasing)

print("\nসব ভার্টেক্সে BFS ও ব্রুট-ফোর্স দূরত্ব একমত:", all_match)
assert all_match, "BFS distances did not match the independent brute-force check!"
assert is_nondecreasing, "BFS dequeue order was not non-decreasing in distance!"
print("যাচাই সম্পন্ন — প্রমাণিত সঠিকতা প্রোপার্টি কোডেও নিশ্চিত হলো।")