सी प्रोग्राम में एक पीटरसन ग्राफ समस्या?

मान लीजिए हमारे पास नीचे जैसा एक ग्राफ है। वह ग्राफ पीटरसन ग्राफ है। शीर्षों को 0 से 9 तक क्रमांकित किया जाता है। प्रत्येक शीर्ष में कुछ अक्षर होते हैं। मान लीजिए कि उस ग्राफ में एक वाक W पर विचार किया जाता है, जहाँ L शीर्षों का उपयोग किया जाता है। W और S में अक्षर क्रम समान होने पर L अक्षर के साथ एक स्ट्रिंग S को W द्वारा महसूस किया जाता है। हम कई बार शिखर पर जा सकते हैं।

उदाहरण के लिए, एक स्ट्रिंग एस "एबीबीईसीसीडी" की तरह है, यह चलने (0, 1, 6, 9, 7, 2, 3) द्वारा महसूस किया जाता है। हमारा काम है ऐसे वॉक को ढूंढना, और अगर वो वॉक मौजूद है, तो लेक्सिकोग्राफिक रूप से कम से कम ऐसे वॉक को खोजें। अगर कोई सक्स वॉक नहीं है, तो वापसी -1.

एल्गोरिदम

पीटरसनग्राफवॉक (एस, वी) -

begin
   res := starting vertex
   for each character c in S except the first one, do
      if there is an edge between v and c in outer graph, then      
         v := c
      else if there is an edge between v and c+5 in inner graph, then
         v := c + 5
      else
         return false
      end if
         put v into res
      done
   return true
end

उदाहरण

#include<iostream>
using namespace std;
bool adj_mat[10][10] = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0},
   {1, 0, 1, 0, 0, 0, 1, 0, 0, 0},
   {0, 1, 0, 1, 0, 0, 0, 1, 0, 0},
   {0, 0, 1, 0, 1, 0, 0, 0, 1, 0},
   {1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
   {1, 0, 0, 0, 0, 0, 0, 1, 1, 0},
   {0, 1, 0, 0, 0, 0, 0, 0, 1, 1},
   {0, 0, 1, 0, 0, 1, 0, 0, 0, 1},
   {0, 0, 0, 1, 0, 1, 1, 0, 0, 0},
   {0, 0, 0, 0, 1, 0, 1, 1, 0, 0}
};
char S[100005];
char res[100005];
bool petersonGraphWalk(char* S, int v){
   res[0] = v + '0';
   for(int i = 1; S[i]; i++){
      //traverse the outer graph
      if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){
         v = S[i] - 'A';
      }
      //then check the inner graph
      else if(adj_mat[v][S[i] - 'A' + 5] || adj_mat[S[i] - 'A' + 5][v]){
         v = S[i] - 'A' + 5;
      }else{
         return false;
      }
      res[i] = v + '0';
   }
   return true;
}
main() {
   char* str = "ABBECCD";
   if(petersonGraphWalk(str, str[0] - 'A') || petersonGraphWalk(str, str[0] - 'A' + 5)){
      cout << res;
   }else{
      cout << -1;
   }
}

आउटपुट

0169723