首页 > 代码库 > 哈密尔顿环 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