গ্রাফপড়তে ৫ মিনিট লাগবে

ডেপথ-ফার্স্ট সার্চ (Depth-First Search - DFS)

পেছনে ফেরার আগে একটা রাস্তা ধরে যত দূর যানয়া যায় তত দূর যান

time: O(V+E)space: O(V)

ধরুন আপনি নতুন একটা শহরে ঘুরতে বের হয়েছেন। আপনার স্টাইল হলো: যেকোনো একটা রাস্তা বেছে নিয়ে হাঁটতে শুরু করা এবং একেবারে শেষ মাথায় না পৌঁছানো পর্যন্ত ওই রাস্তা ধরেই আগানো। রাস্তা শেষ হয়ে গেলে অর্থাৎ ডেড-এন্ডে পৌঁছালে, আপনি সেখান থেকে পেছনে ফিরে এসে অন্য কোনো রাস্তা ট্রাই করেন। অন্য কোনো অপশন ট্রাই করার আগে আপনি একটা রাস্তায় পুরোপুরি মনপ্রাণ ঢেলে দেন। এই স্টাইলটাকেই বলা হয় ডেপথ-ফার্স্ট সার্চ (Depth-First Search বা DFS)।

BFS যেমন একটু একটু করে চারদিকে গোল হয়ে ছড়ায়, DFS তার উল্টো—সে যতটা সম্ভব গভীরে বা দূরে চলে যায়। আর যখন যানয়ার মতো নতুন কোনো শহর বা প্রতিবেশী বাকি থাকে না, তখন সে ব্যাকট্র্যাক (Backtrack) করে বা পেছনে ফিরে আসে।

স্ট্যাক (Stack) বা রিকার্শন (Recursion)

DFS করার জন্য স্ট্যাক (Stack) লাগে — সেটা আপনি কোডে নিজে বানিয়ে নিতে পারেন, অথবা ফাংশনের নিজস্ব কল স্ট্যাক (রিকার্শন) ব্যবহার করতে পারেন। কোনো নতুন শহর পেলেই সেটা স্ট্যাকে ঢোকানো (Push) হয়, আর ওই শহরের সব কাজ শেষ হয়ে গেলে স্ট্যাক থেকে বের (Pop) করে দেওয়া হয়। রিকার্শন বা ফাংশনের ভেতরে একই ফাংশনকে ডাকা হলো DFS লেখার সবচেয়ে দারুণ আর স্বাভাবিক উপায়:

pseudocode

function dfs(graph, city, visited = new Set()):
  visited.add(city)
  process(city)

  for neighbor of graph[city]:
    if neighbor not in visited:
      dfs(graph, neighbor, visited)

আর যদি রিকার্শনের কারণে মেমোরি ফুল (Stack Overflow) হয়ে যানয়ার ভয় থাকে, তখন রিকার্শন বাদ দিয়ে নিজে একটা লুপ আর স্ট্যাক ডেটা স্ট্রাকচার বানিয়ে এটা করা হয়।

কানেক্টেড কম্পোনেন্ট (Connected components) খোঁজা

একটা ম্যাপে এমন কিছু বিচ্ছিন্ন আইল্যান্ড বা দ্বীপ থাকতে পারে, যেগুলোর সাথে বাইরের কোনো শহরের রাস্তাই নেই। এই অবস্থায় আপনি ভিজিট না করা যেকোনো একটা শহর থেকে DFS শুরু করুন: ওই যাত্রায় আপনি যতগুলো শহরে পৌঁছাতে পারবেন, তারা সবাই মিলে একটা কানেক্টেড কম্পোনেন্ট (Connected component) তৈরি করবে (এই কম্পোনেন্ট ট্র্যাকিংয়ের কাজটা ইউনিয়ন-ফাইন্ড (Union-Find) দিয়েও করা যায়)। ওই DFS শেষ হওয়ার পর, এখনো যানয়া হয়নি এমন আরেকটা শহর পিক করে নতুন করে আবার DFS শুরু করুন। এভাবে কয়বার আপনাকে নতুন করে DFS শুরু করতে হলো, তা গুনলেই পেয়ে যাবেন আপনার ম্যাপে কয়টা আলাদা আইল্যান্ড বা কম্পোনেন্ট আছে।

সাইকেল বা চক্কর (Cycle) আছে কি না চেক করা

DFS চলার সময় যদি আপনি এমন কোনো প্রতিবেশীর দেখা পান যাকে আগেই ভিজিট করা হয়েছে (এবং সে আপনার ডিরেক্ট প্যারেন্ট বা ঠিক পেছনের জন নয়), তার মানে আপনি একটা সাইকেল (Cycle) খুঁজে পেয়েছেন — অর্থাৎ ম্যাপের ভেতরে এমন একটা রাস্তা আছে যা ঘুরেফিরে আবার আগের জায়গায় নিয়ে আসে। ডেডলক চেক করা বা DAG (Directed Acyclic Graph) ভ্যালিডেট করার জন্য এটা জানা খুব জরুরি।

pseudocode

// ডিরেক্টেড গ্রাফের ক্ষেত্রে তিনটা অবস্থা বা রং মনে রাখুন:
// WHITE = এখনো যাইনি, GRAY = এখন ওই রাস্তাতেই আছি, BLACK = কাজ শেষ
function hasCycle(graph, city, color):
  color[city] = GRAY
  for neighbor of graph[city]:
    if color[neighbor] === GRAY: return true  // ব্যাক-এজ মানেই চক্কর বা সাইকেল!
    if color[neighbor] === WHITE:
      if hasCycle(graph, neighbor, color): return true
  color[city] = BLACK
  return false

◈ Watch DFS explore

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

দ্রষ্টব্য: মনে রাখবেন, DFS কিন্তু আপনাকে সবচেয়ে ছোট রাস্তা বা শর্টেস্ট রুট খুঁজে দেওয়ার কোনো গ্যারান্টি দেয় না (সেটা BFS-এর কাজ)। DFS-এর আসল ক্ষমতা হলো ম্যাপের খুঁটিনাটি বের করে আনা: যেমন কানেক্টেড কম্পোনেন্ট বের করা, সাইকেল চেক করা, টপোলজিক্যাল সর্টিং করা অথবা গোলকধাঁধা (Maze) সলভ করা।