数据结构实验七.doc

文档介绍：实验报告
(2014 / 2015 学年第一学期)
课程名称
数据结构——使用C++语言描述
实验名称
图的基本运算及飞机换乘次数最少问题
实验时间
2014
年
12
月
3
日
指导单位
计算机科学与技术系
指导教师
学生姓名
班级学号
学院(系)
专业
实验报告
实验名称
图的基本运算及飞机换乘次数最少问题
指导教师
实验类型
上机
实验学时
4
实验时间
2014年12月3日
实验目的和要求
验证在邻接矩阵和邻接表实现图的基本运算的算法;在邻接矩阵存储结构上实现图的深度和宽度优先遍历算法。
,编号为0~n−1,m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。
提示:可以使用有向图表示城市间的航线。只要两城市间有航班,则图中这两点间存在一条权为1的边。可以使用Dijkstra算法实现。
思考:如果是城市公交车的最少换乘问题,将如何解决?假如希望使用类似的算法,则图中的边如何设置?
二、实验环境(实验设备)
Vs2013
实验原理及内容:
实验一:
1)掌握在图的邻接矩阵和邻接表存储结构实现图的基本运算的算法
2)学****使用图算法解决应用问题的方法
邻接矩阵的遍历与邻接表的遍历类似,都是通过递归来实现。以下是代码:
void ExtMGraph<T>::DFS()
{
bool *visited = new bool[n];
for (int i = 0; i<n; i++)
visited[i] = false;
for (i = 0; i<n; i++)
{
if (!visited[i])
{
DFS(i, visited);
cout << endl;
}
}
delete[]visited;
}
template<class T>
void ExtMGraph<T>::DFS(int v, bool *visited)
{
visited[v] = true;
cout << " " << v;
for (int u = 0; u<n; u++)
if (a[v][u] != noEdge && !visited[u])
DFS(u, visited);
}
template<class T>
void ExtMGraph<T>::BFS()
{
bool *visited = new bool[n];
for (int i = 0; i<n; i++)
visited[i] = false;
for (int i = 0; i<n; i++)
{
if (!visited[i])
{
BFS(i, visited);

}
}
delete[]visited;
}
template<class T>
void ExtMGraph<T>::BFS(int v, bool *visited)
{
SeqQueue<int>q(Vertices());
visited[v] = true;
cout << " " << v;
(v);
while (!())
{
(v);
();
for (int i = 0; i<n; i++)
if (!visited[i] && a[v][i] != noEdge)
{
visited[i] = true;
cout << " " << i;
(i);
}
}
}
在主函数中只要添加该代码:
#include””
void main()
{
int weight = 3;
int noEdge = 1000;
int k = 1; int l = 2;
ExtMGraph<int> extMGraph2(8,noEdge);
(1, 2, k);
(1, 4, k);
(2, 3, k);
(4, 3, k);
(4, 5, k);
(3, 6, k);
(5, 7, k);
(6, 7, k);
extMGra