গ্রাফ এবং এর ট্রাভার্সাল অ্যালগরিদম

এই সেকশনে আমরা দেখব গ্রাফ ডেটা স্ট্রাকচার কী এবং এর ট্রাভার্সাল অ্যালগরিদম।

গ্রাফ একটি নন-লিনিয়ার ডেটা স্ট্রাকচার। এতে কিছু নোড এবং তাদের কানেক্টেড এজ থাকে। এজগুলো ডিরেক্টেড বা আনডিরেক্টেড হতে পারে। এই গ্রাফকে G(V, E) হিসেবে রিপ্রেজেন্ট করা যায়। নিচের গ্রাফকে G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C), (C, A)}) হিসেবে রিপ্রেজেন্ট করা যায়।

গ্রাফের দুটি ধরনের ট্রাভার্সাল অ্যালগরিদম রয়েছে। এগুলোকে ব্রেডথ ফার্স্ট সার্চ এবং ডেপথ ফার্স্ট সার্চ বলা হয়।

ব্রেডথ ফার্স্ট সার্চ (BFS)

ব্রেডথ ফার্স্ট সার্চ (BFS) ট্রাভার্সাল একটি অ্যালগরিদম, যা একটি দিয়ে গিয়ে গ্রাফের সব নোড ভিজিট করতে ব্যবহৃত হয়। এই ট্রাভার্সাল অ্যালগরিদমে একটি নোড সিলেক্ট করা হয় এবং তারপর সব অ্যাডজেসেন্ট নোড একে একে ভিজিট করা হয়। সব অ্যাডজেসেন্ট ভার্টেক্স কমপ্লিট হলে, এটি আরও ভার্টেক্স চেক করতে যাবে এবং আবার তার অ্যাডজেসেন্ট ভার্টেক্স চেক করবে।

অ্যালগরিদম

bfs(vertices, start)
Input: The list of vertices, and the start vertex.
Output: Traverse all of the nodes, if the graph is connected.
Begin
    define an empty queue que
    at first mark all nodes status as unvisited
    add the start vertex into the que
    while que is not empty, do
        delete item from que and set to u
        display the vertex u
        for all vertices 1 adjacent with u, do
            if vertices[i] is unvisited, then
                mark vertices[i] as temporarily visited
                add v into the queue
            done
        mark u as completely visited
    done
End

ডেপথ ফার্স্ট সার্চ (DFS)

ডেপথ ফার্স্ট সার্চ (DFS) একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম। এই অ্যালগরিদমে একটি স্টার্টিং ভার্টেক্স দেওয়া হয়, এবং যখন একটি অ্যাডজেসেন্ট ভার্টেক্স পাওয়া যায়, সেটি প্রথমে সেটিতে মুভ করে এবং একই রকমে ট্রাভার্স করার চেষ্টা করে।

অ্যালগরিদম

dfs(vertices, start)
Input: The list of all vertices, and the start node.
Output: Traverse all nodes in the graph.
Begin
    initially make the state to unvisited for all nodes
    push start into the stack
    while stack is not empty, do
        pop element from stack and set to u
        display the node u
        if u is not visited, then
            mark u as visited
            for all nodes i connected to u, do
                if ith vertex is unvisited, then
                    push ith vertex into the stack
                    mark ith vertex as visited
                done
            done
    done
End