摘要

在现实生活中，对于无向图研究有很高的实用价值。正确地理解掌握如何构造无向图以及遍历问题，将会给我们带来巨大的经济效益和社会效益。随着最小生成树理论与算法的发展与完善，其在现实生活中的应用越来越广泛。求最小生成树问题能在很多经济学问题中得到很好的应用。因此，对最小生成树在具体的经济学案例中的应用进行研究和完善是必须的，并且有着很高的经济价值，如“最小投资”应用前景非常广泛。

首先本文对图的一些基本知识进行了分析研究，主要说明了图论的一些基本定义和框架以及图论的相关术语，便于本文后面的论述和定力的证明。

其次本文介绍了无向图的一些基本知识，主要说明了图论的一些基本定义和框架以及图论的相关术语，便于本文后面的论述和定力的证明。

最后，对无向图的两种遍历算法进行了详细的说明和讲解，本文分别对无向图的最小度和最大度遍历进行了深入的研究和分析，给出了详细的C语言编码实现和复杂度分析。

本文采用的算法在构造的实际无向图进行实验，实际测试结果表明算法是可行且高效的，达到了算法设计的性能要求。

关键词：无向图，遍历，最大度，最小度

第一章 绪论

1.1 研究背景及意义

图论（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。

1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即（绕行世界）。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。

在图论的历史中，还有一个最著名的问题----四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。20世纪80-90年代曾邦哲的综合系统学（结构论）将“四色猜想”命题转换等价为“互邻面最大的多面体是四面体”。四色猜想有一段有趣的历史，每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接，所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。

总之，无向图的研究可以广泛应用于实际得调度和经济决策等问题中，其具有重要的理论研究价值和实际意义。

第三章 无向图最小度遍历算法设计

3.1 无向图最小度遍历算法概述

目前，求最小生成树的算法已经相当成熟，常用的经典算法有：避圈法(Kruskal算法)、边割法(Prim算法)、破圈法、Sollin算法、Dijkstra算法等。本章在对Prim算法分析的基础上，设计了该算法的Java语言程序，并通过对分公司及总公司间架设网络的实例研究来说明该算法的应用。

3.2 最小度遍历算法

3.2.1 算法思想

任意选取一节点 构成集合 ,然后不断在 中选一点 到 中某点（如： ）权最小的边 加入树T中，并令 直至 。

3.2.2 算法步骤

Step1 设 为 的任一顶点，令 。

Step2 若 ，结束，以 为顶点集， 为边集的图即是 的最小生成树；否则执行Step3。

Step3 构造 ,若 = ,则 不连通，停止；否则，设 ， ， ，令 ， 置 ，执行Step2。