下面的图G称为彼得森图，其顶点的编号从0到9。一些字母也被分配给G的顶点，如下图所示： 让我们考虑图G中的步行W，它由L顶点W1、W2、…、WL组成。如果沿W书写的字母序列等于S，则L字母“A”–“E”的字符串S可通过行走W实现。沿W行走时，可多次访问顶点。 例如，S=’abbecd’由W=（0,1,6,9,7,2,3）实现。确定图G中是否存在实现给定字符串S的行走W，如果是，则从词典学角度找到最少的行走。输入的唯一一行包含一个字符串S。如果没有实现S的walk W，则输出-1，否则，您应该输出实现S的最小词典学walk W。
null
![图片[1]-彼得森图问题-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_Petersen1tinysvg-300x300.png)
例如：
Input : s = 'ABB'Output: 016Explanation: As we can see in the graph the path from ABB is 016.Input : s = 'AABE'Output :-1Explanation: As there is no path that exists, hence output is -1.
我们应用广度优先搜索来访问图的每个顶点。
C++
// 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; } |
JAVA
// Java program to find the // path in Peterson graph class GFG { // path to be checked static char []S = new char [ 100005 ]; // adjacency matrix. static boolean [][]adj = new boolean [ 10 ][ 10 ]; // resulted path - way static char [] result = new char [ 100005 ]; // we are applying breadth first search // here static boolean findthepath( char [] S, int v) { result[ 0 ] = ( char ) (v + '0' ); for ( int i = 1 ; i<( int )S.length; 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] = ( char ) (v + '0' ); } return true ; } // Driver code public static void main(String[] args) { // 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" .toCharArray(); if (findthepath(S, S[ 0 ] - 'A' ) || findthepath(S, S[ 0 ] - 'A' + 5 )) { System.out.print(result); } else { System.out.print( "-1" ); } } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find the # path in Peterson graph # path to be checked # adjacency matrix. adj = [[ False for i in range ( 10 )] for j in range ( 10 )] # resulted path - way result = [ 0 ] # we are applying breadth first search # here def findthepath(S, v): result[ 0 ] = v for i in range ( 1 , len (S)): # first traverse the outer graph if (adj[v][ ord (S[i]) - ord ( 'A' )] or adj[ ord (S[i]) - ord ( 'A' )][v]): v = ord (S[i]) - ord ( 'A' ) # then traverse the inner graph elif (adj[v][ ord (S[i]) - ord ( 'A' ) + 5 ] or adj[ ord (S[i]) - ord ( 'A' ) + 5 ][v]): v = ord (S[i]) - ord ( 'A' ) + 5 # if the condition failed to satisfy # return false else : return False result.append(v) return True # driver code # 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 S = "ABB" S = list (S) if (findthepath(S, ord (S[ 0 ]) - ord ( 'A' )) or findthepath(S, ord (S[ 0 ]) - ord ( 'A' ) + 5 )): print ( * result, sep = "") else : print ( "-1" ) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to find the // path in Peterson graph using System; public class GFG { // adjacency matrix. static bool [,]adj = new bool [10, 10]; // resulted path - way static char [] result = new char [100005]; // we are applying breadth first search // here static bool findthepath(String S, int v) { result[0] = ( char ) (v + '0' ); for ( int i = 1; i < S.Length; 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] = ( char ) (v + '0' ); } return true ; } // Driver code public static void Main(String[] args) { // 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 String S = "ABB" ; if (findthepath(S, S[0] - 'A' ) || findthepath(S, S[0] - 'A' + 5)) { Console.WriteLine(result); } else { Console.Write( "-1" ); } } } // This code is contributed by aashish1995 |
输出：
016
本文由 苏尼迪·乔杜里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
