Graph: BFS and DFS

একটি শুরুর বিন্দু থেকে যা যা reach করা যায়, সেগুলো ঘুরে দেখার দুটি উপায়।

মূল ধারণা (শহরে গুজব ছড়ানো, বা maze)

Graph হলো কিছু বিন্দু (node) আর তাদের জোড়া লাগানো রেখা (edge): শহর আর রাস্তা, মানুষ আর বন্ধুত্ব। এটা explore করতে দুটো জিনিস লাগে: যে node গুলো এখনো দেখা বাকি তার একটি to-do list, আর যেগুলো দেখে ফেলেছেন তার একটি note (যাতে একই জায়গায় ঘুরপাক না খান)।

Code প্রায় একই। শুধু to-do list (queue না stack) বদলালে order বদলায়।

Run করে দেখুন

Node গুলোর নম্বর 0, 1, 2, ... এভাবে, মাঝে কোনো ফাঁক ছাড়া (সর্বোচ্চ 10টি node, 15টি edge)। Neighbor গুলো ছোট থেকে বড় order-এ visit হয়।

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: প্রতিটি node একবার handle হয় আর প্রতিটি edge নির্দিষ্ট সংখ্যক বার দেখা হয়, তাই কাজ বাড়ে node আর edge-এর যোগফলের সাথে (O(V + E))। to-do list-এ সর্বোচ্চ সব node থাকতে পারে, তাই বাড়তি memory O(V)।