العرض أولاً مقابل العمق أولاً

Question

عند اجتياز شجرة/رسم بياني، ما الفرق بين العرض أولاً والعمق أولاً؟أي أمثلة على الترميز أو الكود الكاذب ستكون رائعة.

Answer 1

يفرق هذان المصطلحان بين طريقتين مختلفتين للمشي على الشجرة.

ربما يكون من الأسهل فقط إظهار الفرق.خذ بعين الاعتبار الشجرة:

    A
   / \
  B   C
 /   / \
D   E   F

أ عمق سوف يقوم الاجتياز الأول بزيارة العقد بهذا الترتيب

A, B, D, C, E, F

لاحظ أنك تسير على طول الطريق تحت ساق واحدة قبل المضي قدما.

أ سعة سيزور الاجتياز الأول العقدة بهذا الترتيب

A, B, C, D, E, F

نحن هنا نعمل على طول الطريق عير كل مستوى قبل النزول.

(لاحظ أن هناك بعض الغموض في أوامر الاجتياز، ولقد خدعت للحفاظ على ترتيب "القراءة" في كل مستوى من مستويات الشجرة.في كلتا الحالتين، يمكنني الوصول إلى B قبل C أو بعده، وبالمثل يمكنني الوصول إلى E قبل F أو بعده.قد يكون هذا مهمًا أو لا يهم، يعتمد على طلبك...)

---

يمكن تحقيق كلا النوعين من الاجتياز باستخدام الكود الكاذب:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

الفرق بين أمري الاجتياز يكمن في اختيار Container.

• ل العمق أولا استخدم كومة.(يستخدم التنفيذ العودي مكدس الاستدعاءات...)
• ل اتساع أولا استخدام قائمة الانتظار.

---

يبدو التنفيذ العودي

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

ينتهي العودية عندما تصل إلى عقدة لا يوجد بها أطفال ، لذلك من الضروري أن تنتهي للرسوم البيانية المحدودة والحيوية.

---

في هذه المرحلة، مازلت أغش قليلاً.مع قليل من الذكاء يمكنك ذلك أيضًا يعمل على العقد بهذا الترتيب:

D, B, E, F, C, A

وهو اختلاف في العمق أولاً، حيث لا أقوم بالعمل عند كل عقدة حتى أعود إلى أعلى الشجرة.لقد ومع ذلك زار العقد الأعلى في طريقهم إلى الأسفل للعثور على أطفالهم.

يعد هذا الاجتياز أمرًا طبيعيًا إلى حد ما في التنفيذ العودي (استخدم سطر "الوقت البديل" أعلاه بدلاً من سطر "العمل" الأول)، وليس أيضاً من الصعب إذا كنت تستخدم مكدس صريح، ولكن سأترك الأمر كتمرين.

Answer 2

فهم المصطلحات:

يجب أن تعطيك هذه الصورة فكرة عن السياق الذي توجد فيه الكلمات سعة و عمق يستخدم.

---

عمق البحث الأول:

• تعمل خوارزمية البحث في عمق العمق كما لو كانت ترغب في الابتعاد عن نقطة البداية في أسرع وقت ممكن.

• يستخدم بشكل عام أ Stack لتتذكر أين يجب أن تذهب عندما تصل إلى طريق مسدود.

• القواعد الواجب اتباعها:ادفع الرأس الأول A إلى Stack

  1. إذا كان ذلك ممكنًا، قم بزيارة قمة مجاورة لم تتم زيارتها، وقم بوضع علامة عليها على أنها تمت زيارتها، ثم ادفعها على المكدس.
  2. إذا لم تتمكن من اتباع القاعدة 1، فقم بإخراج قمة من المكدس إن أمكن.
  3. إذا لم تتمكن من اتباع القاعدة 1 أو القاعدة 2، فقد انتهيت.

• كود جافا:

  public void searchDepthFirst() {
      // Begin at vertex 0 (A)
      vertexList[0].wasVisited = true;
      displayVertex(0);
      stack.push(0);
      while (!stack.isEmpty()) {
          int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
          // If no such vertex
          if (adjacentVertex == -1) {
              stack.pop();
          } else {
              vertexList[adjacentVertex].wasVisited = true;
              // Do something
              stack.push(adjacentVertex);
          }
      }
      // Stack is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++)
          vertexList[j].wasVisited = false;
  }
  

• التطبيقات:غالبًا ما تُستخدم عمليات بحث العمق أولاً في محاكاة الألعاب (والمواقف الشبيهة بالألعاب في العالم الحقيقي).في لعبة نموذجية، يمكنك اختيار واحد من بين العديد من الإجراءات الممكنة.يؤدي كل خيار إلى مزيد من الاختيارات، كل منها يؤدي إلى مزيد من الاختيارات، وهكذا إلى رسم بياني للاحتمالات على شكل شجرة يتوسع باستمرار.

---

بحث العرض الأول:

• تحب خوارزمية البحث في العرض الأول البقاء أقرب ما يمكن إلى نقطة البداية.
• يتم تنفيذ هذا النوع من البحث بشكل عام باستخدام ملف Queue.
• القواعد الواجب اتباعها:اجعل بداية Vertex A هي القمة الحالية
  1. قم بزيارة القمة التالية غير التي تمت زيارتها (إن وجدت) والمجاورة للقمة الحالية، وقم بوضع علامة عليها، وأدخلها في قائمة الانتظار.
  2. إذا لم تتمكن من تنفيذ القاعدة 1 لأنه لم تعد هناك رؤوس لم تتم زيارتها، فقم بإزالة قمة من قائمة الانتظار (إن أمكن) واجعلها القمة الحالية.
  3. إذا لم تتمكن من تنفيذ القاعدة 2 لأن قائمة الانتظار فارغة، فقد انتهيت.

• كود جافا:

  public void searchBreadthFirst() {
      vertexList[0].wasVisited = true;
      displayVertex(0);
      queue.insert(0);
      int v2;
      while (!queue.isEmpty()) {
          int v1 = queue.remove();
          // Until it has no unvisited neighbors, get one
          while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
              vertexList[v2].wasVisited = true;
              // Do something
              queue.insert(v2);
          }
      }
      // Queue is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++) 
          vertexList[j].wasVisited = false;
  }
  

• التطبيقات:يبحث البحث عن العرض أولاً أولاً عن جميع القمم التي تبعد حافة واحدة عن نقطة البداية، ثم جميع القمم التي تبعد حافتين، وهكذا.يعد هذا مفيدًا إذا كنت تحاول العثور على أقصر مسار من قمة البداية إلى قمة معينة.

نأمل أن يكون ذلك كافيًا لفهم عمليات البحث ذات العرض الأول والعمق أولاً.لمزيد من القراءة أوصي بفصل الرسوم البيانية من كتاب ممتاز عن هياكل البيانات من تأليف روبرت لافور.

Answer 3

بالنظر إلى هذه الشجرة الثنائية:

اتساع الاجتياز الأول:
اجتياز كل مستوى من اليسار إلى اليمين.

"أنا G، أطفالي هم D وأنا، أحفادي هم B، E، H و K، وأحفادهم هم A، C، F"

- Level 1: G 
- Level 2: D, I 
- Level 3: B, E, H, K 
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, A, C, F

العمق الأول اجتياز:
لا يتم الاجتياز عبر المستويات بأكملها في وقت واحد.بدلاً من ذلك، يغوص الاجتياز في عمق الشجرة (من الجذر إلى الورقة) أولاً.ومع ذلك، فهو أكثر تعقيدًا بعض الشيء من مجرد الصعود والهبوط.

هناك ثلاث طرق:

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:  
Grab the Root. (G)  
Then Check the Left. (It's a tree)  
Grab the Root of the Left. (D)  
Then Check the Left of D. (It's a tree)  
Grab the Root of the Left (B)  
Then Check the Left of B. (A)  
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)  
Check the Right of D. (It's a tree)  
Grab the Root. (E)  
Check the Left of E. (Nothing)  
Check the Right of E. (F, Finish D Tree. Move back to G Tree)  
Check the Right of G. (It's a tree)  
Grab the Root of I Tree. (I)  
Check the Left. (H, it's a leaf.)  
Check the Right. (K, it's a leaf. Finish G tree)  
DONE: G, D, B, A, C, E, F, I, H, K  

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.  
Check the Left of the G Tree. (It's a D Tree)  
Check the Left of the D Tree. (It's a B Tree)  
Check the Left of the B Tree. (A)  
Check the Root of the B Tree (B)  
Check the Right of the B Tree (C, finished B Tree!)  
Check the Right of the D Tree (It's a E Tree)  
Check the Left of the E Tree. (Nothing)  
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...  
Onwards until...   
DONE: A, B, C, D, E, F, G, H, I, K  

3) POSTORDER: 
LEFT, RIGHT, ROOT  
DONE: A, C, B, F, E, D, H, K, I, G

الاستخدام (ويعرف أيضًا باسم لماذا نهتم):
لقد استمتعت حقًا بشرح Quora البسيط لأساليب Depth First Traversal وكيفية استخدامها بشكل شائع:
"سيقوم اجتياز In-Order بطباعة القيم [بترتيب BST (شجرة البحث الثنائية)]"
"يتم استخدام اجتياز الطلب المسبق لإنشاء نسخة من [شجرة البحث الثنائية]."
"يتم استخدام اجتياز ما بعد الطلب لحذف [شجرة البحث الثنائية]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

Answer 4

وأعتقد أنه سيكون من المثير للاهتمام أن يكتب كل منهما بطريقة فقط عن طريق التحول بعض الأسطر من التعليمات البرمجية شأنه أن يوفر لك خوارزمية واحدة أو أخرى، حتى يتسنى لك أن نرى أن dillema ليست قوية جدا كما يبدو ل تكون في البداية.

وأنا شخصيا مثل تفسير BFS كما إغراق المشهد: سيتم غمرت المناطق المنخفضة الارتفاع أولا، وبعد ذلك فقط في المناطق المرتفعة ستتبع. إذا كنت تتخيل ارتفاعات المناظر الطبيعية وخطوط التساوي كما نرى في كتب الجغرافيا، من السهل أن نرى أن BFS يملأ كل منطقة تحت نفس isoline في نفس الوقت، كما أن هذا سيكون مع الفيزياء. وهكذا، وتفسير ارتفاعات كما المسافة أو تكلفة تحجيم يعطي فكرة بديهية جدا من الخوارزمية.

ومع وضع هذا في الاعتبار، يمكنك التكيف بسهولة الفكرة وراء اتساع أولا البحث للعثور على الحد الأدنى تغطي شجرة بسهولة، أقصر الطرق، وأيضا العديد من خوارزميات التقليل أخرى.

وأنا لم أرى أي تفسير بديهية من DFS بعد (فقط معيار واحد حول المتاهة، ولكن هو ليس قويا مثل BFS واحد والفيضانات)، لذلك بالنسبة لي يبدو أن BFS يبدو أن ربط أفضل مع الظواهر الفيزيائية كما هو موضح أعلاه، في حين DFS يرتبط بشكل أفضل مع الخيارات dillema على أنظمة عقلانية (أي شخص أو أجهزة الكمبيوتر البت فيها التحرك لجعل على لعبة الشطرنج أو الخروج من متاهة).

وهكذا، بالنسبة لي الفرق بين الأكاذيب التي ظاهرة طبيعية أفضل مباريات نموذج انتشارها (transversing) في الحياة الحقيقية.