DFS একটি গ্রাফকে প্রতিটি শাখায় যতদূর সম্ভব গভীরে যেয়ে অন্বেষণ করে, তারপর ফিরে আসে। এটি একটি stack ব্যবহার করে (প্রায়ই রিকার্শনের মাধ্যমে কল স্ট্যাক) এবং বিকল্পগুলি অন্বেষণ করার আগে একটি সম্পূর্ণ পথ পরিদর্শন করে।
ধারণা
একটি নোড থেকে, একটি অপরিদর্শিত প্রতিবেশীতে রিকার্স করুন এবং গভীরভাবে যান; যখন আটকে যান, ফিরে আসুন এবং অন্য একটি শাখা চেষ্টা করুন।
উদাহরণ
python
():
visited :
visited = ()
visited.add(node)
order = [node]
nbr graph[node]:
nbr visited:
order += dfs(graph, nbr, visited)
order
graph = {: [, ], : [], : [], : []}
dfs(graph, )