تحتاج إلى خوارزمية الرسم البياني مماثلة ل DFS

Question

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

لقد وجدت ال فئة ويكيبيديا لخوارزميات الرسم البياني ولكن هناك بحر صغير من الخوارزميات هنا ولست على دراية بمعظمها.

تحرير: مثال: إعطاء الرسم البياني {AB ، EB ، BC ، BD} ، Traverse AS: {A ، B ، E ، B ، C ، D} أو ترتيب فريد من نوعه كـ {a ، b ، e ، c ، d}. لاحظ أن هذه الخوارزمية بخلاف BFS أو DFS لا تحتاج إلى البدء مرة أخرى في عقدة بداية جديدة إذا تم استنفاد جميع مسارات العقدة الأولى.

Answer 1

في DFS ، عادة ما تختار قمة الرأس ليتم زيارتها بعد u بناءً على الحواف التي تبدأ من u. تريد اختيار استنادًا أولاً إلى الحواف التي تنتهي بك. للقيام بذلك ، يمكن أن يكون لديك تحويل الرسم البياني معلومات ، وحاول الحصول على قمة الرأس من هناك أولاً.

سيكون شيئًا من هذا القبيل:

procedure dfs(vertex u)
  mark u as visited
  for each edge (v, u) //found in transpose graph
    if v not visited
      dfs(v)
  for each edge (u, w)
    if v not visited
      dfs(w)

Answer 2

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

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

كود مزيف:

list topsort

procedure dfs(vertex u)
  mark u as visited
  for each edge (u, v)
    if v not visited
      dfs(v)
  add u to the back of topsort

القائمة topsort سيحتوي بعد ذلك على القمم بالترتيب العكسي الذي تريده. فقط عكس عناصر TopSort لتصحيح ذلك.

Answer 3

إذا كنت تبحث عن topological sort, ، يمكنك أيضًا القيام بذلك ، بالنظر إلى ملف قائمة المجاورة (أو قائمة الحواف (u,v) الذي يمكنك معالجته مسبقًا O(E) الوقت):

list top_sort( graph in adjacency list )
     parent = new list
     queue = new queue
     for each u in nodes
         parent(u) = number of parents
         if ( parent(u) is 0 ) // nothing points to node i
             queue.enqueue( u )

     while ( queue is not empty )
         u = queue.pop
         add u to visited
         for each edge ( u, v )
             decrement parent(v) // children all have one less parent
             if ( parent(v) is 0 )
                 queue.enqueue( v )

أعطى adjacency list (أو قائمة الحواف (u,v))، هذا هو O( V + E ), ، نظرًا لأن كل حافة تم لمسها مرتين - مرة واحدة إلى الزيادة ، مرة واحدة للتناقص ، في O(1) الوقت لكل. مع قائمة انتظار عادية ، سيتم أيضًا معالجة كل قاطرة بواسطة قائمة الانتظار على الأقل مرتين - والتي يمكن القيام بها أيضًا O(1) مع قائمة انتظار قياسية.

لاحظ أن هذا يختلف عن DFS (على الأقل تطبيق مباشر) من حيث أنه يعالج الغابات.

ملاحظة أخرى مثيرة للاهتمام هي أنه إذا بديلت queue مع priority_queue فرض نوع من البنية/الطلب ، يمكنك بالفعل إعادة النتائج في ترتيب ما.

على سبيل المثال ، للحصول على رسم بياني تبعية للفصل الكنسي (يمكنك فقط أخذ الفئة X إذا أخذت الفئة Y):

100:
101: 100
200: 100 101
201: 
202: 201

ربما تحصل ، نتيجة لذلك:

100, 201, 101, 202, 200

ولكن إذا قمت بتغييره حتى ترغب دائمًا في أخذ فصول ذات ترقيم أقل أولاً ، فيمكنك تغييرها بسهولة للعودة:

100, 101, 200, 201, 202