C ++ موجه عمق الرسم البياني البحث الأول

Question

أحاول كتابة طريقة DFS للرسوم البيانية الموجه. الآن أنا أواجه خطأ تجزئة ، وأنا غير متأكد حقًا من مكانه. من ما أفهمه من الرسوم البيانية الموجهة ، أعتقد أن منطقي صحيح ... لكن مجموعة جديدة من العيون ستكون مساعدة لطيفة للغاية.

ها هي وظيفتي:

void wdigraph::depth_first (int v) const {

static int fVertex = -1;
static bool* visited = NULL;

if( fVertex == -1 ) {
   fVertex = v;
   visited = new bool[size];
   for( int x = 0; x < size; x++ ) {
      visited[x] = false;
   }
}

cout << label[v];
visited[v] = true;

for (int v = 0; v < adj_matrix.size(); v++) {
   for( int x = 0; x < adj_matrix.size(); x++) {
     if( adj_matrix[v][x] != 0 && visited[x] != false ) {
        cout << " -> ";
        depth_first(x);
     }
     if ( v == fVertex ) {
        fVertex = -1;
        delete [] visited;
        visited = NULL;
     }
   }
}
}

تعريف الفئة:

class wdigraph {
public:
wdigraph(int =NO_NODES);          // default constructor
~wdigraph() {};                   // destructor
int get_size() { return size; }   // returns size of digraph

void depth_first(int) const;// traverses graph using depth-first search
void print_graph() const;   // prints adjacency matrix of digraph

private:
int size;                         // size of digraph
vector<char> label;               // node labels
vector< vector<int> > adj_matrix; // adjacency matrix
};

شكرًا!

Answer 1

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

تفترض الوظيفة أن مصفوفة المجاورة مربعة ، ولكن لا يتم عرض رمز التهيئة ، لذلك يجب فحصه. يمكن إزالة الافتراض عن طريق جعل حالة الحلقة الداخلية adj_matrix[v].size() (إعطاء عقدة v) أو غير ذلك إذا كان هذا ثابتًا ، أضف تأكيدًا قبل تلك الحلقة الداخلية: assert( adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!" ); -الشيء نفسه ينطبق على العضو size وحجم adj_matrix بحد ذاتها.

تبدو الخوارزمية بأكملها أكثر تعقيدًا مما ينبغي ، فإن DFS تبدأ في العقدة V لها الشكل العام لـ:

dfs( v )
   set visited[ v ]
   operate on node (print node label...)
   for each node reachable from v:
      if not visited[ node ]:
         dfs( node )

يبدو أن الخوارزمية الخاصة بك (بشكل غير صحيح بالمناسبة) تحفز الرسم البياني في الاتجاه المعاكس. قمت بتعيين العقدة المعطاة visited, ، ثم حاول تحديد موقع أي عقدة هي نقطة بداية الحافة لتلك العقدة. هذا هو ، بدلاً من اتباع العقد يمكن الوصول إليه من v, ، أنت تحاول الحصول على العقد التي v يمكن الوصول إليه. إذا كان هذا هو الحال (أي إذا كان الهدف هو طباعة جميع المسارات التي تتقارب فيها v) ثم يجب أن تكون حريصًا على عدم ضرب نفس الحافة مرتين أو ستنتهي في حلقة لا حصر لها -> stackoverflow.

لترى أنك ستنتهي بـ Stackoverlow ، فكر في هذا المثال. عقدة البداية 1. يمكنك إنشاء visited موقف المتجه والعلامة 1 كما زار. تجد أن هناك حافة (0،1) في الشجرة ، وهذا يؤدي إلى IF: adj_matrix[0][1] != 0 && visited[1], ، لذلك يمكنك الدخول بشكل متكرر مع وجود عقدة البداية 1 تكرارا. هذه المرة لا تقوم ببناء البيانات الإضافية ، لكن الملاحظة visited[1], ، أدخل الحلقة ، ابحث عن نفس الحافة واتصل بشكل متكرر ...

Answer 2

أنت حذف visited قبل نهاية البرنامج. العودة إلى قمة البداية لا يعني أنك انتهيت. على سبيل المثال ، بالنسبة للرسم البياني لـ V = {1،2،3} ، E = {(1،2) ، (2،1) ، (1،3)}.

أيضا ، لاحظ أنك تستخدم v كمعلمة الإدخال وأيضًا كمتغير من أجل الحلقة.

Answer 3

أرى بعض المشاكل:

السطر التالي

 if( adj_matrix[v][x] != 0 && visited[x] != false ) {

يجب أن يتغير إلى

 if( adj_matrix[v][x] != 0 && visited[x] == false ) {

(تريد أن تتكرر فقط على القمم التي لديها ليس تمت زيارته بالفعل.)

أيضًا ، أنت تقوم بإنشاء متغير جديد v في ال for حلقة تخفي المعلمة v: هذا قانوني C ++ ، لكنها دائمًا فكرة فظيعة.