Trees এবং Graphs এর সাথে কাজ করা

লুয়া (Lua) ভাষায় গাছ (Trees) এবং গ্রাফ (Graphs) ডেটা স্ট্রাকচার তৈরি এবং পরিচালনা করা খুবই নমনীয় এবং সহজ। কারণ, লুয়া টেবিলগুলি (tables) ডেটা সংরক্ষণের জন্য একটি সাধারণ, শক্তিশালী এবং নমনীয় উপায় প্রদান করে। আমরা এখানে গাছ (Trees) এবং গ্রাফ (Graphs) ডেটা স্ট্রাকচারগুলি তৈরি করার জন্য টেবিল এবং কিছু বেসিক এলগরিদম নিয়ে আলোচনা করব।

১. গাছ (Trees)

গাছ (Tree) হল একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার যা নোড (Node) দ্বারা গঠিত। প্রতিটি নোডের মধ্যে একটি মান থাকে এবং এটি এক বা একাধিক চাইল্ড নোডের সাথে যুক্ত থাকে। গাছের সবচেয়ে শীর্ষে থাকা নোডটিকে রুট (Root) বলা হয়।

গাছের উপাদান:

• নোড (Node): একটি গাছের মৌলিক একক, যা একটি ডেটা ধারণ করে।
• রুট (Root): গাছের শীর্ষ নোড।
• চাইল্ড (Child): কোন নোডের নিচের স্তরের নোড।
• লিফ (Leaf): যে নোডে কোনো চাইল্ড নোড নেই।

উদাহরণ: বাইনারি গাছ (Binary Tree)

একটি সিম্পল বাইনারি গাছ তৈরি করা, যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকতে পারে:

-- একটি বাইনারি গাছের জন্য নোড তৈরি
Node = {}
Node.__index = Node

function Node.new(value)
    local self = setmetatable({}, Node)
    self.value = value
    self.left = nil
    self.right = nil
    return self
end

-- গাছের মধ্যে মান যোগ করার ফাংশন
function insert(root, value)
    if root == nil then
        return Node.new(value)
    end

    if value < root.value then
        root.left = insert(root.left, value)
    else
        root.right = insert(root.right, value)
    end
    return root
end

-- গাছটি ইন অর্ডার (Inorder) ট্র্যাভার্স করার ফাংশন
function inorderTraversal(root)
    if root ~= nil then
        inorderTraversal(root.left)
        print(root.value)
        inorderTraversal(root.right)
    end
end

-- গাছ তৈরি করা এবং মান ইনসার্ট করা
local root = Node.new(10)
insert(root, 5)
insert(root, 15)
insert(root, 3)
insert(root, 7)
insert(root, 12)
insert(root, 17)

-- গাছের মান ইনঅর্ডারে প্রিন্ট করা
inorderTraversal(root)  -- আউটপুট: 3 5 7 10 12 15 17

এখানে, আমরা একটি বাইনারি গাছ তৈরি করেছি এবং ইনঅর্ডার ট্র্যাভার্সাল ব্যবহার করে গাছের মধ্যে থাকা মানগুলো প্রিন্ট করেছি।

২. গ্রাফ (Graphs)

গ্রাফ (Graph) একটি গাছের মতো কিন্তু এটি সাইকেল (cycle) ধারণ করতে পারে, এবং প্রতিটি নোড (vertex) একাধিক সংযোগ (edge) দ্বারা অন্যান্য নোডের সাথে যুক্ত থাকতে পারে। গ্রাফে নোড এবং এজ (যে দুটি নোডের মধ্যে সম্পর্ক তৈরি করে) থাকে।

গ্রাফের উপাদান:

• নোড (Vertex): গ্রাফের একটি বিন্দু বা উপাদান।
• এজ (Edge): দুটি নোডের মধ্যে সম্পর্ক।
• ডিরেক্টেড গ্রাফ (Directed Graph): যেখানে এজের দিকে নির্দেশ থাকে।
• আনডিরেক্টেড গ্রাফ (Undirected Graph): যেখানে এজের কোন দিক নির্দেশিত থাকে না।

উদাহরণ: আনডিরেক্টেড গ্রাফ (Undirected Graph)

লুয়া ভাষায় গ্রাফের তৈরি এবং পরিচালনা করার জন্য আমরা একটি সিম্পল টেবিল ব্যবহার করতে পারি।

-- একটি গ্রাফ তৈরি করার জন্য টেবিল ব্যবহার
Graph = {}
Graph.__index = Graph

function Graph.new()
    local self = setmetatable({}, Graph)
    self.nodes = {}
    return self
end

-- গ্রাফে একটি নতুন নোড যোগ করার ফাংশন
function Graph:addNode(node)
    if not self.nodes[node] then
        self.nodes[node] = {}
    end
end

-- গ্রাফে দুটি নোডের মধ্যে একটি এজ যোগ করার ফাংশন
function Graph:addEdge(node1, node2)
    if not self.nodes[node1] then
        self:addNode(node1)
    end
    if not self.nodes[node2] then
        self:addNode(node2)
    end
    table.insert(self.nodes[node1], node2)
    table.insert(self.nodes[node2], node1)
end

-- গ্রাফ প্রিন্ট করার ফাংশন
function Graph:printGraph()
    for node, edges in pairs(self.nodes) do
        print(node .. " is connected to " .. table.concat(edges, ", "))
    end
end

-- গ্রাফ তৈরি এবং এজ যোগ করা
local g = Graph.new()
g:addNode("A")
g:addNode("B")
g:addNode("C")
g:addEdge("A", "B")
g:addEdge("A", "C")
g:addEdge("B", "C")

-- গ্রাফ প্রিন্ট করা
g:printGraph()
-- আউটপুট:
-- A is connected to B, C
-- B is connected to A, C
-- C is connected to A, B

এখানে, একটি আনডিরেক্টেড গ্রাফ তৈরি করা হয়েছে, যেখানে নোডগুলি পরস্পর সংযুক্ত রয়েছে। addEdge ফাংশনটি দুটি নোডের মধ্যে একটি সম্পর্ক তৈরি করে, এবং printGraph ফাংশনটি গ্রাফটি প্রিন্ট করে।

৩. গ্রাফের ট্র্যাভার্সাল (Graph Traversal)

গ্রাফের মধ্যে ভ্রমণ বা ট্র্যাভার্সাল দুটি প্রধান পদ্ধতিতে করা হয়:

1. ডেপথ-ফার্স্ট সার্চ (DFS): একটি নোডের গভীরে প্রবেশ করা এবং পরে পাশের নোডগুলো পরীক্ষা করা।
2. ব্রেডথ-ফার্স্ট সার্চ (BFS): নোডগুলির পাশের সব নোড একসাথে পরীক্ষা করা।

উদাহরণ: ডেপথ-ফার্স্ট সার্চ (DFS)

function dfs(graph, node, visited)
    if not visited[node] then
        print(node)
        visited[node] = true
        for _, neighbor in ipairs(graph.nodes[node]) do
            dfs(graph, neighbor, visited)
        end
    end
end

local g = Graph.new()
g:addNode("A")
g:addNode("B")
g:addNode("C")
g:addNode("D")
g:addEdge("A", "B")
g:addEdge("A", "C")
g:addEdge("B", "D")

-- DFS ট্র্যাভার্সাল
local visited = {}
dfs(g, "A", visited)
-- আউটপুট:
-- A
-- B
-- D
-- C

এখানে, dfs ফাংশনটি একটি গ্রাফে ডেপথ-ফার্স্ট সার্চের মাধ্যমে নোডগুলো পরিদর্শন করছে।

সারসংক্ষেপ

• গাছ (Tree): গাছ হল একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার যেখানে একটি রুট নোড এবং এর সাব-নোডগুলো থাকে। লুয়া টেবিল ব্যবহার করে গাছ তৈরি করা সহজ।
• গ্রাফ (Graph): গ্রাফ হল একটি জটিল ডেটা স্ট্রাকচার যেখানে নোডগুলো একে অপরের সাথে সংযুক্ত থাকে। গ্রাফ তৈরি এবং পরিচালনা করার জন্য টেবিল ব্যবহার করা হয়।
• গ্রাফ ট্র্যাভার্সাল: গ্রাফের মধ্যে ভ্রমণ করতে ডেপথ-ফার্স্ট এবং ব্রেডথ-ফার্স্ট সার্চ পদ্ধতি ব্যবহার করা হয়।

লুয়া ভাষায় গাছ এবং গ্রাফ নিয়ে কাজ করা সহজ এবং ফ্লেক্সিবল, যেহেতু টেবিলগুলি অত্যন্ত নমনীয় ডেটা স্ট্রাকচার।