数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C 程序中的彼得森图问题？
假设我们有一个如下所示的图，该图是一个彼得森图。其中，顶点编号从 0 到 9。每个顶点都有一些字母。将考虑该图中的一个路径 W，其中使用 L 个顶点。当 W 和 S 中的字母序列相同时，则路径 W 会生成一个包含 L 个字母的字符串 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++){
//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
更新于： 19-8-2019
241 人次
广告