数据结构课程设计报告《图的遍历》(9)

{

if(!visited[w])

{

visited[w]=1;

visitvex(g,w);

enqueue(q,w);

}

}

}

}

}

}

4、测试与分析：

针对下图进行测试和分析：

由图已知有8个结点，根据提示“Please input the number of vertex:”输入“8”。再根据图输入邻接矩阵中有关系的两点，两点有关系只要输入一次即可。当输入完所有关系后输入“0，0”再输入回车，程序将输出该图邻接矩阵。再根据提示选择“b”，“d”或“q”。选“b”表示广度优先搜索（Breadth_First Search），“d”表示深度优先搜索（Depth_First Search），“q”表示退出。

Please input the number the number of vertex:

8

Please input R<0,0 END>:

1,2

2,4

4,8

5,8

2,5

1,3

3,6

3,7

0,0

This is the linjiejuzhen of graph:

0 1 1 0 0 0 0 0

1 0 0 1 1 0 0 0

1 0 0 0 0 1 1 0

0 1 0 0 0 0 0 1

0 1 0 0 0 0 0 1

0 0 1 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 1 0 0 0

Please input b or d or q,Breadth_first: b Depth_first: d quit: q b

Breadth_first:

1 2 3 4 5 6 7 8

Please input b or d or q,Breadth_first: b Depth_first: d quit: q d

Depth_fitst:

1 2 4 8 5 3 6 7

Please input b or d or q,Breadth_first: b Depth_first: d quit: q q

Press any key to contine

运行结果正确此程序可用

四、设计总结：

图的遍历是程序设计语言编译中的一个最基本问题。“图的遍历”是数据结构中主要的内容之一，也是重要的内容之一。它是树的遍历的拓展，但要比树的遍历复杂得多，是排序等的基础。它运用了深度优先遍历，广度优先遍历，入队，出队等多种运算，很有意义，是对数据结构一些基本操作的综合应用。

在做设计的开始就遇到了很多困难，比如，如何才能构造邻接矩阵，如何将邻接矩阵表示出来，如何将结果输出，以及深度优先搜索和广度优先搜索的用C语言表达等。在仔细研究教材寻找资料后，并和同学一同探讨最终将困难解决。

本次课程设计是学习数据结构后的一次具体的实践，体现了理论与实践的有效结合。在实践中体现出理论的思想，在实践中深入了解理论的具体实质，在实践中明白理论的精髓所在。同样也很好地锻炼了我自己动手动脑的的能力！