ব্রেথ-ফার্স্ট সার্চ বিশ্লেষণ

ভার্টেক্স সেট $V$‍ এবং এজ সেট $E$‍ সহ একটি লেখচিত্র খুঁজতে, ব্রেথ-ফার্স্ট সার্চের কত সময় লাগবে? উত্তর হল, $O(V+E)$‍ সময় লাগবে।

$O(V+E)$‍ সময় অর্থ কি, তা এখন দেখা যাক। এখন, এই মুহূর্তের জন্য মনে করা যাক যে $|E|\ge |V|$‍, বেশিরভাগ লেখচিত্রের ক্ষেত্রেই এটি প্রযোজ্য, বিশেষ ভাবে যে লেখচিত্রের জন্য আমরা ব্রেথ-ফার্স্ট সার্চ ব্যবহার করব। তাহলে, $|V|+|E|\le |E|+|E|=2\cdot |E|$‍। কারণ আমরা অ্যাসিম্পটটিক নোটেশনে (asymptotic notation) ধ্রুবক গুণনীয়কগুলোকে উহ্য করি, সেকারণে আমরা যখন $|E|\ge |V|$‍, $O(V+E)$‍ দেখি, আসলে এটির অর্থ দাড়ায় $O(E)$‍। এখন যদি আমাদের কাছে $|E|<|V|$‍ থাকে, তাহলে $|V|+|E|\le |V|+|V|=2\cdot |V|$‍ এবং এটির $O(V+E)$‍ মুলত অর্থ দাড়ায় $O(V)$‍। আমরা উভকেই এভাবে বলতে পারি যে, $O(V+E)$‍ এটি আসলে এই $O(max(V,E))$‍ অর্থটি প্রকাশ করে। সাধারনভাবে বলতে গেলে, আমাদের কাছে যদি $x$‍ এবং $y$‍ এর প্যারামিটার থাকে, তাহলে এই $O(x+y)$‍ এর অর্থ দাঁড়াবে $O(max(x,y))$‍।

(এখান লক্ষ্য করলে দেখা যাবে যে, এখানে একটি লেখচিত্র সংযুক্ত থাকবে যদি প্রতিটি শীর্ষবিন্দু থেকে অন্যান্য যে উলম্বগুলো আছে তার প্রতিটিতে একটি করে পথ থাকে। একটি গ্রাফের সর্বনিম্ন যতসংখ্যক মান থাকতে পারবে এবং যতসংখ্যকবার সংযুক্ত থাকতে পারে সেটা হল $|V|-1$‍। একটি লেখচিত্র যেখানে $|E|=|V|-1$‍ আর এটাকে বলা হয় একটি free tree।)

$O(V+E)$‍ সময়ে ব্রেডথ-ফার্স্ট সার্চ কীভাবে রান করে? এখানে প্রতিটি শীর্ষবিন্দুর দূরত্ব রান করানোর জন্য $O(V)$‍ সময় প্রয়োজন হয় ($\mathrm{\Theta }(V)$‍ সময়)। প্রতিটি শীর্ষবিন্দুতে সর্বোচ্চ একবার যাওয়া হবে, কারণ শুধুমাত্র প্রথমবারই এটা এর দূরত্বে পৌঁছাচ্ছে যেটা হল null এবং তাই প্রতিটি শীর্ষবিন্দু সর্বোচ্চ একবার সারি আকারে থাকছে। যেহেতু যখন আমরা এই শীর্ষবিন্দু থেকে চলে আসছি শুধুমাত্র তখনই শীর্ষবিন্দুগুলো পরীক্ষা করে দেখছি তাই প্রতিটি প্রান্তবিন্দু সর্বোচ্চ দুইবার আমরা পরীক্ষা করে দেখতে পারব, যে শীর্ষবিন্দুগুলোতে এই ঘটনাগুলো আছে তার প্রতিটির জন্য একবার করে। সুতরাং, ব্রেডথ-ফার্স্ট সার্চ শীর্ষবিন্দু খুঁজে বের করতে $O(V+E)$‍ সময় ব্যয় করবে।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।