首页 > 代码库 > Graph-BFS-Fly-图的广度优先遍历-最小转机问题
Graph-BFS-Fly-图的广度优先遍历-最小转机问题
#include <iostream> #include <queue> using namespace std; /* 5 7 1 5 1 2 1 3 2 3 2 4 3 4 3 5 4 5 2 -------------------------------- Process exited with return value 0 Press any key to continue . . . */ class Node { public: Node(int _x, int _z); public: int x; int z; }; Node::Node(int _x, int _z) { this->x = _x; this->z = _z; } const int infinity = 999999; int vertx, edge, start, end; int Graph[20][20] = {0}, book[20] = {0}; queue<Node> qgraph; void BFS() { book[start] = 1; Node firstnode(start, 0); qgraph.push(firstnode); while(!qgraph.empty()) { int flag = 0; int x = qgraph.front().x; for(int i = 1; i <= vertx; i++) { if(Graph[x][i] != infinity && book[i] == 0) { book[i] = 1; Node node(i, qgraph.front().z + 1); qgraph.push(node); } if(qgraph.back().x == end) { flag = 1; break; } } if(flag == 1) { break; } qgraph.pop(); } return; } int main() { cin >> vertx >> edge >> start >> end; 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 j = 1; j <= edge; j++) { int x, y; cin >> x >> y; Graph[x][y] = 1; Graph[y][x] = 1; } BFS(); cout << endl << qgraph.back().z; return 0; }
Graph-BFS-Fly-图的广度优先遍历-最小转机问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。