假设我们有一个如下所示的图形。这个图形是彼得森图。顶点从0到9编号。每个顶点都有一些字母。考虑一个在该图中的行走w，其中使用了l个顶点。当行走w中的字母序列和s相同时，字符串s由行走w实现。我们可以多次访问顶点。
例如，一个字符串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 trueend
example的中文翻译为：示例#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
以上就是c程序中的peterson图问题的详细内容。