数据结构实验3(飞机最少环城次数问题)
最后更新于：2022-04-01 20:52:00
使用图算法解决应用问题: 设有n个城市, 编号为0 ~ n - 1, m条航线的起点和终点由用户输入提供. 寻找一条换乘次数最少的线路方案.
使用有向图表示城市间的航线, 只要两城市之间有航班, 则图中这两点间存在一条权为1的边. 用Dijkstra算法实现求最少换乘次数.
在MGraph类中增加Choose函数以及Dijkstra函数即可.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
enum ResultCode { Underflow, Duplicate, Failure, Success, NotPresent, OutOfBounds };
template
class Graph
{
public:
virtual ~Graph() {};
virtual ResultCode Insert(int u, int v, T w) = 0;
virtual ResultCode Remove(int u, int v) = 0;
virtual bool Exist(int u, int v) const = 0;
/* data */
};
template
class MGraph: public Graph
{
public:
MGraph(int mSize, const T& noedg);
~MGraph();
ResultCode Insert(int u, int v, T w);
ResultCode Remove(int u, int v);
bool Exist(int u, int v) const;
int Choose(int *d, bool *vis);
void Dijkstra(int v, int *d, int *path);
int Vertices() const { return n; }
void Output();
protected:
T **a;
T noEdge;
int n, e;
/* data */
};
template
void MGraph::Output()
{
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j)
if(a[i][j] == noEdge) cout << "NE\t";
else cout << a[i][j] << "\t";
cout << endl;
}
cout << endl << endl << endl;
}
template
MGraph::MGraph(int mSize, const T &noedg)
{
n = mSize, e = 0, noEdge = noedg;
a = new T *[n];
for(int i = 0; i < n; ++i) {
a[i] = new T[n];
for(int j = 0; j < n; ++j)
a[i][j] = noEdge;
a[i][i] = 0;
}
}
template
MGraph::~MGraph()
{
for(int i = 0; i < n; ++i)
delete []a[i];
delete []a;
}
template
bool MGraph::Exist(int u, int v) const
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v || a[u][v] == noEdge) return false;
return true;
}
template
ResultCode MGraph::Insert(int u, int v, T w)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] != noEdge) return Duplicate;
a[u][v] = w;
e++;
return Success;
}
template
ResultCode MGraph::Remove(int u, int v)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] == noEdge) return NotPresent;
a[u][v] = noEdge;
e--;
return Success;
}
template
int MGraph::Choose(int *d, bool *vis)
{
int pos = -1;
T m = INF;
for(int i = 0; i < n; ++i)
if(d[i] <= m && !vis[i]) {
m = d[i];
pos = i;
}
return pos;
}
template
void MGraph::Dijkstra(int v, int *d, int *path)
{
if(v < 0 || v > n - 1) throw OutOfBounds;
bool *vis = new bool[n];
for(int i = 0; i < n; ++i) {
vis[i] = false;
d[i] = a[v][i];
if(i != v && d[i] < INF) path[i] = v;
else path[i] = -1;
}
vis[v] = true;
d[v] = 0;
for(int i = 1; i < n; ++i) {
int x = Choose(d, vis);
vis[x] = true;
for(int j = 0; j < n; ++j)
if(!vis[j] && d[x] + a[x][j] < d[j]) {
d[j] = d[x] + a[x][j];
path[j] = x;
}
}
}
int main(int argc, char const *argv[])
{
int n, m;
cout << "请输入城市个数:";
cin >> n;
cout << "请输入航线条数:";
cin >> m;
MGraph A(n, INF);
int c, f;
cout << "请输入每条航线的起点和终点: " << endl;
for(int i = 0; i < m; ++i)
{
cout << "航线" << i + 1 <<": ";
cin >> c >> f;
A.Insert(c, f, 1);
}
char s;
int i = 0, j = 0;
do{
int v, w;
cout << "请输入你的起点和终点:";
cin >> v >> w;
while(v < 0 || w < 0 || w > n - 1 || v > n - 1)
{
cout << "输入错误!请重新输入:";
cin >> v >> w;
}
int *b = new int[n];
int *d = new int[n];
int *path = new int[n];
A.Dijkstra(v, d, path);
int e = n - 1;
for(int j = 0; j < n; ++j)
b[j] = -2;
if(w != v)
{
j = w;
while(path[j] != -1)
{
b[e] = path[j];
e--;
j = path[j];
}
if(e == n - 1 || d[j] == INF) cout << "该路间无线路!" << endl;
else {
cout << "从" << v << "到" << w << "的换乘次数最小的线路方案为:";
for(int k = 0; k < n; ++k)
if(b[k] != -2) cout << b[k] << ",";
cout << w << endl;
}
}
if(w == v) cout << "从" << v << "到" << w << "该路间无需乘飞机!" << endl;
delete []b;
delete []d;
delete []path;
cout << "请问是否继续查询路线?请输入Y/N:";
cin >> s;
while(s != 'Y' && s != 'y' && s != 'n' && s != 'N') {
cout << "输入错误!请重新输入:";
cin >> s;
}
}while(s == 'Y' || s == 'y');
return 0;
}
~~~
';