图论是一门古老的学科,它的诞生可追溯到1736年。在离散数学领域内,图论占有主导地位。图论具有直观、清晰、解决问题简捷等特点,更重要的是,实际中的许多实际问题可以划成等价的图论问题。正因为如此,图论具有广泛的应用价值,图论可将各种复杂的工程系统和管理问题用“图”来描述,然后用数学方法求得最优结果。图论中所研究的“图”,是由若干个点,称作顶点和若干条连接两顶点的线段称作边,组成。通常顶点可用来表示事物,边用来表示这些事物之间的关系。顶点的位置、边的长短是无关紧要的,当是可以设定不同的边的权值来表示顶点问的关系强弱。图论是解决许多工程问题中算法设计的一种有效地数学模型,便于计算分析和计算机存储。算法是解决问题的一系列步骤的集合。因此,算法设计与分析对于问题的解决至关重要。作为离散数学重要的组成部分,图论已成为当今算法设计中的一项重要内容。因为图论与算法问题有着密切关系,“图”为一些算法问题提供了一个直观的数学平台,图的理论也为这些算法的实现提供了理论依据。事实上,众多的算法问题都直接或间接地与图有关。例如在NP完全问题中有相当一部分是图论问题或与“图”有关。基于图论的上述优点,从而将图论的相关理论引用到算法设计中来。本文首先介绍一些图论的理论以及他们的应用。从最小生成树得到的算法出发,分析和总结最小生成树算法的优点和不足,进而提出一种基于最小生成树的改进算法应用于聚类分析算法中,之后对算法进行了分析,从中解释它在解决一些聚类问题的高效性优点。