গ্রাফ অ্যালগরিদম৭ মিনিট পড়া

টপোলজিক্যাল সর্ট (Topological Sort)

কাজগুলোকে তাদের নির্ভরতা অনুযায়ী সাজান — ডিম আগে না মুরগি আগে, এমন দ্বন্দ্ব থাকবে না

time:O(V+E)space:O(V)requirement:DAG (শুধুমাত্র ডিরেক্টেড অ্যাসাইক্লিক গ্রাফ)

ধরুন আপনি বিশ্ববিদ্যালয়ের কোর্স বাছাই করছেন। আপনি ক্যালকুলাস ১ করার আগে কোনোভাবেই ক্যালকুলাস ২ করতে পারবেন না। ডেটা স্ট্রাকচার না করে অ্যালগরিদম করতে পারবেন না। প্রতিটি কোর্সেরই কিছু পূর্বশর্ত (prerequisite) বা আগের প্রয়োজনীয় কোর্স থাকে, এবং আপনাকে এমন একটি বৈধ ক্রম বা অর্ডার বের করতে হবে যাতে আপনি সবগুলো কোর্স করতে পারেন।

ঠিক এই কাজটিই করে টপোলজিক্যাল সর্ট (Topological Sort): যখন নির্ভরতা বা ডিপেন্ডেন্সি (যেমন, "B-এর আগে অবশ্যই A-কে হতে হবে") আছে এমন অনেকগুলো কাজ দেওয়া হয়, তখন এটি এমন একটি ক্রম খুঁজে বের করে যেখানে প্রতিটি নির্ভরতা বা শর্ত পূরণ করা হয়। এর ফলাফলের প্রতিটি এজ (edge) বা রেখা সামনের দিকে নির্দেশ করে — অর্থাৎ কোনো কাজ কখনোই তার ওপর নির্ভরশীল কোনো কাজের পরে আসে না।

সবচেয়ে কঠিন একটি নিয়ম: কোনো সাইকেল থাকা যাবে না

টপোলজিক্যাল সর্ট শুধুমাত্র একটি ডিরেক্টেড অ্যাসাইক্লিক গ্রাফে (DAG - Directed Acyclic Graph) কাজ করে — অর্থাৎ এমন একটি নির্দেশিত গ্রাফ যেখানে কোনো সাইকেল বা চক্র নেই। কারণ কী? ধরুন কোর্স A নেওয়ার জন্য কোর্স B লাগবে, আবার কোর্স B নেওয়ার জন্য কোর্স A লাগবে, তাহলে এই কোর্সগুলো নেওয়ার কোনো বৈধ ক্রমই থাকা সম্ভব নয়। একটি সাইকেল বা চক্র টপোলজিক্যাল অর্ডারিংকে অসম্ভব করে তোলে। যেকোনো অ্যালগরিদম যা এই অসম্ভব পরিস্থিতিটি শনাক্ত করতে পারে, তা আপনার জন্য বড় একটি সুবিধা।

কানের অ্যালগরিদম (Kahn's Algorithm - ইন-ডিগ্রি ট্র্যাকিং সহ BFS)

ইন-ডিগ্রি (in-degree)-কে এমনভাবে কল্পনা করুন যেন এটি একটি কাজের বাকি থাকা পূর্বশর্তের সংখ্যা। ইন-ডিগ্রি 0 হওয়া মানে হলো কাজটির কোনো অপূর্ণ পূর্বশর্ত নেই — অর্থাৎ সেগুলো শুরু করার জন্য প্রস্তুত।

কান-এর অ্যালগরিদমের ধাপগুলো:

প্রতিটি ভার্টেক্স বা নোডের ইন-ডিগ্রি গণনা করুন।
যে ভার্টেক্সগুলোর ইন-ডিগ্রি 0, সেগুলোকে একটি কিউ-তে (queue) রাখুন।
ক্রমাগত কিউ থেকে একটি একটি করে ভার্টেক্স u বের করুন, সেটিকে ফলাফলে যুক্ত করুন, এবং এর প্রতিটি প্রতিবেশী v-এর ইন-ডিগ্রি এক করে কমান। যদি কোনো v-এর ইন-ডিগ্রি কমে 0 হয়ে যায়, তবে সেটিকে কিউ-তে যুক্ত করুন।
যদি ফলাফলে সমস্ত V সংখ্যক ভার্টেক্স থাকে, তবে সেটি একটি বৈধ টপোলজিক্যাল অর্ডার। আর যদি না থাকে — তবে গ্রাফটিতে একটি সাইকেল রয়েছে এবং কোনো বৈধ ক্রম সম্ভব নয়।

এখানে সাইকেল ডিটেকশন বা শনাক্তকরণ একদম বিনামূল্যে পাওয়া যায়: সাইকেলে আটকে থাকা ভার্টেক্সগুলোর ইন-ডিগ্রি কখনোই 0 তে পৌঁছায় না, তাই এগুলোকে কখনোই ফলাফলে যুক্ত করা হয় না।

ডিএফএস-ভিত্তিক পদ্ধতি (রিভার্স পোস্ট-অর্ডার)

একটি স্বাভাবিক ডিএফএস (DFS) চালান। যখন কোনো ভার্টেক্সের ডিএফএস কল রিটার্ন করে (অর্থাৎ এর সমস্ত বংশধরকে পুরোপুরি অন্বেষণ করা হয়েছে), তখন সেটিকে একটি স্ট্যাকে (stack) পুশ করুন। যখন সমস্ত ভার্টেক্সের জন্য ডিএফএস সম্পন্ন হয়, তখন স্ট্যাকটি ওপর থেকে নিচে বা টপ-টু-বটম পড়লেই আপনি একটি বৈধ টপোলজিক্যাল অর্ডার পেয়ে যাবেন।

এটি কেন কাজ করে? যদি u → v একটি এজ থাকে, তবে ডিএফএস u-কে শেষ করার আগেই v-কে পুরোপুরি শেষ করে (u-এর কল ততক্ষণ পর্যন্ত রিটার্ন করতে পারে না যতক্ষণ না এর বংশধররা শেষ হয়)। তাই u স্ট্যাকের আরও গভীরে পৌঁছায় — এবং পপ (pop) করার অর্ডারে আগেই বের হয়ে আসে।

ব্যবহার (Applications)

টপোলজিক্যাল সর্ট সবখানেই ব্যবহৃত হয়: বিল্ড সিস্টেমে (build systems) (নির্ভরতার ক্রমানুসারে ফাইল কম্পাইল করা), প্যাকেজ ম্যানেজারে (package managers) (যে কোড লাইব্রেরি ব্যবহার করবে তার আগেই লাইব্রেরিগুলো ইনস্টল করা), কোর্স শিডিউলিংয়ে (course scheduling) (আগে পূর্বশর্ত কোর্সগুলো করা), এবং DAG-তে ডিপি (DP on DAGs) (রিভার্স টপোলজিক্যাল অর্ডারে বিভিন্ন অবস্থা বা স্টেট প্রসেস করা যাতে সমস্ত সাব-প্রবলেমগুলো আগে থেকেই তৈরি থাকে)।

দ্রষ্টব্য: একটি টপোলজিক্যাল অর্ডারিং কখনো অনন্য (unique) হয় না — একটি গ্রাফের অনেকগুলো বৈধ অর্ডারিং থাকতে পারে। জিরো ইন-ডিগ্রি থাকা কোন নোডগুলোকে আপনি আগে কিউ-তে রাখবেন তার ওপর ভিত্তি করে কানের অ্যালগরিদম ভিন্ন ভিন্ন ফলাফল দিতে পারে। এবং এর সবগুলোই সঠিক।

কানের অ্যালগরিদম এবং ডিএফএস-ভিত্তিক টপোলজিক্যাল সর্ট

from collections import deque

def kahns_topo(n, edges):
    """Kahn's BFS-based topological sort. Returns [] if cycle detected."""
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indegree[v] += 1
    queue = deque(u for u in range(n) if indegree[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == n else []  # empty = cycle

def dfs_topo(n, edges):
    """DFS-based topological sort."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    visited = [False] * n
    stack = []
    def dfs(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)
    for u in range(n):
        if not visited[u]:
            dfs(u)
    return stack[::-1]

# 0->1, 0->2, 1->3, 2->3
edges = [(0,1),(0,2),(1,3),(2,3)]
print(kahns_topo(4, edges))  # [0, 1, 2, 3] or [0, 2, 1, 3]
print(dfs_topo(4, edges))    # [0, 2, 1, 3] or similar valid order