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

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

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

एल्गोरिदम

petersonGraphWalk(S, v) -

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++){
        // बाहरी ग्राफ को पार करें
        if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){
            v = S[i] - 'A';
        }
        // फिर आंतरिक ग्राफ जांचें
        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;
    }
}

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

एल्गोरिदम

उदाहरण

आउटपुट