首页 > 代码库 > 哈密尔顿环 dfs
哈密尔顿环 dfs
( ⊙ o ⊙ ) 题目:
(⊙v⊙)嗯,代码:
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int N = 25; 6 int n, cnt; 7 int a[N][N]; 8 int v[N], p[N]; 9 10 void print(){11 printf("Route #%d: ", ++cnt);//路径条数 12 for(int i=1; i<=p[0]; i++) printf("%d - ", p[i]);13 printf("1\n");14 }15 16 void dfs(int x){17 v[x] = 1, p[++p[0]] = x;18 if(p[0] == n) {19 if(a[p[0]][1]) print();20 }21 else for(int i=1; i<=n; i++)22 if(a[x][i] && !v[i]) dfs(i);23 v[x] = 0, p[p[0]] = 0, --p[0];//回溯过程 24 }25 26 int main(){27 scanf("%d", &n);28 for(int i=1; i<=n; i++)29 for(int j=1; j<=n; j++)30 scanf("%d", &a[i][j]);//输入一个表示i,j之间是否有边的矩阵 31 dfs(1);32 return 0;33 }
哈密尔顿环 dfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。