الدرس 21 · Algorithms

Graph search: BFS and DFS

لم يُترجم بعد؛ يُعرض باللغة الإنجليزية

Maps, friend lists, web links and computer networks are all graphs: things joined to other things. Searching one means visiting every node you can reach, without going round in circles. Step through breadth-first search and depth-first search on the same 7-node graph, watch the queue and the stack that drive them, and see why only one of them finds shortest paths.

12 دقيقة12 خطوات5 أسئلةIntermediate

شكل 21 · تفاعلي

جارٍ تحميل الرسم…

أو ← →

اختبر نفسك

5 أسئلة سريعة

اختر إجابة لتعرف السبب. تُحفَظ نتيجتك مع تقدّمك.

01Breadth-first search keeps the nodes it still has to visit in which structure?

BFS takes the node that has waited longest. That is a queue (first in, first out), which is why it finishes every node 1 edge away before any node 2 edges away.

02On the lesson's graph, starting at A, what order does BFS visit the nodes in?

A first, then its neighbours B and C, then their new neighbours D, E and F, then G. A B D G E F C is the depth-first order.

03What does the seen set stop?

E and F both lead to G, which is already seen, so G is not added again. Without the check, a graph with a loop would make the search go round forever.

04DFS reached C along A, B, D, G, F, C. What does that tell you?

DFS follows one path as deep as it can, so the path it finds can be long. BFS reaches C in 1 edge because it explores level by level.

05Edges now have costs, and you want the cheapest route. Which algorithm fits?

BFS counts edges, not costs. Dijkstra's algorithm always takes the cheapest node next from a priority queue; OSPF routers use it to pick routes by link cost.

المصطلحات الأساسية

المسرد

Graph: A set of nodes (also called vertices) joined by edges, such as places joined by roads.
Neighbour: A node one edge away. A graph is often stored as a list of neighbours for each node (an adjacency list).
Queue: A line where the first item in is the first out (FIFO). Python's collections.deque is a fast queue.
Stack: A pile where the last item in is the first out (LIFO). Recursive calls form a stack.
Breadth-first search (BFS): Explores level by level with a queue; finds the fewest edges from the start in an unweighted graph.
Depth-first search (DFS): Follows one path as far as it can, then backtracks; uses a stack or recursion.
Seen set: The record of nodes already found, so none is added twice and loops cannot trap the search.
O(V + E): Work that grows with the number of nodes (V) plus the number of edges (E).

تفاصيل إضافية

الملاحظات والمصادر

A Python list can act as a queue, but list.pop(0) has to shift every other item. collections.deque is built for fast appends and pops at both ends, so BFS uses it.
A Python set has no order. The drawing lists the seen set in the order nodes were added, to make it easy to follow.
Python limits how deep recursion can go (sys.getrecursionlimit() is 1000 by default). For very deep graphs, DFS uses an explicit list as a stack instead of recursion.
O(V + E) assumes adjacency lists, as here. If the graph is stored as a V by V table (an adjacency matrix), finding neighbours costs O(V) per node, so both searches take O(V²).
Dijkstra's algorithm needs edge costs that are zero or more. OSPF routers run it on the link costs of their area to build their routing tables (RFC 2328, section 16.1).
Both searches try neighbours in alphabetical order. A different order gives a different but equally valid visit order; BFS distances stay the same.

اختبار يتاح بعد الخطوة الأخيرة.