哥尼斯堡的"七桥问题"
数据结构课程设计
题目:哥尼斯堡的“七桥问题”院系:
班级:
学号:
姓名:
2014-2015年度 第1学期
哥尼斯堡的“七桥问题”
一.
二. 题目:哥尼斯堡的“七桥问题” 设计目标
帮助学生熟练掌握图和邻接表的使用,了解利用图能够解决生活中的那些实际问题。
三. 问题描述
在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?
四. 概要设计
1> 构建用邻接表存储的图结构体:
2> 图的初始化
3> 读入并存储一个图G
4>图G的深度优先搜索
5>检查边的度是否全为偶数
五. 详细设计(给出算法的伪码描述和流程图)
总体操作步骤:
流程图设计:
主流程图:
1> 构建用邻接表存储的图结构体:
typedef struct {
int Visited[MAXV]; /* 顶点标记 */
int Edges[MAXV][MAXV]; /* 邻接表 */
int VertexN, EdgeN; /* 顶点和边数 */
} Graph;
2> 图的初始化:
3> 读入并存储一个图G
4> 图G的深度优先搜索
:
5> 检查边的度是否全为偶数
:
6> 主函数:
代码分析:
1> 图的初始化:
void InitializeG ( Graph *G )
{
int i, j;
for (i=0; i
{
for (j=0; j
G->Edges[i][j] = 0;
G->Visited[i] = 0;
}
G->VertexN = G->EdgeN = 0;
}
2> 读入并存储一个图G:
void ReadG ( Graph *G )
{ /* 读入并存储一个图G */
int i, V1, V2;
scanf(
for (i=0; iEdgeN; i++)
{
scanf(
G->Edges[V1-1][V2-1] = G->Edges[V2-1][V1-1] = 1;
}
}
3> 图G的深度优先搜索:
void DFS ( Graph *G, int V )
{ /* 图G的深度优先搜索 */
int W;
G->Visited[V] = 1; /* 将访问到的结点进行标记 */
for (W=0; WVertexN; W++)
if (G->Edges[V][W] && !G->Visited[W])
DFS(G, W);
}
4> 检查边的度是否全为偶数:
int CheckG ( Graph *G )
{ /* 检查边的度是否全为偶数 */
int r, i, j;
for (i=0; iVertexN; i++)
{
r = 0;
for (j=0; jVertexN; j++)
r += G->Edges[i][j];
if (r%2) return 0; /* 发现奇数度的边则返回0 */
}
return 1; /* 全是偶数度的边则返回1 */
}
5> 主函数:
int main()
{
int i;
Graph *G = malloc( sizeof(Graph) );
InitializeG( G );
ReadG( G );
DFS( G, 0 ); /* 检查连通性 */
for (i=0; iVertexN; i++)
if (!G->Visited[i])
break;
if (iVertexN) /* 若有结点没被DFS访问到 */
printf(
else /* 若图连通 */
printf(
return 0;
}
六. 测试分析
白盒:
查看代码完整性
黑盒:
测试是否可以正确的创建,删除,插入,打印,查找等操作
七. 使用说明
插入删除语句:删除1条内容
插入语句:插入一条信息
自动打印:打印内容
八. 测试数据
注:学生在测试数据时,需要写出测试用例和截图
十.课程设计总结
通过“哥尼斯堡的“七桥问题””这个题目,我认识到了图的使用,以及邻接表存储。在整个课程设计做完之后,我感觉到自己以前学到的东西还是理解不到位,通过这次课程设计反而学到了许多东西。以后我会继续保持之中状态在生活中多做练习,从而改进自己的不足!