# 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.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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

 `// C++ program to find the ` `// path in Peterson graph ` `#include ` `using` `namespace` `std; ` ` `  `// path to be checked  ` `char` `S;  ` ` `  `// adjacency matrix.  ` `bool` `adj; ` ` `  `// resulted path - way  ` `char` `result; ` ` `  `// we are applying breadth first search ` `// here ` `bool` `findthepath(``char``* S, ``int` `v) ` `{ ` `    ``result = 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 = adj = adj = adj =  ` `    ``adj = adj = adj = adj = ` `    ``adj = adj = adj = adj = ` `    ``adj = adj = adj = ``true``; ` `     `  `    ``// path to be checked ` `    ``char` `S[] = ``"ABB"``; ` `     `  `    ``if` `(findthepath(S, S - ``'A'``) ||  ` `        ``findthepath(S, S - ``'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

Graph Graph

code

load comments