Tutorialspoint.dev

A Peterson Graph Problem

The following graph G is called a Petersen graph and its vertices have been numbered from 0 to 9. Some letters have also been assigned to vertices of G, as can be seen from the following picture:
Let’s consider a walk W in graph G, which consists of L vertices W1, W2, …, WL. A string S of L letters 'A' – 'E' is realized by walk W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.

For example, S = 'ABBECCD' is realized by W = (0, 1, 6, 9, 7, 2, 3). Determine whether there is a walk W which realizes a given string S in graph G, and if so then find the lexicographically least such walk. The only line of input contains one string S. If there is no walk W which realizes S, then output -1 otherwise, you should output the least lexicographical walk W which realizes S.

Examples:

Input : s = 'ABB'
Output: 016
Explanation: As we can see in the graph
             the path from ABB is 016.
Input : s = 'AABE'
Output :-1
Explanation: As there is no path that
             exists, hence output is -1.



We apply breadth first search to visit each vertex of the graph.

// C++ program to find the
// path in Peterson graph
#include <bits/stdc++.h>
using namespace std;
  
// path to be checked 
char S[100005]; 
  
// adjacency matrix. 
bool adj[10][10];
  
// resulted path - way 
char result[100005];
  
// we are applying breadth first search
// here
bool findthepath(char* S, int v)
{
    result[0] = v + '0';
    for (int i = 1; S[i]; i++) {
          
        // first traverse the outer graph
        if (adj[v][S[i] - 'A'] || adj[S[i] -
                              'A'][v]) {
            v = S[i] - 'A';
        }
  
        // then traverse the inner graph
        else if (adj[v][S[i] - 'A' + 5] || 
                 adj[S[i] - 'A' + 5][v]) {
            v = S[i] - 'A' + 5;
        }
  
        // if the condition failed to satisfy
        // return false
        else 
            return false;
  
        result[i] = v + '0';
    }
  
    return true;
}
  
// driver code
int main()
{
    // here we have used adjacency matrix to make
    // connections between the connected nodes
    adj[0][1] = adj[1][2] = adj[2][3] = adj[3][4] = 
    adj[4][0] = adj[0][5] = adj[1][6] = adj[2][7] =
    adj[3][8] = adj[4][9] = adj[5][7] = adj[7][9] =
    adj[9][6] = adj[6][8] = adj[8][5] = true;
      
    // path to be checked
    char S[] = "ABB";
      
    if (findthepath(S, S[0] - 'A') || 
        findthepath(S, S[0] - 'A' + 5)) {
        cout << result;
    } else {
        cout << "-1";
    }
    return 0;
}

Output:

016

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Graph Graph

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter