মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
ব্রেথ-ফার্স্ট সার্চ বিশ্লেষণ
ভার্টেক্স সেট এবং এজ সেট সহ একটি লেখচিত্র খুঁজতে, ব্রেথ-ফার্স্ট সার্চের কত সময় লাগবে? উত্তর হল, সময় লাগবে।
(এখান লক্ষ্য করলে দেখা যাবে যে, এখানে একটি লেখচিত্র সংযুক্ত থাকবে যদি প্রতিটি শীর্ষবিন্দু থেকে অন্যান্য যে উলম্বগুলো আছে তার প্রতিটিতে একটি করে পথ থাকে। একটি গ্রাফের সর্বনিম্ন যতসংখ্যক মান থাকতে পারবে এবং যতসংখ্যকবার সংযুক্ত থাকতে পারে সেটা হল । একটি লেখচিত্র যেখানে আর এটাকে বলা হয় একটি free tree।)
null
এবং তাই প্রতিটি শীর্ষবিন্দু সর্বোচ্চ একবার সারি আকারে থাকছে। যেহেতু যখন আমরা এই শীর্ষবিন্দু থেকে চলে আসছি শুধুমাত্র তখনই শীর্ষবিন্দুগুলো পরীক্ষা করে দেখছি তাই প্রতিটি প্রান্তবিন্দু সর্বোচ্চ দুইবার আমরা পরীক্ষা করে দেখতে পারব, যে শীর্ষবিন্দুগুলোতে এই ঘটনাগুলো আছে তার প্রতিটির জন্য একবার করে। সুতরাং, ব্রেডথ-ফার্স্ট সার্চ শীর্ষবিন্দু খুঁজে বের করতে এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।