資料結構
網路
關係資料庫管理系統
作業系統
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 人次
廣告