首页 > 代码库 > Graph-DFS-Map-图的深度优先遍历-城市地图问题
Graph-DFS-Map-图的深度优先遍历-城市地图问题
#include <iostream> using namespace std; /* 5 8 1 2 2 1 5 10 2 3 3 2 5 7 3 1 4 3 4 4 4 5 5 5 3 3 min: 9 -------------------------------- Process exited with return value 0 Press any key to continue . . . */ const int infinity = 999999; int minnum = infinity; int vertx, edge; int Graph[20][20] = {0}, book[20] = {0}; void DFS(int _n, int _dis) { if(_dis > minnum) return; if(_n == vertx) { if(_dis < minnum) { minnum = _dis; } return; } for(int i = 1; i <= vertx; i++) { if(Graph[_n][i] != infinity && book[i] == 0) { book[i] = 1; DFS(i, _dis + Graph[_n][i]); book[i] = 0; } } } int main() { cin >> vertx >> edge; for(int i = 1; i <= vertx; i++) { for(int j = 1; j <= vertx; j++) { if(i == j) { Graph[i][j] = 0; } Graph[i][j] = infinity; } } for(int i = 1; i <= edge; i++) { int x, y, z; cin >> x >> y >> z; Graph[x][y] = z; } DFS(1, 0); cout << endl << "min: " << minnum; return 0; }
Graph-DFS-Map-图的深度优先遍历-城市地图问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。