首页 > 代码库 > 一步一步写算法（之克鲁斯卡尔算法 上）
一步一步写算法（之克鲁斯卡尔算法 上）
原文: 一步一步写算法（之克鲁斯卡尔算法 上）
【未完，待续】
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
克鲁斯卡尔算法是计算最小生成树的一种算法。和prim算法（上，中，下）按照节点进行查找的方法不一样，克鲁斯卡尔算法是按照具体的线段进行的。现在我们假设一个图有m个节点，n条边。首先，我们需要把m个节点看成m个独立的生成树，并且把n条边按照从小到大的数据进行排列。在n条边中，我们依次取出其中的每一条边，如果发现边的两个节点分别位于两棵树上，那么把两棵树合并成为一颗树；如果树的两个节点位于同一棵树上，那么忽略这条边，继续运行。等到所有的边都遍历结束之后，如果所有的生成树可以合并成一条生成树，那么它就是我们需要寻找的最小生成树，反之则没有最小生成树。
上面的算法可能听上去有些费解，我们可以用一个示例说明一下，
/** 9* D -----------* 3 | |* | 6 |* A ------- B * | |* | 7 | 5* -------C----**/现在有这么4个点。其中 A-D 为3， A-C为7，A-B为6，B-D为9，B-C为5，下面就开始计算，我们首先默认所有的点都是单独的最小生成树，
/** * D * * A B * * C**/第一步，按照从小到大的顺序，我们加入最小的边A-D，
/** * D * 3 | * | * A B *** C**/然后，我们发现下面最小的边是B-C，
/** * D * 3 | * | * A B * |* | 5* C----**/接着，我们发现最小的边是A-B，因为点A和点B位于不同的最小生成树上面，所以继续合并，
/* * D * 3 | * | 6 * A---------- B * |* | 5* C----**/接下来，我们还会遍历A-C，B-D，但是我们发现此时边的节点都已经遍历过了，所以均忽略，最小生成树的结构就是上面的内容。
那么最小生成树的数据结构是什么，应该怎么定义，不知道朋友们还记得否？我们曾经在prim算法中讨论过，
/* 直连边 */typedef struct _DIR_LINE{ int start; int end; int weight; struct _DIR_LINE* next;}DIR_LINE;/* 最小生成树 */typedef struct _MINI_GENERATE_TREE{ int node_num; int line_num; int* pNode; DIR_LINE* pLine;}MINI_GENERATE_TREE;/* 节点边信息 */typedef struct _LINE{ int end; int weight; struct _LINE* next;}LINE;/*节点信息*/typedef struct _VECTEX{ int start; int number; LINE* neighbor; struct _VECTEX* next;}VECTEX;/* 图信息 */typedef struct _GRAPH{ int count; VECTEX* head;}GRAPH;【未完，待续】
一步一步写算法（之克鲁斯卡尔算法 上）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。