গ্রাফ বনাম গাছ
গ্রাফ এবং ট্রি ডেটা স্ট্রাকচারে ব্যবহার করা হয়। গ্রাফ এবং গাছের মধ্যে অবশ্যই কিছু পার্থক্য রয়েছে। বাইনারি সম্পর্কযুক্ত শীর্ষবিন্দুগুলির একটি সেটকে গ্রাফ বলা হয় যেখানে ট্রি হল একটি ডেটা স্ট্রাকচার যেখানে একে অপরের সাথে সংযুক্ত নোডের সেট রয়েছে।
গ্রাফ
একটি গ্রাফ হল আইটেমগুলির একটি সেট যা কিনারা দ্বারা সংযুক্ত এবং প্রতিটি আইটেম নোড বা শীর্ষবিন্দু হিসাবে পরিচিত। অন্য কথায়, একটি গ্রাফকে শীর্ষবিন্দুর সেট হিসাবে সংজ্ঞায়িত করা যেতে পারে এবং এই শীর্ষবিন্দুগুলির মধ্যে একটি বাইনারি সম্পর্ক রয়েছে।
একটি গ্রাফ বাস্তবায়নে, নোডগুলি বস্তু বা কাঠামো হিসাবে প্রয়োগ করা হয়। প্রান্তগুলি বিভিন্ন উপায়ে উপস্থাপন করা যেতে পারে।একটি উপায় হল প্রতিটি নোড একটি ঘটনা প্রান্ত অ্যারের সাথে যুক্ত করা যেতে পারে। যদি তথ্যটি প্রান্তের পরিবর্তে নোডগুলিতে সংরক্ষণ করতে হয় তবে অ্যারেগুলি নোডের পয়েন্টার হিসাবে কাজ করে এবং প্রান্তগুলিকেও উপস্থাপন করে। এই পদ্ধতির একটি সুবিধা হল গ্রাফে অতিরিক্ত নোড যোগ করা যায়। বিদ্যমান নোডগুলি অ্যারেতে উপাদান যুক্ত করে সংযুক্ত করা যেতে পারে। তবে একটি অসুবিধা রয়েছে কারণ নোডগুলির মধ্যে একটি প্রান্ত আছে কিনা তা নির্ধারণ করার জন্য সময় প্রয়োজন৷
এটি করার অন্য উপায় হল একটি দ্বিমাত্রিক অ্যারে বা ম্যাট্রিক্স M রাখা যাতে বুলিয়ান মান রয়েছে। নোড i থেকে j পর্যন্ত প্রান্তের অস্তিত্ব এন্ট্রি Mij দ্বারা নির্দিষ্ট করা হয়। এই পদ্ধতির একটি সুবিধা হল দুটি নোডের মধ্যে কোন প্রান্ত আছে কিনা তা খুঁজে বের করা।
গাছ
গাছ কম্পিউটার বিজ্ঞানে ব্যবহৃত একটি ডেটা কাঠামোও। এটি গাছের গঠনের অনুরূপ এবং একে অপরের সাথে সংযুক্ত নোডের একটি সেট রয়েছে৷
একটি গাছের একটি নোডে একটি শর্ত বা মান থাকতে পারে।এটি নিজস্ব একটি গাছও হতে পারে বা এটি একটি পৃথক ডেটা কাঠামো উপস্থাপন করতে পারে। একটি ট্রি ডেটা স্ট্রাকচারে শূন্য বা তার বেশি নোড থাকে। যদি একটি নোডের একটি শিশু থাকে তবে তাকে সেই সন্তানের প্যারেন্ট নোড বলা হয়। একটি নোডের সর্বাধিক একজন অভিভাবক থাকতে পারে। নোড থেকে পাতা পর্যন্ত দীর্ঘতম নিম্নগামী পথ হল নোডের উচ্চতা। নোডের গভীরতা তার মূলের পথ দ্বারা উপস্থাপিত হয়।
একটি গাছে, উপরের নোডটিকে রুট নোড বলে। রুট নোডের কোনো পিতা-মাতা নেই কারণ এটি শীর্ষস্থানীয়। এই নোড থেকে, সমস্ত গাছ অপারেশন শুরু হয়। লিঙ্ক বা প্রান্ত ব্যবহার করে, রুট নোড থেকে অন্যান্য নোডগুলিতে পৌঁছানো যায়। নীচের সবচেয়ে স্তরের নোডগুলিকে লিফ নোড বলা হয় এবং তাদের কোনও সন্তান নেই। যে নোডটিতে চাইল্ড নোডের সংখ্যা রয়েছে তাকে ইনার নোড বা অভ্যন্তরীণ নোড বলা হয়।
গ্রাফ এবং গাছের মধ্যে পার্থক্য:
• একটি গাছকে গ্রাফের একটি বিশেষ কেস হিসাবে বর্ণনা করা যেতে পারে যার কোনো সেলফ লুপ এবং সার্কিট নেই৷
• একটি গাছে কোনো লুপ নেই যেখানে একটি গ্রাফে লুপ থাকতে পারে৷
• একটি গ্রাফে তিনটি সেট রয়েছে যেমন প্রান্ত, শীর্ষবিন্দু এবং একটি সেট যা তাদের সম্পর্ককে উপস্থাপন করে যখন একটি গাছ একে অপরের সাথে সংযুক্ত নোড নিয়ে গঠিত। এই সংযোগগুলিকে প্রান্ত হিসাবে উল্লেখ করা হয়৷
• গাছে নোডের সংযোগ কীভাবে ঘটতে পারে তা বানান করে অনেক নিয়ম রয়েছে যেখানে গ্রাফে নোডগুলির মধ্যে সংযোগ নির্দেশ করার কোনও নিয়ম নেই৷
