首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第九章“图论”——无权值的最短路径问题
《数据结构与算法分析：C语言描述》复习——第九章“图论”——无权值的最短路径问题
2014.07.04 18:24
简介：
给定一个有向图，你可以认为每条边长度都是1（所以叫无权值）。下面的算法可以求出从特定的起点到终点的最短路径长度。
描述：
从起点出发，根据当前顶点出发的边进行广度优先搜索，直至找到终点即可。如果搜索结束了仍然没有找到终点，那么起点无法到达终点。
实现：
1 // A simple illustration for unweighted shortest path. Graph represented by adjacency matrix. 2 #include <iostream> 3 #include <queue> 4 #include <vector> 5 using namespace std; 6 7 void unweightedShortestPath(const vector<vector<bool> > &graph, 8 vector<int> &dist, vector<bool> &reachable) 9 {10 // The minimal distances from 0th vertex to others.11 int n;12 int i, j;13 14 n = (int)graph.size();15 dist.resize(n);16 reachable.resize(n);17 18 if (n < 1) {19 return;20 }21 22 for (i = 0; i < n; ++i) {23 reachable[i] = false;24 }25 26 queue<int> q;27 28 dist[0] = 0;29 reachable[0] = true;30 31 q.push(0);32 while (!q.empty()) {33 i = q.front();34 q.pop();35 for (j = 0; j < n; ++j) {36 if (!graph[i][j] || reachable[j]) {37 continue;38 }39 dist[j] = dist[i] + 1;40 reachable[j] = true;41 q.push(j);42 }43 }44 }45 46 int main()47 {48 vector<vector<bool> > graph;49 vector<int> dist;50 vector<bool> reachable;51 int n;52 int nk;53 int i, j;54 int tmp;55 56 while (cin >> n && n > 0) {57 graph.resize(n);58 for (i = 0; i < n; ++i) {59 graph[i].resize(n, false);60 }61 62 for (i = 0; i < n; ++i) {63 cin >> nk;64 for (j = 0; j < nk; ++j) {65 cin >> tmp;66 graph[i][tmp] = true;67 }68 }69 70 unweightedShortestPath(graph, dist, reachable);71 72 for (i = 0; i < n; ++i) {73 cout << i << ": ";74 if (reachable[i]) {75 cout << dist[i] << endl;76 } else {77 cout << "Unreachable" << endl;78 }79 }80 81 for (i = 0; i < n; ++i) {82 graph[i].clear();83 }84 graph.clear();85 }86 87 return 0;88 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。