Graphs: الأساسيات و BFS و DFSnodes · edges · adjacency list · visited · BFS · DFS · connected components
الـ graph هو أقرب data structure للدنيا الحقيقية: محطات مترو، صحاب على فيسبوك، مواد ليها prerequisites، data centers متوصلة بكابلات. هنبدأ من الصفر خالص، لحد ما تكتب BFS و DFS من دماغك وتحل مسائل زي اللي بتيجي في الـ online assessments.
هتطلع من الفصل ده وإنت عارف
- يعني إيه node و edge و directed و weighted و degree و path و cycle و component، وتشوفهم مرسومين قدامك.
- تحوّل الـ edges اللي في المسألة لـ adjacency list في 5 سطور، وتعرف إمتى تستخدم adjacency matrix.
- ليه الـ
visitedلازم، وليه بنعلّم الـ node وقت الـ push مش وقت الـ pop. - تكتب BFS و DFS (recursive و iterative) من دماغك، وتفهم ليه الـ BFS بيدّي أقصر مسافة.
- تعدّ الـ connected components (مسألة تقسيم الـ data centers لـ regions)، وتعرف ليه الـ complexity هي O(V + E).
- تعمل BFS على states زي مسألة (a, b) اللي جت في الاختبار، وتعرف الـ trick بتاع إنك تمشي لورا.
ليه Graphs؟
في الـ trees كانت الدنيا منظمة: فيه root، وكل node ليها parent واحد بس، ومفيش أي دواير. والـ heap كانت tree برضه بس متخزنة في array. دلوقتي هنشيل القواعد دي كلها.
بص على خريطة مترو القاهرة. كل محطة نقطة، وكل خط بين محطتين معناه إن فيه قطر مباشر بينهم. محطة التبادل متوصلة بأكتر من خط، وفيه أكتر من طريق بين أي محطتين، وممكن تلف وترجع لنفس المحطة. مفيش root ومفيش "أب". ده اسمه graph: نقط اسمها nodes، وخطوط بينها اسمها edges.
والـ graph موجود في حاجات كتير بتستخدمها كل يوم:
- فيسبوك: كل شخص node، وكل صداقة edge. الـ "People you may know" هي صحاب صحابك، يعني nodes على بُعد 2 منك.
- مواد الكلية: كل مادة node، ولو مادة محتاجة مادة قبلها يبقى فيه edge ليها اتجاه، من الأساسية للمتقدمة.
- Google Maps: التقاطعات nodes والشوارع edges، وكل شارع ليه وقت. الوقت ده اسمه weight.
- الاختبار بتاعك: data centers متوصلة ببعض بكابلات، والمطلوب تقسّمها لـ regions. كل data center node، وكل كابل edge، وكل region حتة متوصلة ببعضها.
شوفها على مترو صغير فيه 6 محطات. الرقم اللي تحت كل محطة هو عدد المحطات من محطة 0:
كل طبقة فيها المحطات اللي على نفس المسافة. ولاحظ إن محطة 3 ليها طريقين (من 1 ومن 2)، بس اتحسبت مرة واحدة. الحتة دي بالذات هي اللي بتفرق بين كود شغال وكود بيلف للأبد.
طب إزاي تعرف إن المسألة اللي قدامك graph أصلًا، وهي ساعات ما بتقولش كلمة graph خالص؟
إزاي تعرفه من المسألة
أغلب مسائل الـ graph ما بتقولش "graph". بتقول كلام زي ده:
الـ key insight: لو عندك حاجات، وفيه علاقة بين كل اتنين منهم، يبقى عندك graph، حتى لو المسألة ما رسمتش ولا نقطة. الحاجات هي الـ nodes والعلاقة هي الـ edges. مسألة (a, b) اللي في الاختبار مثال حلو: مفيش أي رسمة، بس كل state زي (2, 3) هي node، وكل حركة مسموحة هي edge.
| السؤال في المسألة | الأداة | فين |
|---|---|---|
| فيه طريق من A لـ B؟ أقدر أوصل لكل الأماكن؟ | BFS أو DFS | هنا (مثال 1 و 3) |
| كام group / region / province؟ | Connected components | هنا (مثال 2)، و DSU في Graphs المتقدمة |
| أقل عدد moves أو steps؟ | BFS (طبقات) | هنا (مثال 5) |
| جزر، خريطة، maze | BFS / DFS على grid | Graphs على Grid |
| ترتيب مهام ليها dependencies | Topological sort | Graphs المتقدمة |
| أقصر طريق بأوزان (وقت، فلوس) | Dijkstra | Graphs المتقدمة |
flowchart TD
A["Things + a relation between pairs?"] -- yes --> B{"Laid out as a 2D grid?"}
A -- no --> Z["Probably not a graph problem"]
B -- yes --> G["Grid BFS / DFS"]
B -- no --> C{"What is asked?"}
C -- "reachable? visit all?" --> R["BFS or DFS"]
C -- "how many groups?" --> K["Connected components"]
C -- "fewest moves, no weights" --> S["BFS layers"]
C -- "order with dependencies" --> T["Topological sort"]
C -- "cheapest path with weights" --> D["Dijkstra"]
الأسئلة دي بالترتيب ده بتوصّلك للأداة في أغلب المسائل.
قبل ما نحل أي حاجة، لازم نتفق على الكلمات: node و edge و degree و path و cycle… دي هتقابلك في كل مسألة.
القاموس: الكلمات اللي هتسمعها
كل كلمة هنا معناها بسيط جدًا. الجدول بيقولها، والـ animation تحت بترسمها واحدة واحدة على نفس المترو.
| الكلمة | معناها | في المترو |
|---|---|---|
| node (أو vertex) | نقطة في الـ graph | محطة |
| edge | خط بيوصل بين اتنين nodes | قطر مباشر بين محطتين |
| undirected | الـ edge شغالة في الاتجاهين | القطر رايح جاي |
| directed | الـ edge ليها اتجاه واحد (سهم) | شارع one-way، أو follow على تويتر |
| weighted | كل edge عليها رقم: وقت، مسافة، فلوس | عدد الدقايق بين محطتين |
| neighbors | الـ nodes اللي بينها وبين node معيّنة edge مباشرة | المحطات اللي تروحها من غير ما تقف في النص |
| degree | عدد الـ neighbors | عدد الخطوط الطالعة من المحطة |
| path | سلسلة nodes، كل اتنين ورا بعض بينهم edge | رحلة من محطة لمحطة |
| cycle | path بيرجع لنفس الـ node اللي بدأ منها | لفة وترجع مكانك |
| connected | من أي node تقدر توصل لأي node تانية | كل المحطات على شبكة واحدة |
| component | حتة متوصلة ببعضها ومقطوعة عن الباقي | شبكة مترو في مدينة تانية |
هنكتب V لعدد الـ nodes و E لعدد الـ edges. في المترو ده V = 6 و E = 7. وخلي في بالك الحسبة دي عشان هنحتاجها في الـ complexity: لو جمعت الـ degrees كلها، كل edge بتتعد مرتين (مرة من كل طرف)، فالمجموع دايمًا 2E.
تمام، فهمنا الرسمة. بس الكمبيوتر ما بيشوفش رسومات. إزاي نخزّن الـ graph في الكود؟
إزاي تخزّن الـ graph في الكود
1. Edge list: اللي المسألة بتديهولك
أغلب المسائل بتديك الـ graph كـ list of edges: كل edge عبارة عن array فيها رقمين.
المشكلة: الـ BFS هيسأل طول الوقت "مين جيران الـ node دي؟". ومع edge list بس، كل سؤال هيلف على كل الـ edges، يعني O(E) للسؤال الواحد. محتاجين شكل يجاوب السؤال ده على طول.
2. Adjacency list: لكل node لستة جيرانها
بنعمل array اسمها adj فيها خانة لكل node، وكل خانة فيها array بجيران الـ node دي. بعدها adj[3] بتديك جيران 3 على طول. ده الشكل اللي هتستخدمه في 90% من المسائل.
- بنعمل
narrays فاضية، واحدة لكل node. الـArray.fromبتنادي الـ arrow function مرة لكل خانة، فكل node بتاخد array جديدة. أوعىnew Array(n).fill([])، دي بتحط نفس الـ array في كل الخانات (الغلطة 2 تحت). - الـ destructuring
[u, v]بيفك كل edge لطرفينها. أوضح منe[0]وe[1]. - الـ graph undirected، فالـ edge معناها إن v جار لـ u و u جار لـ v. لو نسيت السطر 5، الـ traversal هيمشي في اتجاه واحد ويفوّت nodes. ولو المسألة قالت directed، بتشيل السطر 5.
- الـ memory هنا
narrays مجموع أطوالها2E، يعني O(V + E).
شوف الـ adj وهي بتتبني edge ورا edge:
3. Adjacency matrix: جدول n × n
الشكل التاني جدول: matrix[u][v] = 1 لو فيه edge بين u و v، و 0 لو مفيش. الصف رقم u هو "مين متوصل بـ u".
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Memory | O(V + E) | O(V²) |
| u و v متوصلين؟ | O(degree): تدوّر في adj[u] | O(1): matrix[u][v] |
| هات جيران u | O(degree): بالظبط اللي محتاجه | O(V): لازم تلف على الصف كله |
| BFS / DFS كامل | O(V + E) | O(V²) |
| تستخدمه إمتى | تقريبًا دايمًا | لما المسألة تديهولك جاهز (زي مثال 2)، أو n صغير |
ليه الـ list بتكسب؟ لأن أغلب الـ graphs الحقيقية sparse: كل node ليها كام جار بس. فيسبوك فيه مليارات أشخاص، وكل واحد صحابه بالمئات. الـ matrix هتحجز مليار × مليار خانة، أغلبها أصفار.
4. الـ grid كمان graph
خريطة مقسومة مربعات (زي مسائل الجزر والـ maze) هي graph مستخبي: كل خانة node، وجيرانها اللي فوقها وتحتها وشمالها ويمينها. مش محتاج تبني adj خالص، بتحسب الجيران وإنت ماشي.
ده موضوع الفصل الجاي كله. ونفس الفكرة، "الجيران بتتحسب مش بتتخزن"، هترجعلك في مثال 5 مع الـ states.
دلوقتي عندنا adj. أول ما تيجي تلف عليها هتقع في فخ: الـ graph فيه دواير. إيه اللي هيحصل؟
ليه لازم visited؟
في الـ tree، لما بتنزل من node لولادها عمرك ما بترجع لفوق، لأن مفيش edge بترجعك. في الـ graph، الـ edge بين 0 و 1 شغالة في الاتجاهين: من 0 تروح 1، ومن 1 ترجع 0، ومن 0 تروح 1… للأبد.
جرّب BFS زي بتاع الـ trees بالظبط، من غير أي visited، على المترو بتاعنا. الرقم تحت كل محطة هو عدد المرات اللي دخلت فيها الـ queue:
الـ queue عمره ما هيفضى. ده infinite loop، والـ memory هتخلص قبل الوقت.
الحل إننا نعلّم كل node بعد ما نشوفها، وما ندخلهاش الـ queue تاني. بس إمتى بالظبط نعلّمها؟ أول حاجة بتيجي في الدماغ: لما نطلّعها من الـ queue (pop). جرّب:
10 pops لـ 6 nodes. محطة 3 دخلت الـ queue مرتين، لأن 1 و 2 الاتنين شافوها قبل ما حد يطلّعها ويعلّمها، ونفس الكلام حصل لـ 4 و 5. ولو الكود بيعدّ حاجة (nodes، مساحة جزيرة)، هيعدّها مرتين. وفي graph كبير الـ queue بيتملي نسخ مكررة.
كده معانا كل القطع: adj و queue و visited. يلا نركّبهم مع بعض في BFS كامل.
BFS: دواير بتكبر حوالين البداية
الـ BFS (Breadth-First Search) بيزور الـ nodes طبقة طبقة: البداية، وبعدين كل اللي على بُعد 1، وبعدين كل اللي على بُعد 2… والأداة اللي بتضمن الترتيب ده هي الـ queue: أول واحد يدخل أول واحد يطلع. ده نفس الـ level order اللي عملته في الـ trees، زائد الـ visited.
- في الأول محدش اتشاف، فكله
false. - الـ
distبيبدأ-1مش 0، لأن 0 معناها "دي البداية". لو node فضلت-1في الآخر يبقى مفيش طريق ليها. - البداية بتدخل الـ queue وبتتعلّم في نفس اللحظة. أول تطبيق للقاعدة: mark on push.
- الـ
headهو index أول واحد في الطابور. بدلqueue.shift()اللي بتزق كل العناصر خطوة لقدام (O(n) كل مرة)، بنحرّك الـ index بس، O(1). head < queue.lengthمعناها "لسه فيه ناس في الطابور".<مش<=، لأن لماheadيساوي الطول يبقى مفيش عنصر عند الـ index ده.queue[head++]: خد العنصر اللي عندhead، وبعدين زوّدhead. الـ++بعد الاسم معناها "استخدم القيمة القديمة الأول".- بنلف على جيران
uبس، مش على كل الـ nodes. ده اللي هيخلّي الـ complexity O(V + E). - لو
vجديدة: نعلّمها، ومسافتها مسافةuزائد 1، وندخلها الطابور. التلاتة مع بعض. ولو visited، يا اتعالجت يا واقفة في الطابور بمسافة أحسن أو قدها، فمش هنلمسها. - لو محتاج reachability بس، الـ
visitedكفاية والـdistزيادة. بس هي ببلاش: نفس اللفة بتجاوب "أقل عدد edges" لكل node.
شوفه على المترو. الـ node اللي برواز متقطع واقفة في الـ queue، والصفرا هي u اللي بنعالجها، والـ teal خلصت. الرقم تحت كل node هو الـ dist، وراقب العدّادين pops و edgeChecks:
ليه أول وصول لـ node يبقى أقصر مسافة؟
بص على الـ queue في الـ animation: في أي لحظة فيه nodes من طبقة d وبعدها nodes من طبقة d + 1 بس، عمرهم ما بيتلخبطوا. ليه؟ كل node من طبقة d بتزق جيرانها في آخر الطابور، ورا كل اللي من طبقتها. فالطبقة d كلها بتطلع قبل أي حد من d + 1. يعني أول مرة نشوف node، بنشوفها من أقرب طبقة ممكنة، وده أقصر طريق.
ولو عايز الطريق نفسه مش طوله بس، خزّن لكل node مين اللي اكتشفها، وارجع بيها لورا من الهدف:
BFS من 0 على المترو (adj[0] = [1, 2]، adj[1] = [0, 3]، adj[2] = [0, 3]، adj[3] = [1, 2, 4, 5]). بأي ترتيب الـ nodes بتطلع من الـ queue؟
- 0, 1, 3, 2, 4, 5
- 0, 1, 2, 3, 4, 5
- 0, 1, 3, 4, 5, 2
- 0, 2, 1, 3, 5, 4
0 بتزق 1 و 2 بالترتيب ده. 1 بتطلع وتزق 3، و 2 بتطلع وتلاقي 3 visited. بعدها 3 تزق 4 و 5. الاختيار الأول ده ترتيب الـ DFS، هتشوفه في الجزء الجاي.
الـ BFS بيوسّع بالعرض، طبقة طبقة. طب لو عايز تغطس في طريق واحد لآخره قبل ما ترجع؟ ده DFS.
DFS: امشي لآخر الطريق وارجع
الـ DFS (Depth-First Search) بيمسك أول جار ويغطس فيه، ومن هناك أول جار، وهكذا لحد طريق مسدود. ساعتها بس يرجع خطوة ويجرّب الجار اللي بعده. الرجوع ده اسمه backtracking.
DFS بالـ recursion
الـ recursion مناسبة جدًا هنا: "زور u" معناها "علّمها، وبعدين زور كل جار مش متزار". والـ call stack هو اللي بيفتكرلك إنت جاي منين. لو محتاج تفتكر الـ recursion، ارجع لـ فصلها.
- الـ
dfsالداخلية شايفةvisitedوorderوadjمن غير ما نبعتهم، لأنها معمولة جوهdfsOrder(closure). - بنعلّم أول ما ندخل، قبل ما نلمس أي جار. ده المقابل لـ mark on push: أول ما قررنا نزور u، محدش يقدر يدخلها تاني.
- لكل جار مش visited بننادي
dfs(v)، والنداء ده مش بيرجع غير لما كل اللي ورا v يخلص. ده الغطس. - مفيش base case صريح زي
if (n === 0). الـ base case هنا ضمني: node كل جيرانها visited، فالـ loop ما بتناديش حاجة والـ function بترجع. - نقطة البداية. لو الـ graph متقطّع، النداء ده هيزور الـ component بتاعة
startبس.
الأصفر هو الـ node اللي فوق الـ call stack، والأزرق nodes لسه مستنية في الـ stack، والـ teal خلصت خالص:
لاحظ الترتيب: 0, 1, 3, 2, 4, 5. من 3 غطس في 2، مع إن 2 جارة لـ 0 مباشرة. الـ DFS ما بيهتمش بالمسافة خالص، عشان كده ما ينفعش يجاوب "أقصر طريق".
DFS بـ stack بإيدك
الـ recursion في JS ليها حد: حوالي 10 آلاف نداء جوه بعض، وبعدها بيضرب RangeError (Maximum call stack size exceeded). جرّبناها على سلسلة فيها 10⁵ node ووقعت. الحل: stack عادية بدل الـ call stack. والكود هو الـ BFS تقريبًا، بس pop() بدل queue[head++]:
- نفس بداية الـ BFS: البداية جوه ومتعلّمة.
pop()بتطلّع آخر واحد دخل (LIFO). ده الفرق الوحيد عن الـ BFS، وهو اللي بيخلّيه يغطس: آخر جار اتزق هو أول واحد يتزار. والـpopهنا O(1) لأنها من آخر الـ array، مش زيshift.- نفس الـ mark on push، فكل node بتدخل الـ stack مرة واحدة.
الترتيب هنا 0, 2, 3, 5, 4, 1، مختلف عن الـ recursive، لأن الـ stack بتطلّع آخر جار اتزق الأول. الاتنين DFS صح. وفي مسائل الـ reachability والـ components والعدّ، الترتيب مش فارق خالص.
الـ DFS بينفع في إيه؟
- Reachability و components: زيه زي الـ BFS، والـ recursive أقصر في الكتابة.
- كل الطرق الممكنة: زي "اطبع كل الـ paths من 0 لـ n - 1". ده backtracking، وهو DFS في الأصل.
- Cycle detection و topological sort في الـ directed graphs، في Graphs المتقدمة.
طب لما الاتنين بيزوروا نفس الـ nodes، إمتى تختار ده وإمتى ده؟
BFS ولا DFS؟
| BFS | DFS | |
|---|---|---|
| الأداة | queue (FIFO) + head | recursion، أو stack (LIFO) |
| الترتيب | طبقة طبقة، الأقرب الأول | يغطس لآخر الطريق ويرجع |
| أقصر طريق (من غير أوزان) | أيوه: أول وصول = أقل عدد edges | لأ |
| الـ memory | الـ queue ممكن يشيل طبقة كاملة (graph عريض) | قد عمق الطريق (graph طويل) |
| الكود | queue و head و while | الـ recursive أقصر كود ممكن |
| الخطر | shift() البطيئة | stack overflow في الـ recursion العميقة |
| بيكسب في | أقل عدد moves، أقرب حاجة، طبقات | كل الـ paths، backtracking، cycles، topo sort |
| Complexity | O(V + E) | O(V + E) |
الاتنين بيبدأوا من node واحدة وبيزوروا الحتة بتاعتها بس. طب لو الـ graph متقطّع حتت، زي الـ data centers في الاختبار؟
Connected Components: الـ graph متقطّع كام حتة؟
ارجع لمسألة الاختبار: شبكة data centers، بعضها متوصل ببعض بكابلات. الـ region هي مجموعة data centers تقدر توصل من أي واحد فيها لأي واحد تاني، ومقطوعة عن الباقي. يعني الـ region هي connected component، والمطلوب تعدّهم.
الـ BFS من node واحدة بيزور الـ component بتاعتها كلها وبس. فالفكرة: لف على كل الـ nodes بالترتيب. أي node لسه مش visited معناها إن محدش من الـ components اللي فاتت وصلها، يعني هي أول node في component جديدة. زوّد العدّاد، واعمل BFS منها يعلّم الـ component كلها.
- بنلف على كل الـ nodes. لو بدأت من 0 بس، أي component مفيهاش 0 هتضيع.
- node visited يعني اتعدّت مع component قبل كده، فبنعدّيها.
- العدّاد بيزيد هنا بس: node محدش وصلها = component جديدة.
- الـ BFS template بالظبط، بيعلّم الـ component كلها. ممكن تحط مكانه
dfs(s)والنتيجة واحدة. - node لوحدها من غير ولا edge بتتعد component برضه. خلي بالك منها في الاختبار.
كل component بتاخد لون:
الـ for الخارجية والـ while الداخلية شكلهم nested loops، بس ده مش O(V²). كل node بتدخل الـ queue مرة واحدة في البرنامج كله، مش مرة لكل s.
استنى، loop جوه loop وتطلع مش O(V²)؟ تعالى نعدّ العمليات واحدة واحدة.
ليه O(V + E)؟ بالعدّ
ارجع لـ animation الـ BFS وبص على العدّادين في آخر خطوة: pops = 6 و edgeChecks = 14. الرقمين دول جايين منين؟
- الشغل على الـ nodes: كل node بتدخل الـ queue مرة واحدة بالظبط (الـ visited ضامن ده)، وبتطلع مرة. يعني V push و V pop: O(V). المترو فيه 6 nodes، و 6 pops.
- الشغل على الـ edges: لما
uبتطلع، بنلف علىadj[u]، يعني degree(u) لفة. وكل node بتطلع مرة، فالمجموع = مجموع الـ degrees =2E. عندنا 7 edges، يعني 14 check. - المجموع:
V + 2E، يعني O(V + E). الـ inner loop مش بتلف E مرة كل مرة، بتلف degree(u) بس. عشان كده جمع مش ضرب. - ومع الـ matrix؟ "هات جيران u" = لف على صف كامل، يعني V لكل node، فالمجموع O(V²) مهما كانت الـ edges قليلة.
| V | E | Adjacency list: V + E | Matrix: V² |
|---|---|---|---|
| 1,000 | 5,000 | 6,000 | 1,000,000 |
| 100,000 | 200,000 | 300,000 | 10,000,000,000 (TLE) |
الـ memory: الـ adj نفسها O(V + E)، والـ visited والـ queue O(V). والـ DFS الـ recursive بياخد O(V) في الـ call stack في الـ worst case (سلسلة طويلة).
كده الأدوات كلها معاك. يلا نحل مسائل حقيقية، ونبدأ بأبسط سؤال ممكن: فيه طريق ولا لأ؟
مثال محلول 1: Find if Path Exists in Graph
عندك n nodes مترقمين من 0 لـ n - 1، ولستة undirected edges. هل فيه طريق من source لـ destination؟
نفكّر فيها مع بعض
- افهم المطلوب: مش عايزين الطريق ولا طوله، yes أو no بس. ده reachability.
- Brute force: تجرّب كل الطرق من source. عدد الطرق في graph فيه cycles ممكن يبقى exponential، ومن غير visited هيلف للأبد.
- الـ insight: السؤال الحقيقي "هل destination في نفس الـ component بتاعة source؟". BFS من source بيزور الـ component دي كلها في O(V + E).
- الخطة: نحوّل الـ edges لـ
adj، وبعدين الـ BFS template، ولو destination طلعت من الـ queue نعمل early return بـ true. - الحالات الطرفية:
source === destination، ومفيش edges خالص، و nodes لوحدها.
- نفس
buildAdjبالظبط، مكتوبة inline. في الاختبار اكتبها كده عادي. - الـ BFS template: البداية في الـ queue ومتعلّمة.
- بنشيك وقت الـ pop. كده حالة
source === destinationمتغطية من غير سطر زيادة، لأن source أول واحد بيطلع. - زي الـ template، من غير
distلأن السؤال yes/no. - الـ queue فضي ولسه ما شفناش destination، يبقى في component تانية.
نفس الكود مرتين: مرة لـ destination = 4، ومرة لـ 6:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| n=1, [], 0 → 0 | true | source هي destination، والشيك وقت الـ pop بيلقطها |
| n=3, [], 0 → 2 | false | مفيش edges خالص، الـ queue بيفضى بعد pop واحدة |
| [[0,1],[1,2],[2,0]], 0 → 2 | true | cycle، والـ visited بيمنع اللف حواليه |
| destination في حتة تانية | false | الـ BFS بيخلص من غير ما يشوفها |
التعقيد: بناء الـ adj O(E)، والـ BFS O(V + E). الـ memory O(V + E).
هنا الـ graph جالنا edges، والسؤال عن node واحدة. طب لو جالنا جدول، والسؤال "كام حتة"؟
مثال محلول 2: Number of Provinces (مسألة الـ data centers)
عندك n مدن وجدول isConnected مقاسه n × n: الخانة [i][j] بـ 1 لو المدينة i متوصلة مباشرة بالمدينة j. الـ province مجموعة مدن متوصلة ببعض، مباشرة أو عن طريق مدن تانية. رجّع عدد الـ provinces.
adj واستخدم كود الـ components اللي فوق زي ما هو.
نفكّر فيها مع بعض
- افهم المطلوب: كل province هي connected component. المطلوب عددهم.
- الجديد هنا: الـ graph جاي adjacency matrix مش edges. مش محتاجين نبني
adj: جيران u هما كل v في الصف u قيمتها 1. - الخطة: نفس كود الـ components، بالـ DFS الـ recursive عشان أقصر، والجيران من الصف.
- القطر:
isConnected[i][i]دايمًا 1 (المدينة متوصلة بنفسها). مش مشكلة، لأن i ساعتها visited فبنعدّيها. - الحالات الطرفية: مدينة واحدة، وكل المدن لوحدها، وكله متوصل.
- عدد المدن هو عدد الصفوف.
- نعلّم أول ما ندخل، زي الـ DFS template.
- بنلف على كل الأعمدة من 0 لـ
n - 1، يعني O(n) لكل مدينة حتى لو جيرانها قليلين. ده تمن الـ matrix. - شرطين مع بعض: فيه كابل، ولسه ما زرناهاش. لو نسيت
!visited[v]هتلف بين 0 و 1 لحد stack overflow. - نفس الـ for الخارجية بتاعة الـ components: مدينة مش visited = province جديدة.
فوق: الـ data centers ملوّنة بالـ region بتاعتها. في النص: الجدول، والصف اللي بنقراه أزرق. تحت: الـ call stack.
| Input | المتوقع | ليه |
|---|---|---|
| [[1]] | 1 | مدينة واحدة = province واحدة |
| identity 3 × 3 | 3 | مفيش كابلات، كل مدينة لوحدها |
| كله 1 | 1 | كله متوصل ببعض |
| [[1,1,0],[1,1,1],[0,1,1]] | 1 | 0 و 2 مش متوصلين مباشرة، بس عن طريق 1 |
التعقيد: كل مدينة بتتزار مرة، وبتلف على صف كامل: O(n²). ودي أحسن حاجة ممكنة، لأن قراية الـ input نفسه n². الـ memory O(n) للـ visited والـ call stack.
لحد دلوقتي الـ edges كانت رايح جاي. طب لو الـ edge ليها اتجاه واحد، والسؤال "أقدر أزور الكل"؟
مثال محلول 3: Keys and Rooms
عندك n أوض، كلها مقفولة ما عدا أوضة 0. جوه كل أوضة شوية مفاتيح، و rooms[i] هي أرقام الأوض اللي مفاتيحها جوه أوضة i. تقدر تدخل كل الأوض؟
نفكّر فيها مع بعض
- فين الـ graph؟ كل أوضة node. ولو مفتاح أوضة 3 جوه أوضة 1، يبقى فيه edge من 1 لـ 3.
- الجديد هنا: الـ graph directed (مفتاح 3 في أوضة 1 ما يعنيش إن مفتاح 1 في أوضة 3)، وجاي جاهز:
roomsهي نفسها الـ adjacency list. - السؤال: هل كل الـ nodes reachable من 0؟ traversal من 0 ونعدّ اللي فتحناه.
- الأداة: DFS بـ stack، عشان الترتيب مش فارق، وعشان نتمرن على الـ iterative.
- الحالات الطرفية: أوضة واحدة بس، وأوضة مفيهاش مفاتيح، ومفتاح لأوضة فتحناها قبل كده.
- بنبدأ من أوضة 0 لأنها الوحيدة المفتوحة.
countبيعدّ الأوض اللي فتحناها، وبيبدأ 1 عشان أوضة 0.rooms[room]هي جيران الأوضة دي. مفيشbuildAdjولا push في الاتجاه التاني، لأن المفتاح بيفتح في اتجاه واحد.- mark on push، والـ
countبيزيد مع الـ visited، فكل أوضة بتتعد مرة واحدة بالظبط. - فتحنا كل الأوض؟ ده أسرع من
visited.every(Boolean)لأنه O(1).
| Input | المتوقع | ليه |
|---|---|---|
| [[]] | true | أوضة واحدة ومفتوحة أصلًا |
| [[], [0]] | false | مفتاح 0 جوه 1، بس 1 نفسها مقفولة. الاتجاه فارق |
| [[1], [2], [3], []] | true | سلسلة: كل أوضة فيها مفتاح اللي بعدها |
التعقيد: كل أوضة بتدخل الـ stack مرة، وكل مفتاح بيتقري مرة: O(V + E)، و E هنا عدد المفاتيح كلها.
لحد دلوقتي كنا بنزور الـ graph بس. طب لو المطلوب نبني نسخة كاملة منه؟
مثال محلول 4: Clone Graph
معاك reference لـ node واحدة في graph متوصل و undirected. كل node فيها val ولستة neighbors. اعمل deep copy: nodes جديدة خالص بنفس الـ vals ونفس التوصيلات، ورجّع نسخة الـ node اللي اتدّتلك.
نفكّر فيها مع بعض
- deep copy معناها إن كل node جديدة، والـ neighbors بتاعتها بتشاور على الـ nodes الجديدة مش القديمة.
- المشكلة: الـ cycles. لو نسخت 1، فنسخت جارها 2، فنسخت جارها 1… نسخ لا نهائية. محتاجين نفتكر "الـ node دي اتنسخت قبل كده؟".
- الجديد هنا: الـ visited بقى
Mapمن القديم للجديد. وجود الـ key معناه visited، والـ value هي النسخة نفسها، اللي محتاجينها عشان نوصّل الـ neighbors. - الخطة: BFS. أول ما نشوف node: نعمل نسختها ونحطها في الـ Map ونزقها. ولكل جار: نضيف نسخة الجار لـ neighbors نسخة الـ node الحالية.
- الحالات الطرفية:
node === null، و node لوحدها من غير جيران.
- graph فاضي، نرجّع
null. وعلى LeetCode الـ class اسمها_NodeمشNode، غيّر الاسم بس. Mapمش object عادي، لأن الـ keys هنا objects. الـ object العادي بيحوّل أي key لـ string، فكل الـ nodes هتبقى نفس الـ key"[object Object]".- نسخة البداية تدخل الـ Map، والبداية تدخل الـ queue. ده الـ mark on push.
- أول مرة نشوف
nb: نعمل نسختها ونحطها في الـ Map قبل الـ push. الـ Map هنا هي الـ visited بالظبط. - أهم سطر، وهو برا الـ if: لازم نوصّل الـ edge حتى لو
nbاتنسخت قبل كده. لو دخّلته جوه الـ if، الـ edges اللي بتقفل cycle (زي 2-3) هتضيع. - نرجّع النسخة، مش الأصل. لو رجّعت
nodeالـ judge هيقول إنك ما نسختش.
الأصل على الشمال، والنسخ (بشرطة ') بتتولد على اليمين وبتتوصل edge ورا edge:
| Input | المتوقع | ليه |
|---|---|---|
| null | null | السطر 2 |
| node لوحدها | node جديدة، neighbors فاضية | الـ for مش بتلف خالص |
| 1-2 بس | نسختين، كل واحدة بتشاور على التانية | السطر 14 بيشتغل مرتين، مرة من كل ناحية |
| مثلث 1-2-3 | مثلث جديد | الـ Map بتمنع النسخ اللا نهائي |
التعقيد: كل node بتتنسخ مرة، وكل edge بتتوصّل مرتين (مرة من كل طرف): O(V + E). والـ memory O(V) للـ Map والـ queue.
في كل اللي فات كان فيه graph موجود قدامنا: edges، أو matrix، أو rooms، أو nodes. طب لو مفيش graph خالص، والـ nodes بتتولد وإنت ماشي؟
مثال محلول 5: BFS على states (مسألة (a, b) من الاختبار)
معاك رقمين (a, b). في كل خطوة تقدر تعمل حاجة من اتنين: تزوّد التاني على الأول فتبقى (a + b, b)، أو تزوّد الأول على التاني فتبقى (a, b + a). هل تقدر توصل لـ (c, d)؟ كل الأرقام موجبة.
نفكّر فيها مع بعض
- فين الـ graph؟ كل state زي
(2, 1)هي node، وكل حركة مسموحة edge. الـ graph ده مش متخزن في أي حتة: بنولّد الجيران on the fly. جيران(x, y)هما(x + y, y)و(x, x + y). - الجديد هنا: الـ visited مش array بـ index، لأن الـ states مش أرقام من 0 لـ n - 1. بنحوّل كل state لـ string زي
"2,1"ونحطه فيSet. ليه string؟ لأن الـ Set بيقارن الـ arrays بالـ reference، وnew Set([[1,2]]).has([1,2])بتطلعfalse. - الـ bound: الأرقام بتكبر بس. لو x عدّى c أو y عدّى d، مستحيل نرجع، فنرمي الـ state دي. من غيره الـ BFS هيولّد states للأبد.
- BFS ولا DFS؟ للـ yes/no الاتنين شغالين. بس لو اتسألت "أقل عدد خطوات" يبقى BFS، فاتعوّد عليه في مسائل الـ states.
- البداية هي الهدف. السطر ده لازم لأننا بنشيك على الهدف وقت الـ generate بس، والبداية مش بتتولد.
- الـ Set فيه البداية كـ string. ده الـ mark on push بتاعها.
- الـ array الصغيرة دي فيها الجارين، فالـ loop بتمشي على الحركتين من غير ما نكرر الكود.
- بنشيك وقت الـ generate مش وقت الـ pop، فبنوفّر طبقة كاملة من الشغل.
- الـ bound.
>مش>=: لوnx === cلسه ممكن نوصل، لأن y ممكن يكبر لحد d. - نفس الـ visited بالظبط، بس الـ key string.
الـ graph هنا بيتولّد وإحنا ماشيين: كل node بتظهر لحظة ما بنكتشفها.
التعقيد: في الـ worst case بنزور كل الـ states اللي x فيها لحد c و y لحد d، يعني O(c × d). لو الأرقام لحد 10⁹ ده مستحيل. ولاحظ حاجة غريبة في الـ animation: مفيش ولا state اتشافت مرتين. ده مش صدفة، وهو مفتاح الحل الأذكى.
الفكرة الأذكى: امشي لورا
اسأل السؤال بالعكس: الـ state (c, d) جت منين؟
- لو آخر حركة كانت
(x + y, y): يبقىc = x + yوd = y، فـc > d(لأن x موجب). - لو آخر حركة كانت
(x, x + y): يبقىd > c.
يعني لو c > d، الأب لازم يكون (c - d, d)، مفيش اختيار تاني. ولو d > c الأب هو (c, d - c). ولو c === d ملهاش أب خالص. كل state ليها أب واحد بس، فالـ graph ده في الحقيقة tree، وده سبب إن مفيش state اتكررت. ومن الهدف لورا فيه طريق واحد بس، نمشيه:
الطرح ده هو نفسه Euclid بتاع الـ GCD. ومشكلته إن (10⁹, 1) هتطرح 1 مليار مرة. بس طرح d من c لحد ما c يبقى أصغر من d هو بالظبط c % d: modulo واحدة بدل مليار طرح.
فيه حالة واحدة محتاجة حرص: لو d === b، الـ d مش هيتغير تاني، والـ modulo ممكن تنزّل c تحت a وتعدّي الإجابة. هنا بنسأل مباشرة: الفرق c - a بيتقسم على d؟
- وإحنا راجعين الأرقام بتصغر بس. لو أي واحد نزل تحت البداية، خلاص مش هنوصل.
- رقمين متساويين ملهمش أب. والبداية نفسها اتشيكت في السطر اللي فوقه.
- الـ d واقف على b ومش هيتحرك، فالمسموح بس نطرح d من c كذا مرة. نوصل لـ a لو الفرق مضاعف لـ d.
c %= dبتعمل كل الطرحات مرة واحدة. وبعدهاc < d، فاللفة الجاية هتصغّر d.- نفس الكلام بالعكس.
| Input | المتوقع | ليه |
|---|---|---|
| (1,1) → (1,1) | true | البداية هي الهدف |
| (1,1) → (4,4) | false | رقمين متساويين ملهمش أب |
| (1,1) → (10⁹,1) | true | السطر 6 بيجاوب في خطوة واحدة |
| (2,1) → (17,4) | false | الـ modulo نزّلت c لـ 1، تحت a |
| (3,3) → (12,9) | true | (3,3) → (3,6) → (3,9) → (12,9) |
التعقيد: زي الـ GCD بالظبط: O(log max(c, d))، و O(1) memory.
(0, b) بتروح لنفسها، يعني self-loop، والـ visited هو اللي هيحميك من الـ infinite loop.
كده حلينا 5 مسائل. في كل واحدة كان فيه سطر واحد ممكن يبوّظ كل حاجة. يلا نجمعهم في مكان واحد.
غلطات مشهورة
كل غلطة هنا سطر واحد، وكلها بتعدّي على الأمثلة الصغيرة وتقع في الـ hidden tests.
1. تعلّم visited وقت الـ pop
على المترو ده عمل 10 pops بدل 6، وأي عدّاد في الكود هيعدّ مرتين. الصح: visited[v] = true جنب queue.push(v) على طول، زي الـ template.
2. fill([]) في بناء الـ adj
الـ fill بتحط نفس الـ reference في كل خانة. استخدم Array.from زي الـ template: الـ arrow function بتعمل array جديدة لكل خانة. (fill(0) و fill(false) تمام، لأن الأرقام والـ booleans مش references.)
3. نسيت الاتجاه التاني في الـ undirected
لو الـ edges جاية [3, 0]، الـ BFS من 0 عمره ما هيوصل 3. في الـ undirected لازم السطرين: adj[u].push(v) و adj[v].push(u). وفي الـ directed (زي Keys and Rooms) سطر واحد بس، فاقرا المسألة كويس.
4. queue.shift()
جرّبناها على graph فيه 200,000 node: الـ head خلص في 21ms، والـ shift() أخد حوالي 6 ثواني. الكود صح بس هياخد TLE. استخدم queue[head++] و head < queue.length.
5. Traversal من node 0 بس في graph متقطّع
أي سؤال عن "كام حتة" أو "زور كل الـ nodes" محتاج الـ for الخارجية على كل الـ nodes، زي كود الـ components. والـ node اللي مالهاش edges خالص بتتعد component لوحدها.
6. DFS recursive على graph عميق
لو الـ constraints فيها n لحد 10⁵ والـ graph ممكن يبقى سلسلة، استخدم الـ BFS أو الـ DFS بـ stack. الـ recursive تمام لما العمق صغير، زي grid 50 × 50 أو tree متوازنة.
دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.
اختبر نفسك
graph undirected فيه 8 edges. مجموع الـ degrees بتاعة كل الـ nodes كام؟
- 8
- 16
- يعتمد على عدد الـ nodes
- 64
كل edge بتزوّد degree طرفيها الاتنين، فبتتعد مرتين: 2E = 16 مهما كان عدد الـ nodes. وده بالظبط عدد الـ edge checks في الـ BFS.
المسألة: "أقل عدد moves عشان توصل من state لـ state"، والحركات كلها ليها نفس التكلفة. تستخدم إيه؟
- DFS، لأنه أقصر في الكتابة
- BFS، لأن أول مرة يوصل لـ state بتبقى بأقل عدد moves
- أي واحد، الاتنين بيدّوا أقل عدد
- Dijkstra
الـ BFS بيخلّص طبقة d كلها قبل d + 1، فأول وصول = أقصر. الـ DFS ممكن يوصل من طريق طويل الأول. والـ Dijkstra للتكاليف المختلفة، وهنا كلها زي بعض.
n = 6 و edges = [[0,1],[2,3]]. كام connected component؟
- 2
- 3
- 4
- 6
{0, 1} و {2, 3} و {4} و {5}. الـ nodes اللي مالهاش edges كل واحدة component لوحدها، وده اللي بيوقّع ناس كتير.
الـ input جه adjacency matrix مقاسها n × n، وعملت عليه DFS زي Number of Provinces. الـ time complexity؟
- O(n + E)
- O(n log n)
- O(n²)
- O(n³)
كل node بتتزار مرة، وبتلف على صف كامل طوله n عشان تلاقي جيرانها: n × n. لو حوّلت الـ matrix لـ adj الأول، التحويل نفسه n² برضه.
في مسألة (a, b): من (1, 1)، تقدر توصل (4, 4)؟
- أيوه:
(1,1) → (2,1) → (4,1) → (4,4) - لأ: أي state بعد البداية الرقمين فيها مختلفين
- أيوه، لأن 4 مضاعف لـ 1
- محتاجين BFS عشان نعرف
أي حركة بتطلّع رقم أكبر من التاني بالظبط بمقدار موجب، فمستحيل الاتنين يبقوا متساويين بعد أول حركة. وكمان (4,1) ما بتروحش (4,4): بتروح (5,1) أو (4,5).
كتبت const u = queue.shift() بدل queue[head++]. إيه اللي هيحصل على graph فيه 10⁵ node؟
- Wrong Answer
- الإجابة صح بس ممكن TLE، لأن كل shift بتاخد O(n)
- مفيش فرق خالص
- Stack overflow
الترتيب واحد فالإجابة صح. بس الـ shift بتنقل كل العناصر خطوة، فالـ BFS ممكن يوصل لـ O(V²). في التجربة اللي فوق كانت 6 ثواني بدل 21ms.
تمرين: فكّر قبل ما تفتح
graph[i] هي جيران الـ node رقم i (undirected). تقدر تلوّن كل node بلون من اتنين، ومفيش ولا edge بتوصل بين اتنين nodes بنفس اللون؟
تلميح 1
لوّن البداية بلون 0. كل جيرانها لازم يبقوا لون 1، وجيرانهم لون 0، وهكذا. ده BFS طبقة طبقة: الطبقات الزوجية لون والفردية لون.
تلميح 2
لو لقيت جار متلوّن بنفس لونك، يبقى false على طول. وخلي بالك: الـ graph ممكن يبقى متقطّع، فلف على كل الـ nodes زي كود الـ components. وممكن array واحدة color تعمل شغل الـ visited: -1 يعني لسه ما اتزارتش.
الحل
1 - color[u] بتقلب 0 لـ 1 و 1 لـ 0. والكود هو كود الـ components بالظبط، بس الـ visited بقى بيشيل معلومة زيادة (اللون)، زي ما الـ Map في Clone Graph كانت بتشيل النسخة. O(V + E).
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
كل مسألة بتضيف فكرة واحدة على اللي قبلها. لو قعدت أكتر من 25 دقيقة، ارجع للـ template هنا، وبعدين حاول تاني من غير ما تبص.
- Find if Path Exists in Graphالمثال المحلول 1: edges لـ adj و BFS. اكتبه من دماغك.
- Find Center of Star Graphمفهوم الـ degree بس، من غير traversal. فيها trick بـ edge اتنين بس.
- Find the Town Judgedirected graph: الـ in-degree والـ out-degree كل واحد لوحده.
- Keys and Roomsالمثال 3: الـ adj جاهزة و directed، وزرنا الكل؟
- Number of Provincesالمثال 2، سؤال الـ data centers: components على matrix.
- Reachable Nodes With RestrictionsBFS بس فيه nodes ممنوعة: علّمها visited من الأول.
- All Paths From Source to TargetDFS بيطلّع كل الطرق مش أول طريق. أول خطوة ناحية الـ backtracking.
- Clone Graphالمثال 4: الـ visited بقى Map شايلة النسخة.
- Is Graph Bipartite?التمرين اللي فوق: BFS بيلوّن، والـ graph ممكن يبقى متقطّع.
- Reorder Routes to Make All Paths Lead to the City Zeroخزّن كل edge في الاتجاهين، وعلّم الاتجاه الأصلي بتكلفة 1.
- Jump Game IIIgraph مستخبي: كل index node، والجيران بتتحسب من القفزة.
- Minimum Genetic MutationBFS على states كـ strings، وأقل عدد خطوات = الطبقة.
- Open the Lockstate BFS كامل: Set للـ visited، و states ممنوعة، و 8 جيران لكل state.
- Reaching Pointsمسألة الاختبار نفسها بالأرقام الكبيرة: امشي لورا بالـ modulo.
وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل الاختبار.
الخلاصة
adj، وامشي عليها بـ BFS أو DFS بـ visited بيتعلّم وقت الـ push، في O(V + E). أقل عدد خطوات يبقى BFS، وعدّ الحتت يبقى loop على كل الـ nodes.
| السؤال | الإجابة |
|---|---|
| أعلّم visited إمتى؟ | وقت الـ push، في نفس السطر تقريبًا. مش وقت الـ pop. |
| BFS ولا DFS؟ | minimum / shortest / fewest من غير أوزان: BFS. reachability أو عدّ: أي واحد. |
| الـ queue في JS؟ | array + head. أوعى shift(). |
| Undirected؟ | push في الاتجاهين. Directed: اتجاه واحد. |
| الـ graph متقطّع؟ | for على كل الـ nodes، وكل node مش visited تبدأ component. |
| الـ nodes مش أرقام (states)؟ | string key في Set أو Map، وحط bound يوقف التوليد. |
| Complexity؟ | O(V + E) مع adj list، و O(V²) مع matrix. |
الفصل الجاي: Graphs على Grid، أكتر نوع graph بيتسأل في الاختبارات: خريطة مربعات، كل خانة فيها node. نفس الـ BFS والـ DFS اللي كتبتهم هنا بالظبط، بس الجيران بتتحسب بـ DIRS بدل adj، ومعاهم حاجات جديدة زي الـ multi-source BFS وإزاي تعدّ الدقايق طبقة طبقة بـ levelSize.