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

টারজানের অ্যালগরিদম (Tarjan's Algorithm)

একটি ডিরেক্টেড গ্রাফের (directed graph) সমস্ত ঘনিষ্ঠভাবে যুক্ত গ্রুপকে (tightly-knit groups) একবার অতিক্রম করেই (one pass) খুঁজে বের করুন

time:O(V+E)space:O(V)output:একটিমাত্র ডিএফএস (DFS) এর মাধ্যমে সমস্ত এসসিসি (SCCs)

এমন একটি সামাজিক যোগাযোগ মাধ্যম বা সোশ্যাল নেটওয়ার্কের কথা ভাবুন যেখানে বন্ধুদের কিছু গ্রুপ একে অপরের সাথে এতটাই ঘনিষ্ঠভাবে যুক্ত থাকে যে সবাই সবার কাছে পৌঁছাতে পারে — সরাসরি বা পরিচিত বন্ধুদের মাধ্যমে। এগুলোকে বলা হয় পারস্পরিক যোগাযোগের বলয় (cliques of mutual reachability)। একটি নির্দেশিত গ্রাফ বা ডিরেক্টেড গ্রাফে (directed graph), আমরা এগুলোকে বলি স্ট্রংলি কানেক্টেড কম্পোনেন্ট বা Strongly Connected Components (SCCs)।

আনুষ্ঠানিকভাবে বলতে গেলে: একটি এসসিসি (SCC) হলো ভার্টেক্স বা শীর্যবিন্দুগুলোর এমন একটি সর্বোচ্চ সেট (maximal set) যেখানে প্রতিটি জোড়া u এবং v এর জন্য, u থেকে v পর্যন্ত এবং v থেকে u পর্যন্ত একটি নির্দেশিত বা ডিরেক্টেড পথ (directed path) থাকে। টারজানের অ্যালগরিদম একটিমাত্র ডেপথ-ফার্স্ট সার্চ (depth-first search বা DFS) ব্যবহার করে সমস্ত এসসিসি খুঁজে বের করে — এজন্য গ্রাফটিকে দুবার অতিক্রম করার (traverse) বা এটির একটি বিপরীত বা ট্রান্সপোজ (transposed) কপি তৈরি করার কোনো প্রয়োজন হয় না।

আবিষ্কার (Discovery) এবং লো-লিংক (Low-Link) মান

টারজানের ডিএফএস (DFS) প্রতিটি ভার্টেক্সের জন্য দুটি সংখ্যা ট্র্যাক বা মনে রাখে:

disc[u] — ডিএফএস (DFS) আবিষ্কারের সময় বা ডিসকভারি টাইম (এটি একটি ঘড়ি যা প্রতিবার একটি নতুন ভার্টেক্সে যাওয়ার সময় টিক করে বাড়ে)
low[u] — সবচেয়ে কম আবিষ্কারের সময় যা u এর ডিএফএস (DFS) সাবট্রি (subtree) থেকে ট্রি এজ (tree edges) এবং সর্বাধিক একটি ব্যাক এজের (back edge) মাধ্যমে পৌঁছানো যায় (ব্যাক এজ হলো এমন একটি এজ যা ডিএফএস স্ট্যাকে (DFS stack)-এ থাকা কোনো পূর্বপুরুষের (ancestor) দিকে যায়)

প্রাথমিকভাবে low[u] = disc[u]। যখন ডিএফএস (DFS) প্রতিবেশীদের (neighbors) অনুন্ধান করে:

যদি প্রতিবেশী v আগে থেকে পরিদর্শন করা না হয় (unvisited): তাহলে রিকার্স (recurse) করুন, তারপর low[u] = min(low[u], low[v]) সেট করুন
যদি প্রতিবেশী v ডিএফএস স্ট্যাকে (DFS stack) থাকে (একটি ব্যাক এজ): তাহলে low[u] = min(low[u], disc[v]) সেট করুন

স্ট্যাক (Stack) এবং এসসিসি (SCC) সনাক্তকরণ

প্রতিটি ভার্টেক্স প্রথমবার পরিদর্শন করার সময় একটি সহায়ক স্ট্যাকে (auxiliary stack) পুশ (push) করা হয়। এর মূল ধারণাটি হলো: যখন ডিএফএস (DFS) একটি ভার্টেক্স u এর কাজ শেষ করে (এর সমস্ত উত্তরসূরি বা বংশধরের কাজ শেষ হয়ে যায়), তখন যাচাই করুন low[u] == disc[u] কি না।

যদি হ্যাঁ হয়, তবে u হলো একটি এসসিসির রুট (root of an SCC) — অর্থাৎ u এর সাবট্রি থেকে এর কোনো পূর্বপুরুষের কাছে যাওয়ার বিকল্প পথ নেই। স্ট্যাক থেকে u পর্যন্ত সমস্ত কিছু পপ (pop) করে বের করে নিন — এটিই হলো একটি সম্পূর্ণ এসসিসি (SCC)।

যদি low[u] < disc[u] হয়, তবে u এর কোনো উত্তরসূরি u এর কোনো পূর্বপুরুষের কাছে পৌঁছাতে পারে, এর মানে হলো u নিজে তার নিজের এসসিসির রুট নয় — এটি আরও বড় একটি কম্পোনেন্টের অংশ।

কন্ডেনসেশন ডিএজি (Condensation DAG) থেকে কী জানা যায়

একবার যখন সমস্ত এসসিসি (SCC) পাওয়া যায়, তখন প্রতিটি এসসিসি (SCC)-কে একটি সুপার-নোড (super-node) দিয়ে প্রতিস্থাপন করুন। এর ফলে যে গ্রাফটি তৈরি হয় — যাকে বলা হয় কন্ডেনসেশন ডিএজি (condensation DAG) — এটি সর্বদা অ্যাসাইক্লিক বা চক্রহীন (acyclic) হয় (কারণ কম্পোনেন্টগুলোর ভেতরের চক্রগুলো বা সাইকেলগুলো আগে থেকেই ভেঙে ফেলা হয়েছে)। এই ডিএজি (DAG) উচ্চতর স্তরের কাঠামো বা হাই-লেভেল স্ট্রাকচার তুলে ধরে: কোন কম্পোনেন্টগুলো কোন অন্যান্য কম্পোনেন্টে পৌঁছাতে পারে। এটি কম্পোনেন্টের স্তরে টপোলজিক্যাল সর্ট (topological sort) এর মতো ভবিষ্যতের অ্যালগরিদমগুলোর জন্য একটি ভিত্তি হিসেবে কাজ করে।

সম্প্রসারণ: ব্রিজ (Bridges) এবং আর্টিকুলেশন পয়েন্ট (Articulation Points)

একই ডিএফএস (DFS) ফ্রেমওয়ার্ক অনির্দেশিত বা আনডিরেক্টেড (undirected) গ্রাফে কাজ করে নিচের জিনিসগুলো খুঁজে বের করতে পারে:

ব্রিজ (Bridge): যদি low[v] > disc[u] হয়, তবে এজ (u, v) একটি ব্রিজ — এটিকে সরিয়ে দিলে গ্রাফটি সংযোগ বিচ্ছিন্ন (disconnect) হয়ে যায়
আর্টিকুলেশন পয়েন্ট (Articulation point): ভার্টেক্স u একটি আর্টিকুলেশন পয়েন্ট, যদি এটিকে সরালে গ্রাফটি সংযোগ বিচ্ছিন্ন হয়ে যায় (রুট বা নন-রুটের ক্ষেত্রে শর্ত ভিন্ন হয়)

এর সবগুলোই একটিমাত্র ডিএফএস (DFS) পাস ব্যবহার করে খুঁজে পাওয়া সম্ভব — যার জন্য মোট সময় লাগে O(V+E)।

দ্রষ্টব্য: low[u] এই প্রশ্নের উত্তর দেয়: 'আমার ডিএফএস (DFS) সাবট্রির কোনো ভার্টেক্স কি ব্যাক এজ ব্যবহার করে চুপিসারে কোনো পূর্বপুরুষের কাছে পৌঁছাতে বা ফিরে যেতে পারে?' যদি low[u] == disc[u] হয়, তবে উত্তরটি হলো না — অর্থাৎ u এবং তার সাবট্রি একটি সুরক্ষিত বা সিল করা (sealed-off) গ্রুপ তৈরি করেছে যেখান থেকে বের হওয়ার কোনো রাস্তা নেই। সেই সুরক্ষিত বা সিল করা গ্রুপটিই হলো একটি এসসিসি (SCC)।

টারজানের এসসিসি (SCC) অ্যালগরিদম

def tarjans_scc(n, adj):
    """
    n: number of vertices
    adj: adjacency list
    Returns list of SCCs (each SCC is a list of vertex indices).
    """
    disc = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    sccs = []
    timer = [0]

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        stack.append(u)
        on_stack[u] = True

        for v in adj[u]:
            if disc[v] == -1:       # unvisited
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:       # back edge to ancestor
                low[u] = min(low[u], disc[v])

        if low[u] == disc[u]:       # u is SCC root
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == u:
                    break
            sccs.append(scc)

    for u in range(n):
        if disc[u] == -1:
            dfs(u)
    return sccs

# Graph: 0->1, 1->2, 2->0, 1->3, 3->4, 4->5, 5->3
adj = [[1],[2,3],[0],[4],[5],[3]]
sccs = tarjans_scc(6, adj)
for scc in sccs:
    print(sorted(scc))