القوة الغاشمة والبحث الشامل
تغطي هذه الوحدة استراتيجية القوة الغاشمة لحل المشكلات، بما في ذلك خوارزميات الترتيب (Selection و Bubble Sort)، والبحث المتسلسل، ومطابقة السلاسل النصية، ومشكلة أقرب نقطتين. كما تتناول البحث الشامل للمشكلات التوافقية مثل البائع المتجول، وحقيبة الظهر، ومشكلة التعيين، بالإضافة إلى خوارزميات البحث في الرسوم البيانية (DFS و BFS).
Brute Force and Exhaustive Search
This module covers the Brute Force strategy for problem-solving, including sorting algorithms (Selection and Bubble Sort), sequential search, string matching, and the closest-pair problem. It also explores Exhaustive Search for combinatorial problems like TSP, Knapsack, and Assignment problems, along with graph traversal algorithms (DFS and BFS).
أهداف التعلم
- وصف استراتيجية القوة الغاشمة والبحث الشامل.
- التعرف على مشكلتي ترتيب يتم حلهما باستخدام القوة الغاشمة.
- تطبيق البحث المتسلسل والقوة الغاشمة في مشكلة مطابقة السلاسل النصية.
- تطبيق القوة الغاشمة في حل مشكلة أقرب زوج من النقاط.
- التمييز بين البحث في العمق أولاً (DFS) والبحث في العرض أولاً (BFS).
- Describe Brute force and exhaustive search.
- Recognize two sorting problems solved by Brute force.
- Demonstrate sequential search and brute-force in string matching problem.
- Demonstrate brute-force in solving closest-Pair.
- Distinguish between the Depth-First Search and Breadth-First Search.
1 استراتيجية القوة الغاشمة
1 Brute Force Strategy
القوة الغاشمة هي استراتيجية تعتمد على بيان المشكلة وتعريفات المفاهيم المعنية.
على الرغم من أنها غالباً ما تكون غير فعالة (inefficient)، إلا أنها مفيدة لحل الحالات صغيرة الحجم من المشكلة، وتعتبر من أسهل الاستراتيجيات في التطبيق.
Brute force is a straightforward approach to solving a problem, based on the problem statement and definitions of the concepts involved.
Generally, it is inefficient but can be useful for solving small-size instances of a problem.
It is one of the easiest strategies to implement.
تُستخدم القوة الغاشمة كخط أساس (Baseline) لقياس أداء الخوارزميات الأكثر تعقيداً.
التطبيق الأول لهذه الاستراتيجية غالباً ما ينتج خوارزمية يمكن تحسينها بجهد بسيط.
Brute force serves as a baseline for algorithm performance.
A first application of the brute-force approach often results in an algorithm that can be improved with a modest amount of effort.
It guarantees correctness by exploring all possibilities.
متى يكون استخدام القوة الغاشمة الخيار الأفضل رغم عدم كفاءتها؟ When is using brute force the best choice despite its inefficiency?
عندما يكون حجم المدخلات صغيراً جداً بحيث لا يبرر تعقيد كتابة خوارزمية متقدمة، أو عندما نحتاج إلى حل مرجعي (Baseline) لاختبار صحة خوارزميات أخرى.
When the input size is very small, making the overhead of a complex algorithm unjustified, or when a simple baseline is needed to verify the correctness of more advanced algorithms.
2 ترتيب الاختيار
2 Selection Sort
يبدأ ترتيب الاختيار بمسح القائمة بأكملها للعثور على أصغر عنصر وتبديله مع العنصر الأول.
ثم يمسح القائمة بدءاً من العنصر الثاني للعثور على أصغر عنصر بين العناصر المتبقية (n-1) ويبدله مع العنصر الثاني.
بشكل عام، في التمريرة i، تبحث الخوارزمية عن أصغر عنصر بين آخر (n-i) عناصر وتبدله مع A[i].
Selection sort starts by scanning the entire given list to find its smallest element and exchange it with the first element.
Then it scans the list starting with the second element to find the smallest among the last n-1 elements and exchanges it with the second element.
Generally, on the ith pass, it searches for the smallest item among the last n-i elements and swaps it with A[i].
العملية الأساسية هي مقارنة المفاتيح A[j] < A[min].
عدد مرات تنفيذها يعتمد فقط على حجم المصفوفة ولا يتأثر بحالة المصفوفة (مرتبة أم لا)، مما يجعل تعقيدها الزمني دائماً O(n^2).
The basic operation is the key comparison A[j] < A[min].
The number of times it is executed depends only on the array size, making it an O(n^2) algorithm on all inputs, regardless of whether the array is already sorted or reverse sorted.
ALGORITHM SelectionSort(A[0..n-1])
for i <- 0 to n-2 do
min <- i
for j <- i+1 to n-1 do
if A[j] < A[min] min <- j
swap A[i] and A[min]
هل ترتيب الاختيار خوارزمية مستقرة (Stable)؟ Is Selection Sort a stable sorting algorithm?
لا، ترتيب الاختيار غير مستقر لأن عملية التبديل قد تغير الترتيب النسبي للعناصر المتساوية.
No, Selection Sort is generally not stable because the swapping step can change the relative order of equal elements.
3 الترتيب الفقاعي
3 Bubble Sort
يقوم الترتيب الفقاعي بمقارنة العناصر المتجاورة في القائمة وتبديلها إذا كانت في غير ترتيبها الصحيح.
بتكرار هذه العملية، يرتفع ('bubbles up') العنصر الأكبر إلى الموضع الأخير في القائمة.
التمريرة التالية ترفع ثاني أكبر عنصر، وهكذا حتى يتم ترتيب القائمة بعد n-1 تمريرة.
Compare adjacent elements of the list and exchange them if they are out of order.
By doing it repeatedly, we end up 'bubbling up' the largest element to the last position on the list.
The next pass bubbles up the second largest element, and so on, until after n-1 passes the list is sorted.
عدد المقارنات في أسوأ الحالات (مصفوفة تنازلية) هو نفسه في ترتيب الاختيار O(n^2).
ومع ذلك، يمكن تحسين الترتيب الفقاعي ليتوقف مبكراً إذا لم تحدث أي تبديلات في تمريرة معينة، مما يعني أن القائمة أصبحت مرتبة.
The number of key comparisons is almost identical to selection sort, resulting in O(n^2) complexity in the worst case.
However, Bubble Sort can be optimized to stop early if a pass completes without any swaps, improving its best-case time complexity to O(n).
ALGORITHM BubbleSort(A[0..n-1])
for i <- 0 to n-2 do
for j <- 0 to n-2-i do
if A[j+1] < A[j] swap A[j] and A[j+1]
| Selection Sort | Bubble Sort | |
|---|---|---|
| آلية العملMechanism | يبحث عن الأصغر ويضعه في البدايةFinds minimum and places it at the beginning | يقارن المتجاورين ويرفع الأكبر للنهايةCompares adjacent and bubbles largest to the end |
| عدد التبديلات (Swaps)Number of Swaps | تبديل واحد لكل تمريرة O(n)One swap per pass O(n) | تبديلات متعددة لكل تمريرة O(n^2)Multiple swaps per pass O(n^2) |
لماذا يقل عدد المقارنات الداخلية في كل تمريرة في الترتيب الفقاعي؟ Why does the number of inner comparisons decrease with each pass in Bubble Sort?
لأن بعد كل تمريرة، يتم وضع أكبر عنصر في مكانه الصحيح في نهاية القائمة، فلا داعي لمقارنته مرة أخرى في التمريرات اللاحقة.
Because after each pass, the largest unsorted element is placed in its correct final position at the end of the array, so it doesn't need to be compared again.
4 البحث المتسلسل
4 Sequential Search
تقارن الخوارزمية المتسلسلة العناصر المتتالية لقائمة معينة بمفتاح بحث حتى يتم العثور على تطابق (بحث ناجح) أو استنفاد القائمة دون العثور على تطابق (بحث غير ناجح).
يمكن تحسين الخوارزمية بإضافة مفتاح البحث إلى نهاية القائمة (كحارس Sentinel) لإلغاء الحاجة للتحقق من نهاية القائمة في كل تكرار.
The sequential algorithm compares successive elements of a given list with a given search key until either a match is encountered (successful search) or the list is exhausted without finding a match (unsuccessful search).
Appending the search key to the end of the list (as a sentinel) eliminates the end-of-list check altogether.
تحسين آخر: إذا كانت القائمة مرتبة، يمكن إيقاف البحث بمجرد مواجهة عنصر أكبر من أو يساوي مفتاح البحث، مما يقلل وقت البحث غير الناجح.
Another enhancement is sorting the list.
This allows searching to be stopped as soon as an element greater than or equal to the search key is encountered, improving the average time for unsuccessful searches.
ALGORITHM SequentialSearch2(A[0..n], K)
A[n] <- K
i <- 0
while A[i] != K do
i <- i + 1
if i < n return i
else return -1
كيف يحسن 'الحارس' (Sentinel) من أداء البحث المتسلسل؟ How does a 'sentinel' improve the performance of Sequential Search?
يقلل من عدد العمليات داخل حلقة while بإزالة شرط التحقق من الوصول لنهاية المصفوفة (i < n)، مما يسرع التنفيذ الفعلي رغم أن التعقيد الزمني يبقى O(n).
It reduces the number of operations inside the while loop by eliminating the boundary check (i < n), speeding up the actual execution time even though the asymptotic complexity remains O(n).
5 مطابقة السلاسل النصية بالقوة الغاشمة
5 Brute-Force String Matching
المشكلة: إيجاد سلسلة فرعية في نص (طوله n) تطابق نمطاً (طوله m).
الخوارزمية تضع النمط فوق بداية النص وتقارن الحروف.
إذا حدث عدم تطابق، يتم إزاحة النمط بمقدار حرف واحد إلى اليمين وتتكرر العملية.
الهدف هو إيجاد الفهرس i لأول حرف في النص يبدأ منه التطابق.
Problem: For a given text of n characters and a pattern of m characters, find a substring of the text that matches the pattern.
The algorithm aligns the pattern with the beginning of the text and compares characters.
If a mismatch occurs, it shifts the pattern one position to the right.
It aims to find index i such that t_i...t_{i+m-1} = p_0...p_{m-1}.
في أسوأ الحالات، قد تضطر الخوارزمية لإجراء m مقارنة قبل إزاحة النمط، ويحدث هذا لكل محاولة من (n-m+1) محاولة.
التعقيد في أسوأ حالة هو O(nm).
أما في النصوص العشوائية، فالكفاءة المتوسطة تكون خطية O(n) لأن الإزاحة تحدث غالباً بعد مقارنة حرف واحد.
Worst case: The algorithm makes all m comparisons before shifting, happening for each of n-m+1 tries.
Worst-case complexity is O(nm).
However, for random texts, it shifts almost always after a single character comparison, making the average-case efficiency linear, O(n).
ALGORITHM BruteForceStringMatch(T[0..n-1], P[0..m-1])
for i <- 0 to n-m do
j <- 0
while j < m and P[j] == T[i+j] do
j <- j + 1
if j == m return i
return -1
متى تحدث أسوأ حالة في مطابقة السلاسل النصية بالقوة الغاشمة؟ أعط مثالاً. When does the worst-case scenario occur in brute-force string matching? Give an example.
تحدث عندما تتطابق جميع الحروف باستثناء الحرف الأخير في النمط. مثال: النص 'AAAAAAAAAB' والنمط 'AAAB'.
It occurs when all characters match except the last one in the pattern. Example: Text 'AAAAAAAAAB' and Pattern 'AAAB'.
6 مشكلة أقرب زوج من النقاط
6 Closest-Pair Problem
المشكلة هي إيجاد أقرب نقطتين في مجموعة من n نقطة.
نهج القوة الغاشمة يحسب المسافة بين كل زوج من النقاط المتميزة ويجد الزوج ذو المسافة الأصغر.
لتجنب حساب المسافة لنفس الزوج مرتين، نأخذ في الاعتبار فقط أزواج النقاط (pi, pj) حيث i < j.
The problem is finding the two closest points in a set of n points.
The brute-force approach computes the distance between each pair of distinct points and finds a pair with the smallest distance.
To avoid computing the distance for the same pair twice, it considers only pairs (pi, pj) for which i < j.
العملية الأساسية هي حساب الجذر التربيعي (أو المسافة المربعة لتجنب تكلفة الجذر).
عدد مرات التنفيذ هو n(n-1)/2، مما يجعل التعقيد الزمني O(n^2).
تسريع الحلقة الداخلية يقلل وقت التشغيل بعامل ثابت فقط.
The basic operation is computing the Euclidean distance.
The number of times it is executed is n(n-1)/2, leading to an O(n^2) time complexity.
Speeding up the innermost loop (e.g., by not computing the square root) only decreases the running time by a constant factor.
ALGORITHM BruteForceClosestPair(P)
d <- infinity
for i <- 1 to n-1 do
for j <- i+1 to n do
d <- min(d, sqrt((x_i - x_j)^2 + (y_i - y_j)^2))
return d
كيف يمكن تحسين خوارزمية أقرب زوج دون تغيير التعقيد الزمني O(n^2)؟ How can the closest-pair algorithm be optimized without changing the O(n^2) complexity?
بتجنب حساب الجذر التربيعي (sqrt) ومقارنة مربع المسافات بدلاً من ذلك، لأن دالة الجذر التربيعي مكلفة حسابياً.
By avoiding the square root calculation and comparing the squared distances instead, since the square root function is computationally expensive.
7 البحث الشامل
7 Exhaustive Search
البحث الشامل هو ببساطة نهج القوة الغاشمة المطبق على المشكلات التوافقية (Combinatorial problems).
يقترح توليد كل عنصر من عناصر مجال المشكلة، واختيار العناصر التي تلبي جميع القيود، ثم إيجاد العنصر المطلوب (مثل العنصر الذي يحسن دالة الهدف).
Exhaustive search is simply a brute-force approach to combinatorial problems.
It suggests generating each and every element of the problem domain, selecting those of them that satisfy all the constraints, and then finding a desired element (e.g., the one that optimizes some objective function).
يتطلب تنفيذه عادةً خوارزمية لتوليد كائنات توافقية (مثل التباديل Permutations أو المجموعات الفرعية Subsets).
المشكلة الرئيسية هي الانفجار التوافقي (Combinatorial Explosion)، حيث ينمو عدد الحلول بشكل أسي أو عاملي، مما يجعله غير عملي للمدخلات الكبيرة.
Its implementation typically requires an algorithm for generating certain combinatorial objects (permutations, subsets).
The main drawback is the combinatorial explosion, making it impractical for all but very small values of n.
ما الفرق بين القوة الغاشمة والبحث الشامل؟ What is the difference between Brute Force and Exhaustive Search?
البحث الشامل هو حالة خاصة من القوة الغاشمة تُطبق تحديداً على المشكلات التوافقية التي تتطلب توليد التباديل أو المجموعات الفرعية.
Exhaustive search is a specific type of brute-force approach applied to combinatorial problems, involving the generation of permutations or subsets.
8 مشكلة البائع المتجول (TSP)
8 Traveling Salesman Problem (TSP)
تطلب المشكلة إيجاد أقصر جولة عبر مجموعة من n مدينة تزور كل مدينة مرة واحدة بالضبط قبل العودة إلى مدينة البداية.
يمكن نمذجتها بواسطة رسم بياني موزن، حيث تمثل الرؤوس المدن وأوزان الحواف تمثل المسافات.
المشكلة تعادل إيجاد أقصر 'دائرة هاميلتونية' (Hamiltonian circuit) في الرسم البياني.
The problem asks to find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started.
It can be modeled by a weighted graph.
The problem is equivalent to finding the shortest Hamiltonian circuit of the graph.
نهج البحث الشامل يولد جميع التباديل للمدن الوسيطة (n-1).
إجمالي عدد التباديل المطلوبة هو (n-1)! / 2 (بافتراض أن المسار العكسي له نفس التكلفة).
هذا النمو العاملي يجعل الخوارزمية غير عملية إلا لقيم n الصغيرة جداً.
The exhaustive search generates all permutations of n-1 intermediate cities.
The total number of permutations needed is 1/2 (n-1)! (assuming undirected edges).
This factorial growth makes the exhaustive-search approach impractical for all but very small values of n.
لماذا نقسم عدد التباديل على 2 في مشكلة البائع المتجول؟ Why do we divide the number of permutations by 2 in TSP?
لأن المسار (أ -> ب -> ج -> أ) له نفس طول المسار العكسي (أ -> ج -> ب -> أ) في الرسوم البيانية غير الموجهة، لذا نلغي التكرار.
Because a tour (e.g., A -> B -> C -> A) has the same length as its reverse (A -> C -> B -> A) in an undirected graph, so we eliminate duplicates.
9 مشكلة حقيبة الظهر
9 Knapsack Problem
بوجود n عنصر بأوزان وقيم معروفة، وحقيبة ظهر بسعة W، المطلوب إيجاد المجموعة الفرعية الأكثر قيمة من العناصر التي تتسع في الحقيبة.
نهج البحث الشامل يولد جميع المجموعات الفرعية (Subsets) الممكنة، يحسب الوزن الإجمالي لكل منها لتحديد المجموعات الممكنة (Feasible)، ثم يختار المجموعة ذات القيمة الأعلى.
Given n items of known weights and values, and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.
The exhaustive-search approach generates all subsets of the n items, computes the total weight of each to identify feasible subsets, and selects the one with maximum value.
عدد المجموعات الفرعية لمجموعة مكونة من n عنصر هو 2^n.
بالتالي، يؤدي البحث الشامل إلى خوارزمية بتعقيد O(2^n).
مشكلتا TSP وحقيبة الظهر هما من أشهر الأمثلة على مشكلات NP-hard.
The number of subsets of an n-element set is 2^n.
Thus, exhaustive search leads to an O(2^n) algorithm.
Both TSP and Knapsack are best-known examples of NP-hard problems, meaning no polynomial-time algorithm is known for them.
لماذا يعتبر البحث الشامل حلاً سيئاً لمشكلة حقيبة الظهر؟ Why is exhaustive search a bad solution for the Knapsack problem?
لأن التعقيد الزمني ينمو بشكل أسي (2^n). إذا كان لدينا 50 عنصراً، سنحتاج للتحقق من أكثر من كوادريليون مجموعة فرعية، وهو أمر مستحيل عملياً.
Because the time complexity grows exponentially (2^n). For just 50 items, it would require checking over a quadrillion subsets, making it practically impossible.
10 مشكلة التعيين
10 Assignment Problem
يوجد n شخص يجب تعيينهم لتنفيذ n وظيفة (شخص واحد لكل وظيفة).
التكلفة C[i,j] معروفة لتعيين الشخص i للوظيفة j.
المشكلة هي إيجاد تعيين بأقل تكلفة إجمالية.
الحلول الممكنة تمثل كـ n-tuples (j1, ..., jn) حيث يشير المكون i إلى الوظيفة المعينة للشخص i.
There are n people who need to be assigned to execute n jobs, one person per job.
The cost C[i,j] if the ith person is assigned to the jth job is known.
The problem is to find an assignment with the minimum total cost.
Feasible solutions are represented as n-tuples (j1, ..., jn).
يوجد تطابق واحد لواحد بين التعيينات الممكنة وتباديل الأعداد الصحيحة n الأولى.
نهج البحث الشامل يتطلب توليد جميع التباديل (n!)، حساب التكلفة لكل تعيين، واختيار الأقل تكلفة.
التعقيد الزمني هو O(n!).
There is a one-to-one correspondence between feasible assignments and permutations of the first n integers.
Exhaustive search requires generating all n! permutations, computing the total cost for each, and selecting the minimum.
The time complexity is O(n!).
هل يمكن حل مشكلة التعيين بكفاءة أكبر من O(n!)؟ Can the Assignment Problem be solved more efficiently than O(n!)?
نعم، باستخدام الخوارزمية المجرية (Hungarian Algorithm) التي تحل المشكلة في وقت كثير الحدود O(n^3).
Yes, using the Hungarian Algorithm, which solves the problem in polynomial time O(n^3).
11 البحث في العمق أولاً (DFS)
11 Depth-First Search (DFS)
يبدأ DFS عند رأس عشوائي ويضع علامة 'تمت الزيارة'.
في كل تكرار، ينتقل إلى رأس غير مزور مجاور للرأس الحالي.
تستمر العملية حتى الوصول إلى 'طريق مسدود' (رأس ليس له جيران غير مزورين).
عندئذ، تتراجع الخوارزمية (backs up) حافة واحدة للوراء وتحاول زيارة رؤوس أخرى.
تستخدم الخوارزمية بنية المكدس (Stack) لتتبع المسار.
DFS starts at an arbitrary vertex, marking it as visited.
On each iteration, it proceeds to an unvisited adjacent vertex.
This continues until a dead end (a vertex with no adjacent unvisited vertices) is encountered.
At a dead end, it backs up one edge to the vertex it came from and tries to continue.
It uses a Stack data structure.
كفاءة DFS تعتمد على بنية البيانات المستخدمة لتمثيل الرسم البياني.
إذا استخدمنا مصفوفة التجاور (Adjacency Matrix)، يكون التعقيد O(|V|^2).
وإذا استخدمنا قائمة التجاور (Adjacency List)، يكون التعقيد O(|V| + |E|).
ينتج عن DFS غابة (Forest) تتكون من حواف شجرية (Tree edges) وحواف خلفية (Back edges).
Efficiency depends on the graph representation.
For an adjacency matrix, traversal time is O(|V|^2).
For an adjacency list, it is O(|V| + |E|).
DFS yields a spanning forest comprising tree edges and back edges, useful for detecting cycles.
ALGORITHM DFS(G)
count <- 0
for each vertex v in V do
if v is marked with 0
dfs(v)
dfs(v)
count <- count + 1; mark v with count
for each vertex w in V adjacent to v do
if w is marked with 0
dfs(w)
كيف يساعد DFS في اكتشاف الدورات (Cycles) في الرسم البياني؟ How does DFS help in detecting cycles in a graph?
إذا واجه DFS أثناء اجتيازه 'حافة خلفية' (Back edge) تشير إلى رأس تمت زيارته مسبقاً ولا يزال في المكدس، فهذا يعني وجود دورة.
If DFS encounters a 'back edge' pointing to an already visited ancestor node currently in the recursion stack, it indicates the presence of a cycle.
12 البحث في العرض أولاً (BFS)
12 Breadth-First Search (BFS)
يتقدم BFS بطريقة متحدة المركز، حيث يزور أولاً جميع الرؤوس المجاورة لرأس البداية، ثم جميع الرؤوس غير المزورة التي تبعد حافتين، وهكذا.
من المريح استخدام طابور (Queue - FIFO).
في كل تكرار، تحدد الخوارزمية جميع الرؤوس غير المزورة المجاورة للرأس الأمامي، تضع علامة عليها، وتضيفها للطابور، ثم تزيل الرأس الأمامي.
BFS proceeds in a concentric manner by visiting first all vertices adjacent to a starting vertex, then all unvisited vertices two edges apart, and so on.
It uses a queue (FIFO).
On each iteration, it identifies all unvisited vertices adjacent to the front vertex, marks them, adds them to the queue, and then removes the front vertex.
يمتلك BFS نفس الكفاءة الزمنية لـ DFS: O(|V|^2) لمصفوفة التجاور، و O(|V| + |E|) لقائمة التجاور.
يضيف الطابور ترتيباً واحداً للرؤوس.
ينتج عن BFS غابة (Forest) تتكون من حواف شجرية وحواف متقاطعة (Cross edges).
BFS has the same time efficiency as DFS: O(|V|^2) for adjacency matrix and O(|V| + |E|) for adjacency list.
The FIFO queue structure adds a single ordering of vertices.
BFS is particularly useful for finding the shortest path in unweighted graphs.
bfs(v)
count <- count + 1; mark v with count and initialize a queue with v
while the queue is not empty do
for each vertex w in V adjacent to the front vertex do
if w is marked with 0
count <- count + 1; mark w with count
add w to the queue
remove the front vertex from the queue
| Depth-First Search (DFS) | Breadth-First Search (BFS) | |
|---|---|---|
| بنية البيانات المستخدمةData Structure Used | المكدس (Stack - LIFO)Stack (LIFO) | الطابور (Queue - FIFO)Queue (FIFO) |
| طريقة الاستكشافExploration Method | التعمق في مسار واحد حتى النهاية ثم التراجعGo deep into a path until dead end, then backtrack | استكشاف متمركز (مستوى بمستوى)Concentric exploration (level by level) |
| التعقيد الزمني (قائمة التجاور)Time Complexity (Adjacency List) | O(|V| + |E|)O(|V| + |E|) | O(|V| + |E|)O(|V| + |E|) |
لماذا يُفضل BFS على DFS لإيجاد أقصر مسار في رسم بياني غير موزن؟ Why is BFS preferred over DFS for finding the shortest path in an unweighted graph?
لأن BFS يستكشف الرؤوس مستوى بمستوى، فأول مرة يصل فيها إلى رأس معين، يكون قد سلك أقصر مسار ممكن إليه (بأقل عدد من الحواف).
Because BFS explores vertices level by level, the first time it reaches a vertex, it is guaranteed to have found the shortest path (minimum number of edges) to it.