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 موجود في حاجات كتير بتستخدمها كل يوم:

تشبيه: أقل عدد محطات لو حد سألك "أقل عدد محطات من هنا لهناك كام؟"، إنت بتعمل حاجة من غير ما تاخد بالك: بتشوف المحطات اللي على بُعد محطة واحدة، وبعدين اللي على بُعد اتنين، وهكذا لحد ما توصل. دواير بتكبر حوالين نقطة البداية. الطريقة دي اسمها BFS، وهي قلب الفصل ده.

شوفها على مترو صغير فيه 6 محطات. الرقم اللي تحت كل محطة هو عدد المحطات من محطة 0:

كل طبقة فيها المحطات اللي على نفس المسافة. ولاحظ إن محطة 3 ليها طريقين (من 1 ومن 2)، بس اتحسبت مرة واحدة. الحتة دي بالذات هي اللي بتفرق بين كود شغال وكود بيلف للأبد.

طب إزاي تعرف إن المسألة اللي قدامك graph أصلًا، وهي ساعات ما بتقولش كلمة graph خالص؟

إزاي تعرفه من المسألة

أغلب مسائل الـ graph ما بتقولش "graph". بتقول كلام زي ده:

لما تشوف: network / connectionsconnectedcan you reach / is there a path regions / provinces / groupsfriends / followerscities and roads prerequisites / dependenciesminimum number of movestransform X into Y rooms and keysislands / mazeclone a graph
ومش graph غالبًا لو: contiguous subarraysorted array + targettop k / kth largest

الـ 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)
جزر، خريطة، mazeBFS / DFS على gridGraphs على Grid
ترتيب مهام ليها dependenciesTopological sortGraphs المتقدمة
أقصر طريق بأوزان (وقت، فلوس)DijkstraGraphs المتقدمة
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رحلة من محطة لمحطة
cyclepath بيرجع لنفس الـ node اللي بدأ منهالفة وترجع مكانك
connectedمن أي node تقدر توصل لأي node تانيةكل المحطات على شبكة واحدة
componentحتة متوصلة ببعضها ومقطوعة عن الباقيشبكة مترو في مدينة تانية

هنكتب V لعدد الـ nodes و E لعدد الـ edges. في المترو ده V = 6 و E = 7. وخلي في بالك الحسبة دي عشان هنحتاجها في الـ complexity: لو جمعت الـ degrees كلها، كل edge بتتعد مرتين (مرة من كل طرف)، فالمجموع دايمًا 2E.

الـ tree هي graph برضه الـ tree هي graph connected ومفيهاش cycles. عشان كده الـ BFS والـ DFS اللي عملتهم في فصل الـ trees هما هما اللي هنعملهم هنا، مع فرق واحد مهم هتشوفه بعد شوية: الـ visited.

تمام، فهمنا الرسمة. بس الكمبيوتر ما بيشوفش رسومات. إزاي نخزّن الـ 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% من المسائل.

  1. بنعمل n arrays فاضية، واحدة لكل node. الـ Array.from بتنادي الـ arrow function مرة لكل خانة، فكل node بتاخد array جديدة. أوعى new Array(n).fill([])، دي بتحط نفس الـ array في كل الخانات (الغلطة 2 تحت).
  2. الـ destructuring [u, v] بيفك كل edge لطرفينها. أوضح من e[0] و e[1].
  3. الـ graph undirected، فالـ edge معناها إن v جار لـ u و u جار لـ v. لو نسيت السطر 5، الـ traversal هيمشي في اتجاه واحد ويفوّت nodes. ولو المسألة قالت directed، بتشيل السطر 5.
  4. الـ memory هنا n arrays مجموع أطوالها 2E، يعني O(V + E).

شوف الـ adj وهي بتتبني edge ورا edge:

3. Adjacency matrix: جدول n × n

الشكل التاني جدول: matrix[u][v] = 1 لو فيه edge بين u و v، و 0 لو مفيش. الصف رقم u هو "مين متوصل بـ u".

Adjacency listAdjacency matrix
MemoryO(V + E)O(V²)
u و v متوصلين؟O(degree): تدوّر في adj[u]O(1): matrix[u][v]
هات جيران uO(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 بيتملي نسخ مكررة.

القاعدة علّم الـ node visited في نفس اللحظة اللي بتعملها فيها push. الـ visited معناها "حد حجزلها مكان في الـ queue خلاص"، مش "اتعالجت". كده كل node بتدخل الـ queue مرة واحدة بالظبط.
تشبيه: كشف المعازيم بتعزموا ناس على فرح، وكل واحد بيعزم صحابه. لو شطبت الاسم من الكشف لما الشخص يوصل الفرح، ممكن اتنين يبعتوا دعوة لنفس الشخص وهو لسه في الطريق. لكن لو شطبته لحظة ما الدعوة اتبعتت، محدش هيعزمه تاني.

كده معانا كل القطع: adj و queue و visited. يلا نركّبهم مع بعض في BFS كامل.

BFS: دواير بتكبر حوالين البداية

الـ BFS (Breadth-First Search) بيزور الـ nodes طبقة طبقة: البداية، وبعدين كل اللي على بُعد 1، وبعدين كل اللي على بُعد 2… والأداة اللي بتضمن الترتيب ده هي الـ queue: أول واحد يدخل أول واحد يطلع. ده نفس الـ level order اللي عملته في الـ trees، زائد الـ visited.

  1. في الأول محدش اتشاف، فكله false.
  2. الـ dist بيبدأ -1 مش 0، لأن 0 معناها "دي البداية". لو node فضلت -1 في الآخر يبقى مفيش طريق ليها.
  3. البداية بتدخل الـ queue وبتتعلّم في نفس اللحظة. أول تطبيق للقاعدة: mark on push.
  4. الـ head هو index أول واحد في الطابور. بدل queue.shift() اللي بتزق كل العناصر خطوة لقدام (O(n) كل مرة)، بنحرّك الـ index بس، O(1).
  5. head < queue.length معناها "لسه فيه ناس في الطابور". < مش <=، لأن لما head يساوي الطول يبقى مفيش عنصر عند الـ index ده.
  6. queue[head++]: خد العنصر اللي عند head، وبعدين زوّد head. الـ ++ بعد الاسم معناها "استخدم القيمة القديمة الأول".
  7. بنلف على جيران u بس، مش على كل الـ nodes. ده اللي هيخلّي الـ complexity O(V + E).
  8. لو v جديدة: نعلّمها، ومسافتها مسافة u زائد 1، وندخلها الطابور. التلاتة مع بعض. ولو visited، يا اتعالجت يا واقفة في الطابور بمسافة أحسن أو قدها، فمش هنلمسها.
  9. لو محتاج 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، بنشوفها من أقرب طبقة ممكنة، وده أقصر طريق.

الكلام ده للـ graphs اللي من غير أوزان الـ BFS بيعدّ عدد الـ edges. لو كل edge ليها وقت مختلف (زي Google Maps)، طريق فيه 3 edges قصيرة ممكن يبقى أسرع من edge واحدة طويلة. ساعتها محتاج Dijkstra، وده في Graphs المتقدمة.

ولو عايز الطريق نفسه مش طوله بس، خزّن لكل 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، ارجع لـ فصلها.

  1. الـ dfs الداخلية شايفة visited و order و adj من غير ما نبعتهم، لأنها معمولة جوه dfsOrder (closure).
  2. بنعلّم أول ما ندخل، قبل ما نلمس أي جار. ده المقابل لـ mark on push: أول ما قررنا نزور u، محدش يقدر يدخلها تاني.
  3. لكل جار مش visited بننادي dfs(v)، والنداء ده مش بيرجع غير لما كل اللي ورا v يخلص. ده الغطس.
  4. مفيش base case صريح زي if (n === 0). الـ base case هنا ضمني: node كل جيرانها visited، فالـ loop ما بتناديش حاجة والـ function بترجع.
  5. نقطة البداية. لو الـ 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++]:

  1. نفس بداية الـ BFS: البداية جوه ومتعلّمة.
  2. pop() بتطلّع آخر واحد دخل (LIFO). ده الفرق الوحيد عن الـ BFS، وهو اللي بيخلّيه يغطس: آخر جار اتزق هو أول واحد يتزار. والـ pop هنا O(1) لأنها من آخر الـ array، مش زي shift.
  3. نفس الـ mark on push، فكل node بتدخل الـ stack مرة واحدة.

الترتيب هنا 0, 2, 3, 5, 4, 1، مختلف عن الـ recursive، لأن الـ stack بتطلّع آخر جار اتزق الأول. الاتنين DFS صح. وفي مسائل الـ reachability والـ components والعدّ، الترتيب مش فارق خالص.

الـ DFS بينفع في إيه؟

طب لما الاتنين بيزوروا نفس الـ nodes، إمتى تختار ده وإمتى ده؟

BFS ولا DFS؟

BFSDFS
الأداةqueue (FIFO) + headrecursion، أو stack (LIFO)
الترتيبطبقة طبقة، الأقرب الأوليغطس لآخر الطريق ويرجع
أقصر طريق (من غير أوزان)أيوه: أول وصول = أقل عدد edgesلأ
الـ memoryالـ queue ممكن يشيل طبقة كاملة (graph عريض)قد عمق الطريق (graph طويل)
الكودqueue و head و whileالـ recursive أقصر كود ممكن
الخطرshift() البطيئةstack overflow في الـ recursion العميقة
بيكسب فيأقل عدد moves، أقرب حاجة، طبقاتكل الـ paths، backtracking، cycles، topo sort
ComplexityO(V + E)O(V + E)
القاعدة السريعة المسألة فيها minimum / shortest / fewest من غير أوزان؟ BFS. المطلوب reachability أو عدّ حتت؟ أي واحد، اكتب اللي إيدك متعودة عليه. محتاج كل الطرق أو تكتشف cycle؟ DFS.

الاتنين بيبدأوا من 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 كلها.

  1. بنلف على كل الـ nodes. لو بدأت من 0 بس، أي component مفيهاش 0 هتضيع.
  2. node visited يعني اتعدّت مع component قبل كده، فبنعدّيها.
  3. العدّاد بيزيد هنا بس: node محدش وصلها = component جديدة.
  4. الـ BFS template بالظبط، بيعلّم الـ component كلها. ممكن تحط مكانه dfs(s) والنتيجة واحدة.
  5. 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. الرقمين دول جايين منين؟

  1. الشغل على الـ nodes: كل node بتدخل الـ queue مرة واحدة بالظبط (الـ visited ضامن ده)، وبتطلع مرة. يعني V push و V pop: O(V). المترو فيه 6 nodes، و 6 pops.
  2. الشغل على الـ edges: لما u بتطلع، بنلف على adj[u]، يعني degree(u) لفة. وكل node بتطلع مرة، فالمجموع = مجموع الـ degrees = 2E. عندنا 7 edges، يعني 14 check.
  3. المجموع: V + 2E، يعني O(V + E). الـ inner loop مش بتلف E مرة كل مرة، بتلف degree(u) بس. عشان كده جمع مش ضرب.
  4. ومع الـ matrix؟ "هات جيران u" = لف على صف كامل، يعني V لكل node، فالمجموع O(V²) مهما كانت الـ edges قليلة.
VEAdjacency list: V + EMatrix: V²
1,0005,0006,0001,000,000
100,000200,000300,00010,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

Find if Path Exists in Graph

easyLeetCode 1971

عندك n nodes مترقمين من 0 لـ n - 1، ولستة undirected edges. هل فيه طريق من source لـ destination؟

Input: n = 7, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[5,6]], source = 0, destination = 4 Output: true (0 → 1 → 3 → 4) Input: same graph, source = 0, destination = 6 Output: false (5 and 6 are a separate piece)

نفكّر فيها مع بعض

  1. افهم المطلوب: مش عايزين الطريق ولا طوله، yes أو no بس. ده reachability.
  2. Brute force: تجرّب كل الطرق من source. عدد الطرق في graph فيه cycles ممكن يبقى exponential، ومن غير visited هيلف للأبد.
  3. الـ insight: السؤال الحقيقي "هل destination في نفس الـ component بتاعة source؟". BFS من source بيزور الـ component دي كلها في O(V + E).
  4. الخطة: نحوّل الـ edges لـ adj، وبعدين الـ BFS template، ولو destination طلعت من الـ queue نعمل early return بـ true.
  5. الحالات الطرفية: source === destination، ومفيش edges خالص، و nodes لوحدها.
  1. نفس buildAdj بالظبط، مكتوبة inline. في الاختبار اكتبها كده عادي.
  2. الـ BFS template: البداية في الـ queue ومتعلّمة.
  3. بنشيك وقت الـ pop. كده حالة source === destination متغطية من غير سطر زيادة، لأن source أول واحد بيطلع.
  4. زي الـ template، من غير dist لأن السؤال yes/no.
  5. الـ queue فضي ولسه ما شفناش destination، يبقى في component تانية.

نفس الكود مرتين: مرة لـ destination = 4، ومرة لـ 6:

Inputالمتوقعليه الحالة دي مهمة
n=1, [], 0 → 0truesource هي destination، والشيك وقت الـ pop بيلقطها
n=3, [], 0 → 2falseمفيش edges خالص، الـ queue بيفضى بعد pop واحدة
[[0,1],[1,2],[2,0]], 0 → 2truecycle، والـ visited بيمنع اللف حواليه
destination في حتة تانيةfalseالـ BFS بيخلص من غير ما يشوفها

التعقيد: بناء الـ adj O(E)، والـ BFS O(V + E). الـ memory O(V + E).

في الانترفيو ممكن تحلها بـ DFS، أو بـ Union-Find اللي في Graphs المتقدمة. اللي الـ interviewer عايز يسمعه: "السؤال reachability، وأي traversal من source بيجاوبه في O(V + E)".

هنا الـ graph جالنا edges، والسؤال عن node واحدة. طب لو جالنا جدول، والسؤال "كام حتة"؟

مثال محلول 2: Number of Provinces (مسألة الـ data centers)

Number of Provinces

mediumLeetCode 547

عندك n مدن وجدول isConnected مقاسه n × n: الخانة [i][j] بـ 1 لو المدينة i متوصلة مباشرة بالمدينة j. الـ province مجموعة مدن متوصلة ببعض، مباشرة أو عن طريق مدن تانية. رجّع عدد الـ provinces.

Input: isConnected = [[1,1,0,0,0,0], [1,1,0,1,0,0], [0,0,1,0,1,0], [0,1,0,1,0,0], [0,0,1,0,1,0], [0,0,0,0,0,1]] Output: 3 ({0, 1, 3}, {2, 4}, {5})
ده سؤال assessment مشهور "قسّم شبكة الـ data centers لـ regions" هي المسألة دي بالظبط: غيّر "مدينة" لـ data center، و "province" لـ region. ولو الاختبار اداك الكابلات كـ edges بدل جدول، ابني adj واستخدم كود الـ components اللي فوق زي ما هو.

نفكّر فيها مع بعض

  1. افهم المطلوب: كل province هي connected component. المطلوب عددهم.
  2. الجديد هنا: الـ graph جاي adjacency matrix مش edges. مش محتاجين نبني adj: جيران u هما كل v في الصف u قيمتها 1.
  3. الخطة: نفس كود الـ components، بالـ DFS الـ recursive عشان أقصر، والجيران من الصف.
  4. القطر: isConnected[i][i] دايمًا 1 (المدينة متوصلة بنفسها). مش مشكلة، لأن i ساعتها visited فبنعدّيها.
  5. الحالات الطرفية: مدينة واحدة، وكل المدن لوحدها، وكله متوصل.
  1. عدد المدن هو عدد الصفوف.
  2. نعلّم أول ما ندخل، زي الـ DFS template.
  3. بنلف على كل الأعمدة من 0 لـ n - 1، يعني O(n) لكل مدينة حتى لو جيرانها قليلين. ده تمن الـ matrix.
  4. شرطين مع بعض: فيه كابل، ولسه ما زرناهاش. لو نسيت !visited[v] هتلف بين 0 و 1 لحد stack overflow.
  5. نفس الـ for الخارجية بتاعة الـ components: مدينة مش visited = province جديدة.

فوق: الـ data centers ملوّنة بالـ region بتاعتها. في النص: الجدول، والصف اللي بنقراه أزرق. تحت: الـ call stack.

Inputالمتوقعليه
[[1]]1مدينة واحدة = province واحدة
identity 3 × 33مفيش كابلات، كل مدينة لوحدها
كله 11كله متوصل ببعض
[[1,1,0],[1,1,1],[0,1,1]]10 و 2 مش متوصلين مباشرة، بس عن طريق 1

التعقيد: كل مدينة بتتزار مرة، وبتلف على صف كامل: O(n²). ودي أحسن حاجة ممكنة، لأن قراية الـ input نفسه n². الـ memory O(n) للـ visited والـ call stack.

لحد دلوقتي الـ edges كانت رايح جاي. طب لو الـ edge ليها اتجاه واحد، والسؤال "أقدر أزور الكل"؟

مثال محلول 3: Keys and Rooms

Keys and Rooms

mediumLeetCode 841

عندك n أوض، كلها مقفولة ما عدا أوضة 0. جوه كل أوضة شوية مفاتيح، و rooms[i] هي أرقام الأوض اللي مفاتيحها جوه أوضة i. تقدر تدخل كل الأوض؟

Input: rooms = [[2], [3], [4, 1], [], [2]] Output: true (0 → 2 → 4 and 1, 1 → 3) Input: rooms = [[1, 2], [2], [0], [4], [3]] Output: false (rooms 3 and 4 only hold each other's keys)

نفكّر فيها مع بعض

  1. فين الـ graph؟ كل أوضة node. ولو مفتاح أوضة 3 جوه أوضة 1، يبقى فيه edge من 1 لـ 3.
  2. الجديد هنا: الـ graph directed (مفتاح 3 في أوضة 1 ما يعنيش إن مفتاح 1 في أوضة 3)، وجاي جاهز: rooms هي نفسها الـ adjacency list.
  3. السؤال: هل كل الـ nodes reachable من 0؟ traversal من 0 ونعدّ اللي فتحناه.
  4. الأداة: DFS بـ stack، عشان الترتيب مش فارق، وعشان نتمرن على الـ iterative.
  5. الحالات الطرفية: أوضة واحدة بس، وأوضة مفيهاش مفاتيح، ومفتاح لأوضة فتحناها قبل كده.
  1. بنبدأ من أوضة 0 لأنها الوحيدة المفتوحة.
  2. count بيعدّ الأوض اللي فتحناها، وبيبدأ 1 عشان أوضة 0.
  3. rooms[room] هي جيران الأوضة دي. مفيش buildAdj ولا push في الاتجاه التاني، لأن المفتاح بيفتح في اتجاه واحد.
  4. mark on push، والـ count بيزيد مع الـ visited، فكل أوضة بتتعد مرة واحدة بالظبط.
  5. فتحنا كل الأوض؟ ده أسرع من 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

Clone Graph

mediumLeetCode 133

معاك reference لـ node واحدة في graph متوصل و undirected. كل node فيها val ولستة neighbors. اعمل deep copy: nodes جديدة خالص بنفس الـ vals ونفس التوصيلات، ورجّع نسخة الـ node اللي اتدّتلك.

Input: edges 1-2, 1-3, 2-3, 3-4 (neighbors: 1:[2,3] 2:[1,3] 3:[1,2,4] 4:[3]) Output: a brand-new graph with the same shape (no node shared with the input)

نفكّر فيها مع بعض

  1. deep copy معناها إن كل node جديدة، والـ neighbors بتاعتها بتشاور على الـ nodes الجديدة مش القديمة.
  2. المشكلة: الـ cycles. لو نسخت 1، فنسخت جارها 2، فنسخت جارها 1… نسخ لا نهائية. محتاجين نفتكر "الـ node دي اتنسخت قبل كده؟".
  3. الجديد هنا: الـ visited بقى Map من القديم للجديد. وجود الـ key معناه visited، والـ value هي النسخة نفسها، اللي محتاجينها عشان نوصّل الـ neighbors.
  4. الخطة: BFS. أول ما نشوف node: نعمل نسختها ونحطها في الـ Map ونزقها. ولكل جار: نضيف نسخة الجار لـ neighbors نسخة الـ node الحالية.
  5. الحالات الطرفية: node === null، و node لوحدها من غير جيران.
  1. graph فاضي، نرجّع null. وعلى LeetCode الـ class اسمها _Node مش Node، غيّر الاسم بس.
  2. Map مش object عادي، لأن الـ keys هنا objects. الـ object العادي بيحوّل أي key لـ string، فكل الـ nodes هتبقى نفس الـ key "[object Object]".
  3. نسخة البداية تدخل الـ Map، والبداية تدخل الـ queue. ده الـ mark on push.
  4. أول مرة نشوف nb: نعمل نسختها ونحطها في الـ Map قبل الـ push. الـ Map هنا هي الـ visited بالظبط.
  5. أهم سطر، وهو برا الـ if: لازم نوصّل الـ edge حتى لو nb اتنسخت قبل كده. لو دخّلته جوه الـ if، الـ edges اللي بتقفل cycle (زي 2-3) هتضيع.
  6. نرجّع النسخة، مش الأصل. لو رجّعت node الـ judge هيقول إنك ما نسختش.

الأصل على الشمال، والنسخ (بشرطة ') بتتولد على اليمين وبتتوصل edge ورا edge:

Inputالمتوقعليه
nullnullالسطر 2
node لوحدهاnode جديدة، neighbors فاضيةالـ for مش بتلف خالص
1-2 بسنسختين، كل واحدة بتشاور على التانيةالسطر 14 بيشتغل مرتين، مرة من كل ناحية
مثلث 1-2-3مثلث جديدالـ Map بتمنع النسخ اللا نهائي

التعقيد: كل node بتتنسخ مرة، وكل edge بتتوصّل مرتين (مرة من كل طرف): O(V + E). والـ memory O(V) للـ Map والـ queue.

نسخة DFS لو طلب DFS، الحتة الحساسة: سجّل النسخة في الـ Map قبل ما تنزل في الجيران. لو سجّلتها بعد، الـ cycle هيرجّعك لنفس الـ node وهي لسه مش في الـ Map، فهتعمل recursion للأبد.

في كل اللي فات كان فيه graph موجود قدامنا: edges، أو matrix، أو rooms، أو nodes. طب لو مفيش graph خالص، والـ nodes بتتولد وإنت ماشي؟

مثال محلول 5: BFS على states (مسألة (a, b) من الاختبار)

Reach the Pair

interviewشبيهة بـ LeetCode 780

معاك رقمين (a, b). في كل خطوة تقدر تعمل حاجة من اتنين: تزوّد التاني على الأول فتبقى (a + b, b)، أو تزوّد الأول على التاني فتبقى (a, b + a). هل تقدر توصل لـ (c, d)؟ كل الأرقام موجبة.

Input: (a, b) = (1, 1), (c, d) = (3, 4) Output: true (1,1) → (2,1) → (3,1) → (3,4) Input: (a, b) = (1, 1), (c, d) = (4, 4) Output: false Input: (a, b) = (2, 1), (c, d) = (17, 5) Output: true (2,1) → (2,3) → (2,5) → (7,5) → (12,5) → (17,5)

نفكّر فيها مع بعض

  1. فين الـ graph؟ كل state زي (2, 1) هي node، وكل حركة مسموحة edge. الـ graph ده مش متخزن في أي حتة: بنولّد الجيران on the fly. جيران (x, y) هما (x + y, y) و (x, x + y).
  2. الجديد هنا: الـ visited مش array بـ index، لأن الـ states مش أرقام من 0 لـ n - 1. بنحوّل كل state لـ string زي "2,1" ونحطه في Set. ليه string؟ لأن الـ Set بيقارن الـ arrays بالـ reference، و new Set([[1,2]]).has([1,2]) بتطلع false.
  3. الـ bound: الأرقام بتكبر بس. لو x عدّى c أو y عدّى d، مستحيل نرجع، فنرمي الـ state دي. من غيره الـ BFS هيولّد states للأبد.
  4. BFS ولا DFS؟ للـ yes/no الاتنين شغالين. بس لو اتسألت "أقل عدد خطوات" يبقى BFS، فاتعوّد عليه في مسائل الـ states.
  1. البداية هي الهدف. السطر ده لازم لأننا بنشيك على الهدف وقت الـ generate بس، والبداية مش بتتولد.
  2. الـ Set فيه البداية كـ string. ده الـ mark on push بتاعها.
  3. الـ array الصغيرة دي فيها الجارين، فالـ loop بتمشي على الحركتين من غير ما نكرر الكود.
  4. بنشيك وقت الـ generate مش وقت الـ pop، فبنوفّر طبقة كاملة من الشغل.
  5. الـ bound. > مش >=: لو nx === c لسه ممكن نوصل، لأن y ممكن يكبر لحد d.
  6. نفس الـ visited بالظبط، بس الـ key string.

الـ graph هنا بيتولّد وإحنا ماشيين: كل node بتظهر لحظة ما بنكتشفها.

التعقيد: في الـ worst case بنزور كل الـ states اللي x فيها لحد c و y لحد d، يعني O(c × d). لو الأرقام لحد 10⁹ ده مستحيل. ولاحظ حاجة غريبة في الـ animation: مفيش ولا state اتشافت مرتين. ده مش صدفة، وهو مفتاح الحل الأذكى.

الفكرة الأذكى: امشي لورا

اسأل السؤال بالعكس: الـ state (c, d) جت منين؟

يعني لو 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؟

  1. وإحنا راجعين الأرقام بتصغر بس. لو أي واحد نزل تحت البداية، خلاص مش هنوصل.
  2. رقمين متساويين ملهمش أب. والبداية نفسها اتشيكت في السطر اللي فوقه.
  3. الـ d واقف على b ومش هيتحرك، فالمسموح بس نطرح d من c كذا مرة. نوصل لـ a لو الفرق مضاعف لـ d.
  4. c %= d بتعمل كل الطرحات مرة واحدة. وبعدها c < d، فاللفة الجاية هتصغّر d.
  5. نفس الكلام بالعكس.
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.

إزاي تقدّمها في الاختبار ابدأ بالـ BFS على states وقول إن الـ complexity O(c × d). بعدها قول "بس كل state ليها أب واحد"، وامشي لورا. ده بيورّي إنك بتفكر مش حافظ. ولو الأرقام ممكن تبقى 0: (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.

تمرين: فكّر قبل ما تفتح

Is Graph Bipartite?

mediumLeetCode 785

graph[i] هي جيران الـ node رقم i (undirected). تقدر تلوّن كل node بلون من اتنين، ومفيش ولا edge بتوصل بين اتنين nodes بنفس اللون؟

[[1,3],[0,2],[1,3],[0,2]] → true (a square: 0 and 2 one colour, 1 and 3 the other) [[1,2],[0,2],[0,1]] → false (a triangle: three nodes, two colours)
تلميح 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 هنا، وبعدين حاول تاني من غير ما تبص.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل الاختبار.

الخلاصة

في جملة واحدة أي "حاجات + علاقات بينها" هي graph: حوّلها لـ 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.