图论中贪心算法的应用

杨迪

【摘要】 在对一些图论问题求解中，应用贪心算法能够快速地、准确地求解，受到了很多工作者的肯定和使用.本文简单地介绍贪心算法解题思想，并在两个典型实例的分析下，阐明了图论中心贪心算法的实际运用.

【关键词】 图论；贪心算法；应用

在求解一些问题中，贪心算法作为一种优解的有效算法，能够快速地、有效地解决很多实际存在的问题，被广泛运用在图论领域中.虽然贪心算法也有不足之处，如应用范畴比较狭窄，但对于图论有些问题，贪心算法既可以正确求解，也有着很高的应用价值.

一、概述贪心算法

贪心算法是一种分级处理方法，在决策中，贪心算法总会对当前情况进行最好的选择.与动态规划算法不同的是，贪心算法并不考虑问题的整体最优，而只是考虑某种意义上的局部最优.因此，贪心算法并未结合所有问题求得整体最优解，但对于一些问题来讲，它可以求得整体最优解.在一些状况下，虽然贪心算法并未得到整体最优解，但是能够得到与最优解的近似，所以，贪心算法有着很高的应用价值.

二、贪心算法的求解步骤

1.基本要素.对于一个切实存在的问题，怎样才能知道是否能够用贪心算法求解并得到最优解，在具体应用过程中，人们研究和总结出两个重要性质：一是，贪心选择的性质；二是，最优子结构的性质.很多使用贪心方法求解问题中都会具有这两个性质.

2.步骤的求解.贪心算法的求解先要明确出一个贪心准则，每步都按照此准则进行方案优化.排序各个问题，排一次输一个量.假若这个输入与已构成的量最优解加在一起后很难出现可行解，这样就不能将输入值与这部分解相融合.

三、使用贪心算法对单源点最短路径求解的可行性

在图论中存在一个很典型的问题：单源点最短路径这一问题.对问题的描述如下：对于有向带权图G=（V，E），其每条边上的权重都是非负实数.选定在V中某个顶点，称为源点.此问题求解的是从源点到图G中其各个顶点的最短路径长度.在这里所讲的长度就是指通过各个边的权值总和.Dijkstra正是运用贪心算法求解这个问题，用所有路径长度之和作为最小贪心准则，所以，每个单独路径都要有最小长度.实现此算法步骤是：将顶点集合分为两个子集，即：S，V-S.在子集S中将所有最短路径顶点都已求得.在初始时，集合S中有源点，然后，将其做贪心来扩充此集合.选取在G中顶点V，从源点到V点并通过S中顶点的路径称之为源点到顶点V的特殊路径，设置数组Dirt记录各个顶点对应的最短特殊路径长度.

四、应用贪心算法求解最小生成树的可行性

（一）Kruskal算法的应用

对于最小生成树图论的讨论是非常有价值和有意义的，具体描述包括如下几点：已知无项连通带权图 G=（V，E）.E中每条边（u，v）的权值设为c[u][v].求图G的生成树G′，使G′上各边权值的总和是所有生成树中各边权值中总和最小.此问题被称为最小生成树问题.求解最小生成树问题有很 多种方法，其中Kruskal、Prim等算法应用最为广泛.

Kruskal算法与Prim算法相比，在生成最小生成树中，前者比后者更加简洁明了.一是将无向连通带权图 G的n个顶点视为n个 独立的分支，但这几个分支间是互相连通的.并根据权值给各个边从小至大展開排序.将第一条边与连通分支进行相连，之后按照权值递增顺序检查剩下的各个边，若加入此边就构成回路，就抛弃此边，然后，考察余下每条边；反之，加入此边并不会构成回路，就将此边加入.

（二）Prim算法的应用

Prim算法思想是：一是在图中选取一个顶点u，将u置于顶点集合子集S里.若S是顶点集合V的真子集，就应该将顶点加入子集S中，但要满足iI ^ S，jI ^ V-S条件，并且C[i][j]是权值最小的一个边.根据同样的步骤进行贪心选择，直至子集S=V结束.在这时，已被选取的边就构成了在图G中的一颗小生成树.

在对比上文两种方法后才发现，这两种方法虽然都是使用贪心算法解决问题，但由于贪心准则不同的影响，最小生成树选边与求解步骤也是不同的，所以，在实际应用贪心算法中，需要因地制宜地应用，盲目、一味地应用贪心算法，很容易引发其他方面的问题，但相对而言，贪心算法还是值得大范围地应用的.

五、结 语

总而言之，图论中还有一些问题很难解决，贪心算法是否能够解决这些问题，还需要深入地探讨和研究.同时，想要在图论中充分应用贪心算法，这就需要有关工作者必须要全面掌握和了解贪心算法，能够熟练、准确地应用，确保贪心算法能够发挥作用，解决好图论中一些疑难问题.