গাছ এবং গ্রাফের মধ্যে পার্থক্য
কন্টেন্ট
বৃক্ষ এবং গ্রাফ অ-লিনিয়ার ডেটা কাঠামোর ক্যাটাগরির অন্তর্গত হয় যেখানে বৃক্ষগুলি হায়ারারিকাল স্ট্রাকচারে নোডগুলির মধ্যে সম্পর্কের প্রতিনিধিত্ব করার একটি খুব কার্যকর উপায় সরবরাহ করে এবং গ্রাফ একটি নেটওয়ার্ক মডেল অনুসরণ করে। গাছ এবং গ্রাফটি পৃথক হয়ে যায় যে গাছের কাঠামো অবশ্যই সংযুক্ত থাকতে হবে এবং গ্রাফের মধ্যে এ জাতীয় কোনও বিধিনিষেধ নেই এমন সময় কখনও লুপ থাকতে পারে না।
একটি অ-রৈখিক ডেটা কাঠামো এমন একটি উপাদান রয়েছে যা একটি প্লেনে বিতরণ করা হয় যার অর্থ একটি লিনিয়ার ডেটা স্ট্রাকচারে বিদ্যমান উপাদানগুলির মধ্যে এই জাতীয় ক্রম নেই।
-
- তুলনা রেখাচিত্র
- সংজ্ঞা
- মূল পার্থক্য
- উপসংহার
তুলনা রেখাচিত্র
| তুলনার জন্য ভিত্তি | গাছ | চিত্রলেখ |
|---|---|---|
| পথ | দু'টি উল্লম্বের মধ্যে কেবল একটি। | একাধিক পথ অনুমোদিত। |
| রুট নোড | এটির ঠিক একটি মূল নোড রয়েছে। | গ্রাফের মূল নোড নেই। |
| loops | কোন লুপ অনুমোদিত নয়। | গ্রাফের লুপ থাকতে পারে। |
| জটিলতা | কম জটিল | তুলনামূলকভাবে আরও জটিল |
| ট্র্যাভারসাল কৌশল | প্রি অর্ডার, অর্ডার এবং পোস্ট-অর্ডার। | প্রথম প্রস্থে অনুসন্ধান এবং গভীরতা-প্রথম অনুসন্ধান। |
| প্রান্তের সংখ্যা | n-1 (যেখানে n নোডের সংখ্যা) | সংজ্ঞায়িত হয়নি |
| মডেল টাইপ | প্রধান পুরোহিত-সংক্রান্ত | নেটওয়ার্ক |
বৃক্ষ সংজ্ঞা
একজন গাছ সাধারণত নোড হিসাবে পরিচিত ডেটা আইটেমগুলির একটি সীমাবদ্ধ সংগ্রহ। যেমন উপরে উল্লিখিত রয়েছে যে একটি গাছ একটি অ-লিনিয়ার ডেটা কাঠামো যা সাজানো ক্রমে ডেটা আইটেমগুলি সাজায়। এটি বিভিন্ন ডেটা উপাদানগুলির মধ্যে একটি শ্রেণিবিন্যাসিক কাঠামো দেখানোর জন্য ব্যবহৃত হয় এবং তথ্যগুলি সম্পর্কিত যা শাখাগুলিতে ডেটা সংগঠিত করে। গাছের মধ্যে একটি নতুন প্রান্ত যুক্ত হওয়ার ফলে লুপ বা সার্কিট তৈরি হয়।
বিভিন্ন ধরণের গাছ রয়েছে যেমন বাইনারি ট্রি, বাইনারি সার্চ ট্রি, এভিএল ট্রি, থ্রেডেড বাইনারি ট্রি, বি-ট্রি ইত্যাদি। ডেটা সংক্ষেপণ, ফাইল স্টোরেজ, পাটিগণিতের অভিব্যক্তির হেরফের এবং গেম ট্রি গাছের প্রয়োগের কিছু অংশ are তথ্য কাঠামো.
গাছের বৈশিষ্ট্য:
- গাছের গোড়ায় গাছের মূল হিসাবে পরিচিত নোড রয়েছে।
- অবশিষ্ট ডেটা আইটেমগুলিকে বিচ্ছিন্ন সাবলেটগুলিতে বিভক্ত করা হয় সাবট্রি হিসাবে উল্লেখ করে।
- গাছটি নীচের দিকে উচ্চতায় প্রসারিত হয়।
- একটি গাছ অবশ্যই সংযুক্ত থাকতে হবে যার অর্থ একটি শিকড় থেকে অন্য সমস্ত নোডের দিকে যেতে হবে।
- এটিতে কোনও লুপ থাকে না।
- একটি গাছের এন -1 প্রান্ত রয়েছে।
টার্মিনাল নোড, প্রান্ত, স্তর, ডিগ্রি, গভীরতা, বন ইত্যাদির মতো গাছের সাথে সম্পর্কিত বিভিন্ন পদ রয়েছে। শর্তগুলির মধ্যে তাদের কয়েকটি নিচে বর্ণিত।
- প্রান্ত - একটি লাইন যা দুটি নোডকে সংযুক্ত করে।
- উচ্চতা - একটি গাছকে স্তরে এমনভাবে বিভক্ত করা হয় যে মূলের নোডটি স্তরে থাকে Then তারপরে, এর তাত্ক্ষণিক শিশুরা 1 স্তরে থাকে এবং এর আশেপাশের শিশুরা স্তর 2 এবং তাই টার্মিনাল বা পাতার নোড পর্যন্ত থাকে।
- ডিগ্রী - এটি প্রদত্ত গাছে নোডের সাবট্রির সংখ্যা।
- গভীরতা - এটি প্রদত্ত গাছে যে কোনও নোডের সর্বাধিক স্তর এবং এটি হিসাবে পরিচিত উচ্চতা.
- টার্মিনাল নোড - সর্বোচ্চ স্তরের নোড হ'ল টার্মিনাল নোড, টার্মিনাল এবং রুট নোড ব্যতীত অন্যান্য নোডগুলি নন-টার্মিনাল নোড হিসাবে পরিচিত।
গ্রাফ সংজ্ঞা
একজন চিত্রলেখ এটি একটি গাণিতিক অ-রৈখিক ডেটা কাঠামো যা বিভিন্ন ধরণের শারীরিক কাঠামোর প্রতিনিধিত্ব করতে পারে। এটি শীর্ষে (বা নোড) এবং দুটি প্রান্তকে সংযোগকারী প্রান্তগুলির একটি গ্রুপ নিয়ে গঠিত। গ্রাফের শীর্ষাংশগুলি বিন্দু বা চেনাশোনা হিসাবে উপস্থাপিত হয় এবং প্রান্তগুলি আর্ক বা লাইন বিভাগ হিসাবে দেখানো হয়। একটি প্রান্তটি ই (ভ, ডাব্লু) দ্বারা প্রতিনিধিত্ব করা হয় যেখানে ভ এবং ডব্লম্ব শীর্ষে অবস্থিত। একটি সার্কিট বা সংযুক্ত গ্রাফ থেকে একটি প্রান্ত অপসারণ একটি উপগ্রাফ তৈরি করে যা একটি গাছ।
গ্রাফগুলি বিভিন্ন বিভাগে যেমন শ্রেণিবদ্ধ করা হয়েছে যেমন নির্দেশিত, অ-নির্দেশিত, সংযুক্ত, নন-সংযুক্ত, সহজ এবং বহু-গ্রাফ। কম্পিউটার নেটওয়ার্ক, পরিবহন ব্যবস্থা, সোশ্যাল নেটওয়ার্ক গ্রাফ, বৈদ্যুতিক সার্কিট এবং প্রকল্প পরিকল্পনা গ্রাফ ডেটা স্ট্রাকচারের কয়েকটি প্রয়োগ। এটি হিসাবে হিসাবে পরিচালিত কৌশল কৌশল নিযুক্ত করা হয় অকালপক্ক (প্রোগ্রাম মূল্যায়ন এবং পর্যালোচনা কৌশল) এবং সিপিএম (সমালোচনামূলক পাথ পদ্ধতি) যা গ্রাফ কাঠামো বিশ্লেষণ করা হয়।
একটি গ্রাফের বৈশিষ্ট্য:
- কোনও গ্রাফের একটি শীর্ষবিন্দুটি প্রান্তগুলি ব্যবহার করে যে কোনও সংখ্যক উল্লম্বের সাথে সংযুক্ত হতে পারে।
- একটি প্রান্তটি দিশা বা নির্দেশিত হতে পারে।
- একটি প্রান্ত ওজন করা যেতে পারে।
গ্রাফেও আমরা বিভিন্ন পদ ব্যবহার করি যেমন সংলগ্ন প্রান্ত, পথ, চক্র, ডিগ্রি, সংযুক্ত গ্রাফ, সম্পূর্ণ গ্রাফ, ওজনযুক্ত গ্রাফ ইত্যাদি Let
- সংলগ্ন কোণ - প্রান্ত (ক, খ) বা (খ, ক) থাকলে ভার্টেক্স এ সংলগ্ন।
- পথ - একটি এলোমেলোভাবে ভার্টেক্স ডাব্লু থেকে একটি পথটি শীর্ষ সূর্যের একটি সংলগ্ন ক্রম।
- চক্র - এটি এমন একটি পথ যেখানে প্রথম এবং শেষ প্রান্তটি একই।
- ডিগ্রী - এটি একটি শীর্ষে বহু প্রান্তের ঘটনা।
- সংযুক্ত গ্রাফ - যদি কোনও এলোমেলো প্রান্ত থেকে অন্য কোনও শীর্ষবিন্দুর কোনও পথ উপস্থিত থাকে তবে সেই গ্রাফটি সংযুক্ত গ্রাফ হিসাবে পরিচিত।
- একটি গাছে উভয় উল্লম্বের মধ্যে কেবল একটিই পথ থাকে যখন গ্রাফের নোডগুলির মধ্যে দ্বি-নির্দেশমূলক এবং দ্বি-নির্দেশমূলক পথ থাকতে পারে।
- গাছটিতে ঠিক একটি মূল নোড রয়েছে এবং প্রতিটি সন্তানের একমাত্র পিতা বা মাতা থাকতে পারে। বিপরীতে, গ্রাফের মধ্যে, মূল নোডের কোনও ধারণা নেই।
- একটি গাছে লুপ এবং স্ব-লুপ থাকতে পারে না যখন গ্রাফে লুপ এবং স্ব-লুপ থাকতে পারে।
- গ্রাফগুলি আরও জটিল কারণ এতে লুপ এবং স্ব-লুপ থাকতে পারে। বিপরীতে, গাছগুলি গ্রাফের তুলনায় সহজ।
- প্রি অর্ডার, ইন-অর্ডার এবং পোস্ট-অর্ডার কৌশলগুলি ব্যবহার করে গাছটি আড়াআড়ি হয়। অন্যদিকে, গ্রাফ ট্র্যাভারসালের জন্য, আমরা বিএফএস (ব্রেথথ ফার্স্ট সন্ধান) এবং ডিএফএস (গভীরতা প্রথম অনুসন্ধান) ব্যবহার করি।
- একটি গাছে এন -1 প্রান্ত থাকতে পারে। বিপরীতে, গ্রাফে, প্রান্তগুলির পূর্বনির্ধারিত সংখ্যা নেই এবং এটি গ্রাফের উপর নির্ভর করে।
- একটি গাছে একটি শ্রেণিবিন্যাসিক কাঠামো থাকে যেখানে গ্রাফের একটি নেটওয়ার্ক মডেল থাকে।
উপসংহার
গ্রাফ এবং ট্রি হ'ল অ-লিনিয়ার ডেটা স্ট্রাকচার যা বিভিন্ন জটিল সমস্যা সমাধানে ব্যবহৃত হয়। একটি গ্রাফটি শীর্ষে এবং প্রান্তের একটি গ্রুপ যেখানে একটি প্রান্তটি একজোড়া কোণকে সংযুক্ত করে যেখানে একটি গাছকে ন্যূনতম সংযুক্ত গ্রাফ হিসাবে বিবেচনা করা হয় যা অবশ্যই সংযুক্ত এবং লুপগুলি থেকে মুক্ত থাকতে হবে।
