Chapterبەش 4 · Lectureوانە 4.2
Depth-First and Breadth-First Searchگەڕانی قووڵایی و گەڕانی پانایی
Breadth-first search (a queue) and depth-first search (a stack): how they work, their strengths and weaknesses, the frontier and explored list worked by hand, the Lab 1 Python code, and the difference between a search and a traversal.
() و (): چۆن کار دەکەن، خاڵە بەهێز و لاوازەکانیان، و بە دەست، کۆدی تاقیگەی 1 و جیاوازیی نێوان گەڕان و .
What you will learnچی فێر دەبیت
- Explain that BFS and DFS share one loop and differ only in the frontier: queue or stack.
- Trace BFS and DFS on a tree by hand, with a frontier and an explored list.
- State the completeness, optimality, time and space of BFS and DFS.
- Read, run and change the Lab 1 Python code, and switch it between DFS, BFS and traversal.
- ڕوونی بکەیتەوە کە BFS و DFS یەک خولیان هاوبەشە و تەنها لە جیاوازن: یان .
- BFS و DFS بە دەست لەسەر پەیڕەو بکەیت، لەگەڵ و .
- ، ، کات و BFS و DFS بڵێیت.
- کۆدی تاقیگەی 1 بخوێنیتەوە، جێبەجێی بکەیت و بیگۆڕیت و لە نێوان DFS، BFS و بیگۆڕیتەوە.
One loop, two ordersیەک خول، دوو ڕیزبەندی
In Search problems you met the general search loop: take a node out of the , test it, expand it, repeat. Breadth-first search (BFS) and depth-first search (DFS) both run this loop. They differ in only one thing: which node they take out of the frontier.
لە کێشەکانی گەڕان خولی گشتیی گەڕانت ناسی: لە دەربهێنە، تاقیی بکەرەوە، فراوانی بکە، دووبارەی بکەرەوە. (BFS) و (DFS) هەردووکیان ئەم خولە جێبەجێ دەکەن. تەنها لە یەک شتدا جیاوازن: کام لە دەردەهێنن.
| Aspectلایەن | BFS | DFS |
|---|---|---|
| Frontier is a… بریتییە لە… | — first in, first out (FIFO) — یەکەم هاتوو، یەکەم دەرچوو (FIFO) | — last in, first out (LIFO) — دوایین هاتوو، یەکەم دەرچوو (LIFO) |
| Takes out the…دەریدەهێنێت… | oldest nodeکۆنترین | newest nodeنوێترین |
| Everyday pictureوێنەیەکی ڕۆژانە | People in line at a bakery: the first to arrive is served first.خەڵک لە ڕیزی نانەواخانەدا: ئەوەی یەکەم جار گەیشتووە یەکەم جار نانی پێ دەدرێت. | A pile of plates: you take the plate you put on top last.کۆمەڵێک قاپ کە لەسەر یەک دانراون: ئەو قاپە هەڵدەگریت کە دوایین جار لەسەرەوە داتناوە. |
Breadth-first searchگەڕانی پانایی
An uninformed search that expands all nodes at one depth before going deeper, using a FIFO queue for the frontier. It finds the path with the fewest steps.
کە هەموو نۆدەکانی یەک قووڵایی فراوان دەکات پێش ئەوەی بچێتە خوارتر. بۆ FIFO بەکار دەهێنێت و ئەو ڕێگایە دەدۆزێتەوە کە کەمترین هەنگاوی هەیە.
The lecture: BFS starts searching from the root node of the tree and expands all the successor nodes at the current level before it moves to the nodes of the next level. It is implemented with a FIFO queue. The lab notes add: BFS uses a queue for finding the shortest path. In Python, a queue is best built with collections.deque.
وانەکە: BFS لە دەست بە گەڕان دەکات و هەموو ئاستی ئێستا فراوان دەکات پێش ئەوەی بچێتە سەر ئاستی دواتر. بە FIFO جێبەجێ دەکرێت. تێبینییەکانی تاقیگە زیاد دەکەن: BFS بۆ دۆزینەوەی بەکار دەهێنێت. لە بە باشترین شێوە بە collections.deque دروست دەکرێت.
Because it moves level by level, BFS visits the lecture's example tree in this order: S → A → B → C → D → G → H → E → F → I → K. The goal K is on level 4, so BFS meets it last.
چونکە ئاست بە ئاست دەڕوات، BFS سەردانی نموونە وانەکە بەم ڕیزبەندییە دەکات: S → A → B → C → D → G → H → E → F → I → K. ئامانجی K لە ئاستی 4دایە، بۆیە BFS لە کۆتاییدا پێی دەگات.
BFS spreads like a smell: from the start it reaches everything one step away, then everything two steps away, and so on, in growing rings.
BFS وەک بۆن بڵاو دەبێتەوە: لە سەرەتاوە دەگاتە هەموو ئەو شوێنانەی یەک هەنگاو دوورن، پاشان ئەوانەی دوو هەنگاو دوورن و بەم شێوەیە، بە بازنەی گەورەتر و گەورەتر.
Where the analogy stops workingسنووری ئەم نموونەیە
A smell spreads in all directions at once. BFS checks one node at a time; it only looks like rings when you watch the whole search.
بۆن لە یەک کاتدا بەرەو هەموو ئاڕاستەیەک بڵاو دەبێتەوە. BFS لە هەر جارێکدا تەنها یەک دەپشکنێت؛ تەنها کاتێک سەیری هەموو گەڕانەکە دەکەیت وەک بازنە دەردەکەوێت.
How breadth-first search visits a graph level by level, why it uses a queue, and how the code keeps track of visited nodes.
چۆن ئاست بە ئاست سەردانی دەکات، بۆچی بەکاردەهێنێت و کۆدەکە چۆن ئاگای لە دەبێت.
Watch 0:00-5:19: BFS intuition and implementation; stops before the flood-fill example.
لە 0:00 تا 5:19 سەیر بکە: بیرۆکە و جێبەجێکردنی ؛ پێش نموونەی flood fill دەوەستێت.
Breadth-first searchگەڕانی پانایی
Strengths and weaknesses of BFSخاڵە بەهێز و لاوازەکانی BFS
| Advantageسوود | Disadvantageزیان |
|---|---|
| It provides a solution if any solution exists.ئەگەر هەر چارەسەرێک هەبێت، چارەسەرێک دەدات. | It requires lots of memory. زۆری پێویستە. |
| If there is more than one solution, it finds the one with the fewest steps.ئەگەر زیاتر لە یەک چارەسەر هەبێت، ئەوەیان دەدۆزێتەوە کە کەمترین هەنگاوی هەیە. | It needs a lot of time.کاتێکی زۆری دەوێت. |
Measured with the four questions from Search problems (b = branching factor, d = depth of the shallowest goal):
بە چوار پرسیارەکەی کێشەکانی گەڕان پێوانە بکرێت (b = ، d = نزیکترین ئامانج):
- Complete: yes, when b is finite. BFS reaches every level in turn, so it cannot miss a goal at a finite depth.
- Optimal: only when every step costs the same. Then “fewest steps” is also “lowest cost”.
- Time: O(b^d) nodes. Space: O(b^d) nodes — the whole last level waits in the frontier. Memory, not time, is usually the first problem.
- : بەڵێ، کاتێک b سنووردار بێت. BFS یەک لە دوای یەک دەگاتە هەموو ئاستێک، بۆیە ئامانجێک لە سنووردار لەدەست نادات.
- : تەنها کاتێک هەموو هەنگاوێک هەمان کۆستی هەبێت. ئەو کاتە «کەمترین هەنگاو» واتە «کەمترین کۆست»یش.
- کات: O(b^d) . : O(b^d) — هەموو ئاستی کۆتایی لە چاوەڕێ دەکات. زۆرجار ، نەک کات، یەکەم کێشەیە.
Depth-first searchگەڕانی قووڵایی
An uninformed search that always expands the deepest node first, going down one branch as far as it can before backing up. It keeps the frontier in a stack (LIFO).
کە هەمیشە قووڵترین نۆد لە پێشدا فراوان دەکات: بەدوای یەک لقدا تا دەتوانێت دادەبەزێت پێش ئەوەی بگەڕێتەوە. لە (LIFO) هەڵدەگرێت.
The lecture: DFS is called so because it starts from the root node and follows each path to its greatest depth before it moves to the next path. It is implemented with a (see Where computers use stacks).
وانەکە: ناوی DFS لەوەوە هاتووە کە لە دەست پێدەکات و هەر ڕێگەیەک تا قووڵترین خاڵی دەگرێتەبەر پێش ئەوەی بچێتە سەر ڕێگەی دواتر. بە جێبەجێ دەکرێت (بڕوانە کۆمپیوتەر لە کوێ ستاک بەکار دەهێنێت).
On the lecture's example tree, DFS starts at the root S and goes A, then B, then D and E. E has no other successor and the goal is still not found, so the search backtracks: it goes back up to the last node that still has an unvisited child. After backtracking it visits C and then G — the goal — and stops. Order: S → A → B → D → E → C → G.
لەسەر نموونە وانەکە، DFS لە ڕەگی S دەست پێدەکات و دەچێت بۆ A، پاشان B، پاشان D و E. E هیچ منداڵێکی تری نییە و ئامانجەکەش هێشتا نەدۆزراوەتەوە، بۆیە گەڕانەکە دەگەڕێتەوە دواوە (): بەرەو سەرەوە دەگەڕێتەوە بۆ دوایین کە هێشتا منداڵێکی سەرداننەکراوی هەیە. دوای گەڕانەوە سەردانی C و پاشان G — ئامانجەکە — دەکات و دەوەستێت. ڕیزبەندی: S → A → B → D → E → C → G.
DFS “goes like a snake”: straight ahead, then left or right; again straight ahead, then left and right, and so on. It keeps going forward as long as it can and only turns back at a dead end.
DFS «وەک مار دەڕوات»: ڕاستەوڕاست، ئینجا چەپ یان ڕاست؛ پاشان دیسان ڕاستەوڕاست، ئینجا چەپ و ڕاست… هتد. تا بتوانێت بەرەو پێش دەڕوات و تەنها لە ڕێگەیەکی داخراودا دەگەڕێتەوە.
Where the analogy stops workingسنووری ئەم نموونەیە
A snake does not remember where it has been. DFS on a graph needs an explored list, or it can go round a loop for ever.
مار لە بیری نییە لە کوێ بووە. DFS لەسەر پێویستی بە هەیە، دەنا دەکرێت بۆ هەمیشە بە دەوری بازنەیەکدا بسووڕێتەوە.
How depth-first search visits a graph: it goes as deep as it can, keeps waiting vertices on a stack and goes back at dead ends.
چۆن سەردانی دەکات: تا بتوانێت بەرەو قووڵ دەڕوات، ئەو چاوەڕێن لە هەڵدەگرێت و کاتێک ڕێگە کۆتایی دێت دەگەڕێتەوە دواوە.
Watch 12:13-16:03: depth-first search on a graph with a stack: go deep first, and go back when a vertex has no unvisited neighbours.
لە 12:13 تا 16:03 سەیر بکە: لەسەر بە ، واتە سەرەتا بەرەو قووڵ بڕۆ و کاتێک هیچ دراوسێیەکی سەردانینەکراوی نەبوو بگەڕێوە دواوە.
Depth-first searchگەڕانی قووڵایی
Strengths and weaknesses of DFSخاڵە بەهێز و لاوازەکانی DFS
| Advantageسوود | Disadvantageزیان |
|---|---|
| It requires very little memory. زۆر کەمی پێویستە. | There is no guarantee of finding the solution.هیچ گەرەنتییەک نییە کە چارەسەرەکە بدۆزێتەوە. |
| It can reach the goal in less time than BFS.دەتوانێت لە کاتێکی کەمتر لە BFS بگاتە ئامانج. | It goes deep down and sometimes it may go into an infinite loop.بەرەو قووڵایی دەچێت و هەندێک جار لەوانەیە بکەوێتە . |
- Complete: no. On an infinite path, or on a graph with loops and no explored set, it can run for ever. (On a finite graph with an explored set it does finish, and it finds a goal if there is one.)
- Optimal: no. It returns the first (left-most) solution it meets, whatever its length or cost.
- Time: O(b^m) nodes, where m is the maximum depth. Space: only O(b·m) — it keeps one path plus the waiting siblings along it. (That counts the frontier. A full explored list, like the one in the lab code, can grow to every state that was visited.)
- : نەخێر. لەسەر ڕێگەیەکی بێکۆتا، یان لەسەر کە بازنەی تێدایە و نییە، دەکرێت بۆ هەمیشە بڕوات. (لەسەر سنووردار کە هەبێت، کۆتایی دێت و ئەگەر ئامانجێک هەبێت دەیدۆزێتەوە.)
- : نەخێر. یەکەم چارەسەر (چەپترین) دەگەڕێنێتەوە کە پێی دەگات، درێژی یان کۆستی هەرچییەک بێت.
- کات: O(b^m) ، کە m . : تەنها O(b·m) — یەک لەگەڵ ئەو براخوشکانەی بە درێژاییەکەیدا چاوەڕێن هەڵدەگرێت. (ئەمە دەژمێرێت. تەواو، وەک ئەوەی کۆدی تاقیگە، دەتوانێت تا هەموو ئەو سەردان کراون گەورە ببێت.)
from collections import deque
def search(children, start, goal, mode):
frontier = deque([start])
explored = set()
order = []
while frontier:
node = frontier.popleft() if mode == "BFS" else frontier.pop()
if node in explored:
continue
explored.add(node)
order.append(node)
if node == goal:
return order
kids = children.get(node, [])
for child in (reversed(kids) if mode == "DFS" else kids):
if child not in explored:
frontier.append(child)
return order
# The lecture's BFS example tree (goal K)
bfs_tree = {"S": ["A", "B"], "A": ["C", "D"], "B": ["G", "H"],
"C": ["E", "F"], "G": ["I"], "E": ["K"]}
# The lecture's DFS example tree (goal G)
dfs_tree = {"S": ["A", "H"], "A": ["B", "C"], "H": ["I", "J"],
"B": ["D", "E"], "C": ["G"], "I": ["K"]}
print("BFS, goal K:", " -> ".join(search(bfs_tree, "S", "K", "BFS")))
print("DFS, goal G:", " -> ".join(search(dfs_tree, "S", "G", "DFS")))
print("DFS on the BFS tree, goal K:", " -> ".join(search(bfs_tree, "S", "K", "DFS")))
print("BFS on the DFS tree, goal G:", " -> ".join(search(dfs_tree, "S", "G", "BFS")))BFS, goal K: S -> A -> B -> C -> D -> G -> H -> E -> F -> I -> K DFS, goal G: S -> A -> B -> D -> E -> C -> G DFS on the BFS tree, goal K: S -> A -> C -> E -> K BFS on the DFS tree, goal G: S -> A -> H -> B -> C -> I -> J -> D -> E -> G
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4-20
One function for both algorithms:
popleft()makes the frontier a queue (BFS),pop()a stack (DFS).یەک بۆ هەردوو :
popleft()دەکات بە (BFS) وpop()بە (DFS).- Lineدێڕی 23-28
Each tree is a : node → list of its children, left to right.
هەر دارێک : ← منداڵەکانی، لە چەپەوە بۆ ڕاست.
Lab 1: the frontier by handتاقیگەی 1: بەرە بە دەست
Lab 1 practises the loop on a : a tree in which every node has 0, 1 or 2 branches. The top node is the head or ; nodes with no children are .
تاقیگەی 1 خولەکە لەسەر ڕاهێنان دەکات: کە هەر 0، 1 یان 2 لقی هەیە. سەرەوە سەر یان ؛ ئەو منداڵیان نییە .
- Empty?بەتاڵە؟
Is the frontier empty? If yes, stop: the goal is not there.
ئایا بەتاڵە؟ ئەگەر بەڵێ، بوەستە: ئامانجەکە لێرە نییە.
- Removeدەرهێنان
If it is not empty, remove a node from it.
ئەگەر بەتاڵ نەبوو، لێی دەربهێنە.
- Found?دۆزرایەوە؟
If the node is the goal, return it.
ئەگەر ئامانج بوو، بیگەڕێنەوە.
- Expandفراوانکردن
If not, expand it: put its children into the frontier.
ئەگەر نا، فراوانی بکە: منداڵەکانی بخەرە ناو .
Worked example with goal = 7. Frontier: [2] → is it empty? No → remove 2 → is 2 the goal? No → expand to 4 and 8 → frontier: [4, 8] → … The loop goes on until every node has been removed. 7 is not in the tree, so the frontier finally becomes empty and the answer is “not found”.
نموونەی کارپێکراو بە ئامانج = 7. : [2] ← بەتاڵە؟ نەخێر ← 2 دەربهێنە ← ئایا 2 ئامانجە؟ نەخێر ← فراوانی بکە بۆ 4 و 8 ← : [4, 8] ← … خولەکە بەردەوام دەبێت تا هەموو دەردەهێنرێن. 7 لە دارەکەدا نییە، بۆیە لە کۆتاییدا بەتاڵ دەبێت و وەڵامەکە «نەدۆزرایەوە»یە.
Lab 1: the frontier by handتاقیگەی 1: بەرە بە دەست
Why we need an explored listبۆچی پێویستمان بە کۆمەڵەی پشکنراو هەیە
Now the lab adds a node 3 that is joined to the root 2 in both directions: 2 → 3 and 3 → 2. This makes a loop, so the drawing is no longer a tree but a .
ئێستا تاقیگەکە بە ناوی 3 زیاد دەکات کە بە هەردوو ئاڕاستە بە ڕەگی 2ەوە بەستراوە: 2 ← 3 و 3 ← 2. ئەمە ڕێگەیەکی بازنەیی دروست دەکات، بۆیە وێنەکە ئیتر نییە، بەڵکو .
Is the frontier empty?
ئایا بەتاڵە؟
If not, remove the left one (in the lab, left always comes first).
ئەگەر نا، ئەوەی چەپ دەربهێنە (لە تاقیگەدا چەپ هەمیشە لە پێشە).
Add it to the explored list.
بیخەرە ناو .
If it is the goal, return it.
ئەگەر ئامانج بوو، بیگەڕێنەوە.
If not, expand it — but only add children that are not already explored or in the frontier.
ئەگەر نا، فراوانی بکە — بەڵام تەنها ئەو منداڵانە زیاد بکە کە پێشتر نەپشکنراون و لە نین.
Worked example with goal = 7. The frontier could start with 2 or 3; the notes choose 3. Remove 3 → add 3 to the explored list → is 3 the goal? No → expand to 2. Frontier: [2] → remove 2 → add 2 to the explored list → is 2 the goal? No → expand to 4, then 8 (3 is already explored, so it is not added again) → and so on.
نموونەی کارپێکراو بە ئامانج = 7. دەکرێت بە 2 یان 3 دەست پێبکات؛ تێبینییەکان 3 هەڵدەبژێرن. 3 دەربهێنە ← 3 بخەرە ناو ← ئایا 3 ئامانجە؟ نەخێر ← فراوانی بکە بۆ 2. : [2] ← 2 دەربهێنە ← 2 بخەرە ناو ← ئایا 2 ئامانجە؟ نەخێر ← فراوانی بکە بۆ 4، پاشان 8 (3 پێشتر پشکنراوە، بۆیە دووبارە زیاد ناکرێتەوە) ← و بەم شێوەیە.
# The Lab 1 drawing: node 2 has children 4 (left) and 8 (right),
# 4 has the child 1, 8 has the child 5, and node 3 is joined to 2
# in BOTH directions (2 -> 3 and 3 -> 2): a loop, so this is a graph.
graph = {2: [4, 8, 3], 3: [2], 4: [1], 8: [5], 1: [], 5: []}
def dfs_trace(start, goal, use_explored, max_steps=20):
frontier = [start]
explored = []
for step in range(1, max_steps + 1):
print("frontier:", frontier)
if not frontier: # 1. Empty?
print(" empty -> goal", goal, "not found")
return
current = frontier.pop() # 2. Remove (stack: last one)
if use_explored:
explored.append(current) # 3. Add to explored
if current == goal: # 4. If found, return goal
print(" remove", current, "-> goal found!")
return
new = []
for child in reversed(graph[current]): # 5. Expand (left child comes out first)
if child not in frontier and child not in explored:
frontier.append(child)
new.append(child)
print(" remove", current, "| explored:", explored,
"| goal?", current == goal, "| add", new[::-1])
print("... stopped after", max_steps, "steps")
print("== With an explored list ==")
dfs_trace(3, 7, use_explored=True)
print()
print("== Without an explored list ==")
dfs_trace(3, 7, use_explored=False, max_steps=8)== With an explored list == frontier: [3] remove 3 | explored: [3] | goal? False | add [2] frontier: [2] remove 2 | explored: [3, 2] | goal? False | add [4, 8] frontier: [8, 4] remove 4 | explored: [3, 2, 4] | goal? False | add [1] frontier: [8, 1] remove 1 | explored: [3, 2, 4, 1] | goal? False | add [] frontier: [8] remove 8 | explored: [3, 2, 4, 1, 8] | goal? False | add [5] frontier: [5] remove 5 | explored: [3, 2, 4, 1, 8, 5] | goal? False | add [] frontier: [] empty -> goal 7 not found == Without an explored list == frontier: [3] remove 3 | explored: [] | goal? False | add [2] frontier: [2] remove 2 | explored: [] | goal? False | add [4, 8, 3] frontier: [3, 8, 4] remove 4 | explored: [] | goal? False | add [1] frontier: [3, 8, 1] remove 1 | explored: [] | goal? False | add [] frontier: [3, 8] remove 8 | explored: [] | goal? False | add [5] frontier: [3, 5] remove 5 | explored: [] | goal? False | add [] frontier: [3] remove 3 | explored: [] | goal? False | add [2] frontier: [2] remove 2 | explored: [] | goal? False | add [4, 8, 3] ... stopped after 8 steps
Without the explored list, 3, 2, 4, 1, 8, 5, 3, 2… repeat for ever; the program stops itself after 8 steps.
بەبێ ، 3، 2، 4، 1، 8، 5، 3، 2… بۆ هەمیشە دووبارە دەبنەوە؛ دوای 8 هەنگاو خۆی دەوەستێنێت.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4
The drawing as a : each node and its neighbours, left to right. 2 lists 3 and 3 lists 2: that is the loop.
وێنەکە وەک : هەر و دراوسێکانی، لە چەپەوە بۆ ڕاست. 2 ناوی 3 دەهێنێت و 3 ناوی 2: ئەوە ڕێگا بازنەییەکەیە.
- Lineدێڕی 12-25
The numbered comments are the steps of the lab's loop.
pop()takes the last item, so the frontier is a stack (DFS).لێدوانە ژمارەدارەکان هەنگاوەکانی خولەکەی تاقیگەن.
pop()دوایین دانە وەردەگرێت، بۆیە (DFS).- Lineدێڕی 22
Children are pushed in reverse, so the left child ends on top of the stack. The output prints the frontier as a list: its right end is the top.
منداڵەکان بە پێچەوانەوە دەخرێنە ناوی، بۆ ئەوەی منداڵی چەپ بکەوێتە سەرەوەی . دەرئەنجامەکە وەک لیست چاپ دەکات: لای ڕاستی سەرەوەیە.
- Lineدێڕی 16-17
With
use_explored=Falsethis line is skipped, so nothing is remembered.لەگەڵ
use_explored=Falseئەم دێڕە جێبەجێ ناکرێت، بۆیە هیچ شتێک لە بیر ناگیرێت.
Lab 1: the frontier by handتاقیگەی 1: بەرە بە دەست
Left comes firstچەپ لە پێشە
The notes say: left is prioritized. In computing, we usually count the left side first and then the right side. So among the children of a node, the left child is visited first.
تێبینییەکان دەڵێن: چەپ لە پێشترە. لە کۆمپیوتەردا بەگشتی سەرەتا حساب بۆ دەستەچەپ دەکرێت، ئینجا دەستەڕاست. بۆیە لە نێوان منداڵەکانی ، سەرەتا سەردانی منداڵی چەپ دەکرێت.
With a queue that is easy: add the left child, then the right child; the left one comes out first. With a stack it is the other way round: to visit the left node first, you must put the right node into the stack first and then the left node, because the last one in is the first one out.
لەگەڵ ئەمە ئاسانە: منداڵی چەپ زیاد بکە، پاشان منداڵی ڕاست؛ ئەوەی چەپ یەکەم جار دەردەچێت. لەگەڵ بە پێچەوانەوەیە: بۆ سەردانیکردنی دەستەچەپ لە پێشدا، پێویستە سەرەتا دەستەڕاست لە دابنرێت ئینجا دەستەچەپ، چونکە دوایین هاتوو یەکەم دەرچووە.
Lab 1 code: DFS on a treeکۆدی تاقیگەی 1: DFS لەسەر دار
Now the same loop in Python. The program builds the tree 3; 8 and 0; 5, 6 and 1 with two , Node and Tree, and searches it depth-first. (If you need a reminder about classes and lists, see Python for the AI labs.)
ئێستا هەمان خول بە . 3؛ 8 و 0؛ 5، 6 و 1 بە دوو ، Node و Tree، دروست دەکات و بە شێوەی قووڵایی تێیدا دەگەڕێت. (ئەگەر پێویستت بە بیرخستنەوەی و لیستەکان هەیە، سەیری Python بۆ تاقیگەکانی ژیریی دەستکرد بکە.)
class Node:
def __init__(self, data):
self.data = data
self.left = None # no children yet
self.right = None
class Tree:
def __init__(self, head_node):
self.head_node = head_node # the root ("head") node
def DFS(self, goal): # DFS uses a stack
frontier = [self.head_node]
explored = []
while frontier:
current = frontier.pop() # pop() removes the LAST item
if current.data == goal: # goal test
return True
explored.append(current)
# Push the right child first, then the left child,
# so that the left child is taken out first.
if current.right is not None and current.right not in frontier and current.right not in explored:
frontier.append(current.right)
if current.left is not None and current.left not in frontier and current.left not in explored:
frontier.append(current.left)
return False # the frontier is empty: the goal is not in the tree
# 3
# / \
# 8 0
# / \ \
# 5 6 1
node1 = Node(3) # root node
node2 = Node(8)
node3 = Node(0)
node4 = Node(5)
node5 = Node(6)
node6 = Node(1)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.right = node6
tree = Tree(node1)
print("Is 100 available?", tree.DFS(100))
print("Is 6 available?", tree.DFS(6))Is 100 available? False Is 6 available? True
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 1-5
Nodestores a value indata.leftandrightstart asNone: no children yet.Nodeنرخێک لەdataدا هەڵدەگرێت.leftوrightبەNoneدەست پێدەکەن: هێشتا منداڵ نییە.- Lineدێڕی 8-10
Treeonly remembers its root, the “head” node.Treeتەنها ڕەگەکەی لە بیرە، «سەر».- Lineدێڕی 13-14
The frontier starts with the root. The explored list starts empty.
بە ڕەگ دەست پێدەکات. بەتاڵ دەست پێدەکات.
- Lineدێڕی 16-17
while frontier:runs while the list is not empty.pop()removes the last item: the list works as a stack, so this is DFS.while frontier:تا لیستەکە بەتاڵ نەبێت کار دەکات.pop()دوایین دانە لادەبات: لیستەکە وەک کار دەکات، بۆیە ئەمە DFSە.- Lineدێڕی 19-20
The goal test.
.
- Lineدێڕی 26-29
Each child is added only if it exists (
is not None) and is not already in the frontier or the explored list. Right first, then left.هەر منداڵێک تەنها زیاد دەکرێت ئەگەر هەبێت (
is not None) و پێشتر لە یان لە نەبێت. سەرەتا ڕاست، پاشان چەپ.- Lineدێڕی 31
An empty frontier means the whole tree was searched: return
False.بەتاڵ واتە هەموو دارەکە گەڕاوە:
Falseبگەڕێنەوە.- Lineدێڕی 34-50
The tree is built by linking nodes. The comment draws it.
دارەکە بە بەستنەوەی دروست دەکرێت. لێدوانەکە وێنەکەی دەکێشێت.
From DFS to BFS in two changesلە DFSەوە بۆ BFS بە دوو گۆڕانکاری
The comments of the lab code explain how to turn the stack into a queue:
لێدوانەکانی کۆدی تاقیگە ڕوونی دەکەنەوە چۆن بکەیت بە :
- Insert
0intopop():pop()removes the last element of the list,pop(0)removes the first element. - Swap the two
ifstatements, so the left child is added before the right child.
0بخەرە ناوpop():pop()دوایین دانەی لیستەکە لادەبات،pop(0)یەکەم دانە.- هەردوو ڕستەی
ifشوێن بگۆڕەوە، بۆ ئەوەی منداڵی چەپ پێش منداڵی ڕاست زیاد بکرێت.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class Tree:
def __init__(self):
self.head = None # the root is attached later
def BFS(self, goal): # BFS uses a queue
frontier = [self.head]
explored = []
while frontier:
current = frontier.pop(0) # pop(0) removes the FIRST item
if current.data == goal:
return True
explored.append(current)
# Left first, then right: the queue keeps this order.
if current.left is not None and current.left not in frontier and current.left not in explored:
frontier.append(current.left)
if current.right is not None and current.right not in frontier and current.right not in explored:
frontier.append(current.right)
return False
# 3
# / \
# 8 0
# / \ \
# 5 6 1
node1 = Node(3)
node2 = Node(8)
node3 = Node(0)
node4 = Node(5)
node5 = Node(6)
node6 = Node(1)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.right = node6
tree = Tree()
tree.head = node1
print(tree.BFS(1))
print(tree.BFS(9))True False
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 8-10
This version creates an empty tree and attaches the root later with
tree.head = node1.ئەم وەشانە بەتاڵ دروست دەکات و دواتر ڕەگەکە بە
tree.head = node1دەبەستێتەوە.- Lineدێڕی 17
pop(0): first in, first out — a queue.pop(0): یەکەم هاتوو، یەکەم دەرچوو — .- Lineدێڕی 25-28
Left child first, then right: the queue keeps this order.
سەرەتا منداڵی چەپ، پاشان ڕاست: ئەم ڕیزبەندییە دەپارێزێت.
- Lineدێڕی 53-54
1 is in the tree (
True); 9 is not (False).1 لە دارەکەدایە (
True)؛ 9 نییە (False).
Another solution of the same lab gives the same two hints in its comments: “if you want BFS, use .pop(0)” and “for BFS, also swap right and left, so that left comes first”. That version searches for 9 depth-first and prints False.
چارەسەرێکی تری هەمان تاقیگە هەمان دوو ئامۆژگاری لە لێدوانەکانیدا دەدات: «ئەگەر BFSت دەوێت، .pop(0) بەکار بهێنە» و «بۆ BFS ڕاست و چەپیش ئاڵوگۆڕ بکە، بۆ ئەوەی چەپ لە پێشدا بێت». ئەو وەشانە بە شێوەی قووڵایی بۆ 9 دەگەڕێت و False چاپ دەکات.
Traversal: visiting every nodeسەردانیکردن: سەردانیکردنی هەموو نۆدێک
Visiting every node of a tree or graph once, in a fixed order, without looking for a goal, for example the breadth-first order 3, 8, 0, 5, 6, 1.
بریتییە لە سەردانیکردنی هەموو یان ، هەر یەکەیان یەک جار و بە ڕیزبەندییەکی دیاریکراو، بەبێ گەڕان بۆ ئامانج؛ بۆ نموونە ڕیزبەندیی پانایی 3، 8، 0، 5، 6، 1.
The lab code has one more comment: “Traverse only (remove the previous if statement): print(current.data)”. If we delete the goal test and simply record each node we remove, the search becomes a traversal: it visits every node once and gives their order.
کۆدی تاقیگە لێدوانێکی تریشی هەیە: «تەنها (ڕستەی ifـی پێشوو لاببە): print(current.data)». ئەگەر بسڕینەوە و تەنها هەر کە دەریدەهێنین تۆمار بکەین، گەڕانەکە دەبێت بە : سەردانی هەموو یەک جار دەکات و ڕیزبەندییەکەیان دەدات.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def traverse(root, mode):
"""Visit every node once and return the visiting order (no goal test)."""
frontier = [root]
explored = []
while frontier:
if mode == "DFS":
current = frontier.pop() # stack: last in, first out
else:
current = frontier.pop(0) # queue: first in, first out
explored.append(current.data) # "Traverse only": record the node
if mode == "DFS":
children = [current.right, current.left] # right first, so left comes out first
else:
children = [current.left, current.right] # left first, so left comes out first
for child in children:
if child is not None:
frontier.append(child)
return explored
# 3
# / \
# 8 0
# / \ \
# 5 6 1
root = Node(3)
root.left, root.right = Node(8), Node(0)
root.left.left, root.left.right = Node(5), Node(6)
root.right.right = Node(1)
print("DFS order:", traverse(root, "DFS"))
print("BFS order:", traverse(root, "BFS"))DFS order: [3, 8, 5, 6, 0, 1] BFS order: [3, 8, 0, 5, 6, 1]
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 14-17
The same two choices as before:
pop()for DFS,pop(0)for BFS.هەمان دوو هەڵبژاردنی پێشوو:
pop()بۆ DFS وpop(0)بۆ BFS.- Lineدێڕی 18
No goal test: every removed node is recorded.
هیچ نییە: هەموو دەرهێنراو تۆمار دەکرێت.
- Lineدێڕی 20-23
The order in which the children go in, so that the left child always comes out first.
ڕیزبەندیی چوونەژوورەوەی منداڵەکان، بۆ ئەوەی منداڵی چەپ هەمیشە لە پێشدا دەربچێت.
Traversal: visiting every nodeسەردانیکردن: سەردانیکردنی هەموو نۆدێک
BFS and DFS orders side by sideڕیزبەندیی BFS و DFS لە تەنیشت یەک
The lab notes compare the two orders on one tree: node 0 has the children 1, 2 and 3; 1 has 4 and 5; 2 has 6; 3 has 7.
تێبینییەکانی تاقیگە دوو ڕیزبەندییەکە لەسەر یەک دار بەراورد دەکەن: 0 منداڵەکانی 1، 2 و 3ی هەیە؛ 1 منداڵەکانی 4 و 5؛ 2 منداڵی 6؛ 3 منداڵی 7.
Here is a cleaner version of the lab code that you can reuse. One search() function does both jobs: mode chooses the order, and goal=None turns it into a traversal. It keeps the frontier in a deque and the explored nodes in a , which makes in explored fast.
ئەمە وەشانێکی ڕێکتری کۆدی تاقیگەیە کە دەتوانیت دووبارە بەکاری بهێنیتەوە. یەک search() هەردوو کارەکە دەکات: mode ڕیزبەندییەکە هەڵدەبژێرێت و goal=None دەیکات بە . لە dequeدا و پشکنراوەکان لە هەڵدەگرێت، کە in explored خێرا دەکات.
from collections import deque
# The tree as a dictionary: each node -> its children, left to right.
# 0
# / | \
# 1 2 3
# / \ | |
# 4 5 6 7
children = {0: [1, 2, 3], 1: [4, 5], 2: [6], 3: [7], 4: [], 5: [], 6: [], 7: []}
def search(start, goal, mode):
"""mode "BFS" uses the frontier as a queue, "DFS" as a stack.
With goal=None it is a traversal: it visits every node."""
frontier = deque([start])
explored = set() # a set: checking "in explored" is fast
order = []
while frontier:
node = frontier.popleft() if mode == "BFS" else frontier.pop()
if node in explored:
continue
explored.add(node)
order.append(node)
if node == goal:
return order, True
kids = children[node]
if mode == "DFS":
kids = reversed(kids) # push right first, so the left child is on top
for child in kids:
if child not in explored:
frontier.append(child)
return order, False
print("BFS traversal:", search(0, None, "BFS")[0])
print("DFS traversal:", search(0, None, "DFS")[0])
print("BFS looking for 6:", search(0, 6, "BFS"))
print("DFS looking for 6:", search(0, 6, "DFS"))BFS traversal: [0, 1, 2, 3, 4, 5, 6, 7] DFS traversal: [0, 1, 4, 5, 2, 6, 3, 7] BFS looking for 6: ([0, 1, 2, 3, 4, 5, 6], True) DFS looking for 6: ([0, 1, 4, 5, 2, 6], True)
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 3-9
The tree as a dictionary of children.
دارەکە وەک منداڵەکان.
- Lineدێڕی 15-16
dequeis a fast queue/stack;set()makes the membership test quick.deque/ خێرایە؛set()پشکنینی بوونی ئەندام خێرا دەکات.- Lineدێڕی 20
The line that chooses the order:
popleft()takes the oldest node (queue, BFS),pop()the newest (stack, DFS). Lines 29–30 only make the left child come out first.ئەو دێڕەی ڕیزبەندییەکە هەڵدەبژێرێت:
popleft()کۆنترین وەردەگرێت (، BFS) وpop()نوێترین (، DFS). دێڕەکانی 29–30 تەنها وا دەکەن منداڵی چەپ لە پێشدا دەربچێت.- Lineدێڕی 21-22
A node can be added twice before it is expanded; the second copy is skipped.
دەکرێت دوو جار پێش زیاد بکرێت؛ وێنەی دووەم جێدەهێڵرێت.
BFS and DFS comparedبەراوردی BFS و DFS
| Propertyتایبەتمەندی | BFS | DFS |
|---|---|---|
| Frontier | Queue (FIFO) (FIFO) | Stack (LIFO) (LIFO) |
| Orderڕیزبەندی | Level by levelئاست بە ئاست | Branch by branch, with backtrackingلق بە لق، لەگەڵ |
| Complete?؟ | Yes (finite b)بەڵێ (b سنووردار) | No (infinite paths, loops)نەخێر (ڕێگای بێکۆتا، بازنە) |
| Optimal?؟ | Yes, if all steps cost the sameبەڵێ، ئەگەر هەموو هەنگاوەکان هەمان کۆستیان هەبێت | Noنەخێر |
| Timeکات | O(b^d) | O(b^m) |
| Memory | O(b^d) — a lotO(b^d) — زۆر | O(b·m) — littleO(b·m) — کەم |
| Good when…باشە کاتێک… | you need the fewest steps and have enough memoryکەمترین هەنگاوت دەوێت و پێویستت هەیە | memory is small and solutions are deep or plentiful کەمە و چارەسەرەکان قووڵن یان زۆرن |
The next lesson, Solving a maze, uses both algorithms on the Lab 2 maze. More uninformed search shows how to keep DFS's small memory and still be complete (depth-limited and iterative deepening search).
وانەی دواتر، چارەسەرکردنی لابیرینت، هەردوو لەسەر تاقیگەی 2 بەکار دەهێنێت. گەڕانی بێزانیاریی زیاتر پیشان دەدات چۆن کەمی DFS بپارێزیت و هێشتا هەبێت ( و ).
Common mistakesهەڵە باوەکان
| Mistakeهەڵە | Fixچارەسەر |
|---|---|
| Forgetting the explored list on a graph with loops.لەبیرکردنی لەسەر کە بازنەی تێدایە. | Keep an explored list (better: a set) and skip nodes already in it. هەڵبگرە (باشتر: ) و ئەو تێیدان جێبهێڵە. |
Using pop(0) but adding the right child first.بەکارهێنانی pop(0) بەڵام زیادکردنی منداڵی ڕاست لە پێشدا. | With a queue, add left then right. With a stack, push right then left.لەگەڵ ، چەپ پاشان ڕاست زیاد بکە. لەگەڵ ، ڕاست پاشان چەپ دابنێ. |
Calling a function DFS when it uses pop(0) (or calling a pop() traversal “breadth-first”).ناونانی بە DFS کاتێک pop(0) بەکار دەهێنێت (یان ناونانی pop() بە «پانایی»). | pop() = stack = DFS; pop(0) = queue = BFS.pop() = = DFS؛ pop(0) = = BFS. |
| Saying BFS finds the cheapest path.وتنی ئەوەی BFS هەرزانترین ڕێگە دەدۆزێتەوە. | It finds the path with the fewest steps; that is the cheapest only if all steps cost the same.ئەو ڕێگەیە دەدۆزێتەوە کە کەمترین هەنگاوی هەیە؛ تەنها کاتێک هەرزانترینە کە هەموو هەنگاوەکان هەمان کۆستیان هەبێت. |
| Saying DFS is faster than BFS.وتنی ئەوەی DFS لە BFS خێراترە. | It depends on where the goal is. DFS can also run for ever.بەندە بە شوێنی ئامانجەکە. DFS دەکرێت بۆ هەمیشەش بڕوات. |
Exercisesڕاهێنانەکان
Use the tree of the Lab 1 notes (2; 4 and 8; 1 under 4; 5 under 8). Write the BFS order and the DFS order. Left comes first.
لە تێبینییەکانی تاقیگەی 1 بەکار بهێنە (2؛ 4 و 8؛ 1 لە ژێر 4؛ 5 لە ژێر 8). ڕیزبەندیی BFS و ڕیزبەندیی DFS بنووسە. چەپ لە پێشە.
Show answerوەڵامەکە پیشان بدە
- BFS: 2, 4, 8, 1, 5 (level by level).
- DFS: 2, 4, 1, 8, 5 (the whole left branch first).
- BFS: 2، 4، 8، 1، 5 (ئاست بە ئاست).
- DFS: 2، 4، 1، 8، 5 (سەرەتا هەموو لقی چەپ).
Look at the last two lines that lecture_trees.py printed. Explain why DFS reaches K on the BFS example tree after only 5 nodes, while BFS needs 10 nodes to reach G on the DFS example tree.
سەیری دوو دێڕی کۆتایی بکە کە lecture_trees.py چاپی کردن. ڕوونی بکەرەوە بۆچی DFS لەسەر نموونە دارەکەی BFS تەنها دوای 5 دەگاتە K، لە کاتێکدا BFS لەسەر نموونە دارەکەی DFS پێویستی بە 10 هەیە تا بگاتە G.
Show answerوەڵامەکە پیشان بدە
DFS on the BFS tree, goal K: S -> A -> C -> E -> K BFS on the DFS tree, goal G: S -> A -> H -> B -> C -> I -> J -> D -> E -> G
DFS dives straight down the left side and meets K after 5 nodes. BFS must finish levels 1 and 2 before it reaches G on level 3.
DFS ڕاستەوخۆ بە لای چەپدا دادەبەزێت و دوای 5 دەگاتە K. BFS دەبێت ئاستەکانی 1 و 2 تەواو بکات پێش ئەوەی بگاتە G لە ئاستی 3.
Change lab1_dfs.py so that it prints each node's value when it is removed from the frontier, and search for 1. What does it print?
lab1_dfs.py بگۆڕە بۆ ئەوەی نرخی هەر کاتێک لە دەردەهێنرێت چاپ بکات و بۆ 1 بگەڕێ. چی چاپ دەکات؟
Hintئاماژە
Add one print right after pop().
یەک print ڕاستەوخۆ دوای pop() زیاد بکە.
Show answerوەڵامەکە پیشان بدە
current = frontier.pop() # pop() removes the LAST item
print(current.data) # new line: show each removed node
...
print("Is 1 available?", tree.DFS(1))3 8 5 6 0 1 Is 1 available? True
The nodes come out in DFS order 3, 8, 5, 6, 0, 1. The goal 1 is the last node, so DFS has to visit the whole tree before it finds it.
بە ڕیزبەندیی DFS دەردەچن: 3، 8، 5، 6، 0، 1. ئامانجی 1 دوایین ، بۆیە DFS دەبێت سەردانی هەموو دارەکە بکات پێش ئەوەی بیدۆزێتەوە.
Summaryپوختە
- BFS and DFS run the same loop. BFS takes the oldest frontier node (queue,
pop(0)); DFS takes the newest (stack,pop()). - BFS goes level by level, spreads like a smell, is complete and finds the fewest steps, but needs much memory.
- DFS goes deep like a snake and backtracks; it needs little memory but is not complete or optimal.
- On a graph with loops, an explored list stops the endless repeats.
- With a goal it is a search; without a goal it is a traversal.
- BFS و DFS هەمان خول جێبەجێ دەکەن. BFS کۆنترین وەردەگرێت (،
pop(0))؛ DFS نوێترین (،pop()). - BFS ئاست بە ئاست دەڕوات، وەک بۆن بڵاو دەبێتەوە، هەیە و کەمترین هەنگاو دەدۆزێتەوە، بەڵام زۆری پێویستە.
- DFS وەک مار بەرەو قووڵایی دەڕوات و دەگەڕێتەوە دواوە؛ کەمی پێویستە بەڵام نە هەیە نە .
- لەسەر کە بازنەی تێدایە، ڕێگری لە دووبارەبوونەوەی بێکۆتا دەکات.
- ئەگەر ئامانج هەبێت گەڕانە؛ ئەگەر ئامانج نەبێت .
Which data structure does BFS use, and which does DFS use?BFS کام پێکهاتەی دراوە بەکار دەهێنێت و DFS کامیان؟
BFS uses a FIFO queue; DFS uses a LIFO stack.
BFS FIFO بەکار دەهێنێت؛ DFS LIFO.
Give the BFS order of the lecture tree S; A, B; C, D, G, H; E, F, I; K.ڕیزبەندیی BFS بۆ دارەکەی وانەکە بنووسە: S؛ A، B؛ C، D، G، H؛ E، F، I؛ K.
S, A, B, C, D, G, H, E, F, I, K.
S، A، B، C، D، G، H، E، F، I، K.
Why can DFS fall into an infinite loop?بۆچی DFS دەکرێت بکەوێتە خولێکی بێکۆتاوە؟
It always goes deeper first; on an endless path or a loop without an explored list it never comes back.
هەمیشە سەرەتا قووڵتر دەچێت؛ لەسەر ڕێگەیەکی بێکۆتا یان بازنەیەک بەبێ هەرگیز ناگەڕێتەوە.
How do you visit the left child first with a stack?چۆن بە ستاک سەرەتا سەردانی منداڵی چەپ دەکەیت؟
Push the right child first and the left child last.
سەرەتا منداڵی ڕاست دابنێ و لە کۆتاییدا منداڵی چەپ.
Lesson complete!وانەکە تەواو بوو!
Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.
Key termsزاراوە سەرەکییەکان
Solving a Maze with DFS and BFSچارەسەرکردنی لابیرینت بە DFS و BFS
Related lecturesوانە پەیوەندیدارەکان
References and further readingسەرچاوەکان و خوێندنەوەی زیاتر
This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.