首页 > 代码库 > 图的深度优先搜索

图的深度优先搜索

#include<iostream>using namespace std;#define MAX 9999int book[101],n,e[101][101],min=MAX;
//cur是当前所在的城市,dis是当前已经走过的路径void dfs(int cur,int dis){ int j; if(dis>min) return; if(cur==n) { if(dis<min) min=dis; return; } for(j=1;j<=n;j++) {if(e[cur][j]!=MAX&&book[j]==0) { book[j]=1; dfs(j,dis+e[cur][j]); book[j]=0; } } return;}int main(){ int i,j,m,a,b,c; cin>>n>>m; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==j) e[i][j]=0; else e[i][j]=MAX; } } for(i=1;i<=m;i++) { cin>>a>>b>>c; e[a][b]=c; } book[1]=1; dfs(1,0); cout<<min; return 0;}

 

图的深度优先搜索