খুব সংক্ষেপে গ্রাফের সংজ্ঞা দিতে গেলে আমরা বলতে পারি, গ্রাফ হচ্ছে একটি non-linear data structure. এখন আমাদের মনে প্রশ্ন আসতে পারে যে non-linear data structure বলতে আমরা কি বুঝি। প্রথমত, data structure হল একই data type এর এক বা একাধিক data element এর সমষ্টি। যেমনঃ array, stack, queue etc. এখন linear বা non-linear data structure কি - এই ব্যাপারটিতে আসা যাক। Linear data structure বলতে আমরা সেই সকল data structure কে বুঝি, যাদের element গুলোকে আমরা কোন linear order এ traverse বা access করতে পারি। যেমন, কোন array এর element গুলোকে আমরা index 0 থেকে শুরু করে পরপর শেষ পর্যন্ত traverse করতে পারি। তাই এটি একটি linear data structure. আবার stack এর ক্ষেত্রে আমরা এর top থেকে element গুলো একটির পর একটি access করতে পারি। তাই এটিও একটি linear data structure. বিপরীতভাবে, যেসকল data structure এর element গুলো আমরা কোন linear order এ access করতে পারি না তাদেরকে non-linear data structure বলে। এদের data element গুলোকে access করার জন্য বিভিন্ন রকমের traversal algorithm আছে। যেমন, গ্রাফ traversal algorithm হিসেবে আছে BFS (Breadth First Search), DFS (Depth First Search) ইত্যাদি।
এখন আসা যাক গ্রাফে data element গুলো কিভাবে সাজানো থাকে - সে বিষয়ে। গ্রাফের দুটি প্রধান বৈশিষ্ট্য হচ্ছে node এবং edge. প্রয়োজনমত আমরা node এবং edge উভয়ের মধ্যেই data রাখতে পারি। সাধারণত আমরা node কে বৃত্ত এবং edge কে রেখাংশ দিয়ে উপস্থাপন করে থাকি।
সহজে চিহ্নিত করার জন্য কোন গ্রাফের node গুলোকে আমরা 1,2,3,…,n ক্রমিক সংখ্যাগুলো দিয়ে সূচিত করতে পারি। দুটি node এর মধ্যে edge থাকার অর্থ হচ্ছে আমরা একটি node থেকে অপরটিতে যেতে পারি। এভাবে একটি মাত্র edge ব্যবহার করে যদি আমরা একটি node থেকে অপরটিতে যেতে পারি, তবে এরা পরস্পরের adjacent node হবে। অবশ্য যদি edge এ direction দেওয়া থাকে তবে আমরা destination node কে source node এর adjacent node বলবো। উদাহরণস্বরূপ, চিত্র-১ এ আমরা দুটি গ্রাফ দেখতে পাচ্ছি। গ্রাফ-১ এ node-1 এর adjacent node ২টি - node-2 এবং node-3. আবার গ্রাফ-২ এ node-1 এর adjacent node ১টি - শুধু node-2.
গ্রাফ- ১ গ্রাফ-২
চিত্র-১
Path: যদি কোন source node থেকে কয়েকটি edge ব্যবহার করে কোন destination node এ যেতে হয়, তবে যাওয়ার সময় visited node গুলোর sequence কে path বলে। যেমন, চিত্র-১ এর গ্রাফ-১ এ node-2 থেকে node-3 যাওয়ার path হচ্ছে 2,1,3. আবার চিত্র-১ এর গ্রাফ-১ এ node-2 থেকে node-3 যাওয়ার কোন path নেই। গ্রাফে দুটি node এর মধ্যে একাধিক path ও থাকতে পারে। উদাহরণস্বরুপ চিত্র-২ এর গ্রাফ-১ এ node-2 থেকে একটি edge ব্যবহার করে node-3 তে যাওয়া যায়, আবার দুটি edge ব্যবহার করে node-1 হয়েও যাওয়া যায়।
গ্রাফ- ১ গ্রাফ-২
চিত্র-২
Cycle: গ্রাফে cycle হচ্ছে এমন একটি path যেখানে প্রথম এবং শেষ node টি একই হবে, আর বাকি node গুলো একবার করে থাকে। যেমন চিত্র-২ এর গ্রাফ-১ এ node-1 থেকে যাত্রা শুরু করে node-2, node-3 হয়ে আমরা পুনরায় node-1 এ ফিরে আসতে পারি। তাই এখানে 1,2,3,1 একটি cycle. আবার চিত্র-২ এর গ্রাফ-২ এ আমরা কোন node থেকে যাত্রা শুরু করে cycle এর শর্ত মেনে পুনরায় ওই node এ ফিরে আসতে পারব না। তাই এই গ্রাফে কোন cycle নেই।
Self-loop: যদি গ্রাফে কোন node নিজের সাথে একটি edge দিয়ে যুক্ত হয়, তবে ওই edge আমরা self-loop বলে থাকি। যেমন, চিত্র-৩ এর গ্রাফে node-1 নিজের সাথে একটি self-loop দিয়ে যুক্ত আছে।
চিত্র-৩
লিখতে গিয়ে আমার মনে একটা প্রশ্ন জেগে উঠলো, “Self-loop কে আমরা cycle বলতে পারি কি?” প্রশ্নটির উত্তর দেওয়ার আগে আমি আমার প্রিয় পাঠককে বলব, আপনি একটু ভেবে দেখুন তো আপনার কি মনে হয়। আগে থেকে নিজের মনে একটা উত্তর আর সেই উত্তরের স্বপক্ষে যুক্তি ভেবে রাখুন এবং এরপর অগ্রসর হয়ে আপনার উত্তরের সাথে আমার খুঁজে বের করা উত্তরটি মিলিয়ে নিন।
এই প্রশ্নের উত্তর খুঁজতে হলে আমাদের ফিরে যেতে হবে Cycle এর সংজ্ঞায়। সেখানে বলা আছে cycle এর প্রথম node আর শেষ node একই হবে। এখন self-loop ব্যবহার করে আমরা যখন একটি node থেকে আবার ওই node এ যাই, তখন আমাদের path এর প্রথম node আর শেষ node একই তো থাকে, তাই না? যদি তাই হয় তবে আমরা তো বলতেই পারি যে self-loop ও একটি cycle যার length 1.
Multiple edges বা Parallel edges: গ্রাফে একটি node থেকে তার adjacent কোন node এ যাওয়ার জন্য একাধিক edge থাকতে পারে। এই ব্যাপারটি multiple edges বা parallel edges বলে। যেমন, চিত্র-৪ এর গ্রাফে node-1 আর node-2 এর মধ্যে ৩টি edge আছে। এটি parallel edges এর একটি উদাহরণ।
চিত্র-৪
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন