একটি শুরুর বিন্দু থেকে যা যা reach করা যায়, সেগুলো ঘুরে দেখার দুটি উপায়।
মূল ধারণা (শহরে গুজব ছড়ানো, বা maze)
Graph হলো কিছু বিন্দু (node) আর তাদের জোড়া লাগানো রেখা (edge): শহর আর রাস্তা, মানুষ আর বন্ধুত্ব। এটা explore করতে দুটো জিনিস লাগে: যে node গুলো এখনো দেখা বাকি তার একটি to-do list, আর যেগুলো দেখে ফেলেছেন তার একটি note (যাতে একই জায়গায় ঘুরপাক না খান)।
BFS (breadth-first)queue ব্যবহার করে: first in, first out। এটা গুজবের মতো ছড়ায়: এক ধাপ দূরের সবাই আগে জানে, তারপর দুই ধাপ দূরের সবাই। তাই এটা shortest path (সবচেয়ে কম edge) খুঁজে পায়।
DFS (depth-first)stack ব্যবহার করে: last in, first out। এটা maze-এ হাঁটার মতো: একটা পথ ধরে যতদূর যাওয়া যায় যান, তারপর পিছিয়ে এসে পরের মোড়টা try করুন।
Code প্রায় একই। শুধু to-do list (queue না stack) বদলালে order বদলায়।
Run করে দেখুন
Node গুলোর নম্বর 0, 1, 2, ... এভাবে, মাঝে কোনো ফাঁক ছাড়া (সর্বোচ্চ 10টি node, 15টি edge)। Neighbor গুলো ছোট থেকে বড় order-এ visit হয়।
নিজে চেষ্টা করুন
একই graph-এ BFS আর DFS run করুন। দুটির visit order তুলনা করুন।
BFS node 0 থেকে শুরু করুন এবং খেয়াল করুন node 4-এ কখন পৌঁছায়। সেই level-ই 0 থেকে তার shortest distance।
যুক্ত নয় এমন node রাখুন, যেমন start 0 দিয়ে 0-1, 2-3। node 2 কি কখনো visit হয়?
visited set না রাখা। যেকোনো cycle-যুক্ত graph-এ আপনার program চিরকাল loop করবে।
BFS-এ visited mark করতে দেরি করা। Node-কে queue-তে add করার সময়ই mark করুন, নাহলে একই node বহুবার queue-তে ঢুকতে পারে।
slice-কে সবসময় queue হিসেবে ব্যবহার করা। practice-এর জন্য queue = queue[1:] ঠিক আছে। বিশাল input-এর ক্ষেত্রে মনে রাখুন এটা পুরনো backing array-কে memory-তে ধরে রাখে।
বিচ্ছিন্ন অংশ ভুলে যাওয়া। একটি search শুধু একটি connected অংশে পৌঁছায়। পুরো graph cover করতে প্রতিটি unvisited node থেকে নতুন search শুরু করুন।
Complexity, সহজ ভাষায়: প্রতিটি node একবার handle হয় আর প্রতিটি edge নির্দিষ্ট সংখ্যক বার দেখা হয়, তাই কাজ বাড়ে node আর edge-এর যোগফলের সাথে (O(V + E))। to-do list-এ সর্বোচ্চ সব node থাকতে পারে, তাই বাড়তি memory O(V)।