资 源 简 介
K r u s k a l算法每次选择n- 1条边,所使用的贪婪准则是:从剩下的
边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选
取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步,其中e 是网络中
边的数目。按耗费递增的顺序来考虑这e 条边,每次考虑一条边。当考虑某条边时,若将其
加入到已选边的集合中会出现环路,则将其抛弃,否则,将它选入。-K ruskal algorithm for each choice of n-1 edges, the greed of the criteria used are: from the left edge select does not produce a loop with the smallest cost edge has been selected to join the edge of the collection. Taking note of the selected edges have a loop if it can not form a spanning tree. K ruskal algorithm sub-e-step, in which e is the number of network edge. According to the order of incremental cost to consider this e edges, each taking a side. When considering a certain edge when, if its added to a collection of selected edge loop will appear, will be its discarded, otherwise, it selected.