一步一步写算法（之克鲁斯卡尔算法 上）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

  克鲁斯卡尔算法是计算最小生成树的一种算法。和prim算法（上，中，下）按照节点进行查找的方法不一样，克鲁斯卡尔算法是按照具体的线段进行的。现在我们假设一个图有m个节点，n条边。首先，我们需要把m个节点看成m个独立的生成树，并且把n条边按照从小到大的数据进行排列。在n条边中，我们依次取出其中的每一条边，如果发现边的两个节点分别位于两棵树上，那么把两棵树合并成为一颗树；如果树的两个节点位于同一棵树上，那么忽略这条边，继续运行。等到所有的边都遍历结束之后，如果所有的生成树可以合并成一条生成树，那么它就是我们需要寻找的最小生成树，反之则没有最小生成树。

    上面的算法可能听上去有些费解，我们可以用一个示例说明一下，

?/*

*          9

*    D -----------

*  3 |           |

*    |      6    |

*    A  -------  B 

*    |           |

*    |   7       | 5

*    -------C----

**/ 

/*

*          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，下面就开始计算，我们首先默认所有的点都是单独的最小生成树，

copy to clipboardprint?/*

*          

*    D 

*         

*    A           B 

*         

*          C

**/ 

/*

*         

*    D

*        

*    A           B

*        

*          C

**/    第一步，按照从小到大的顺序，我们加入最小的边A-D，

copy to clipboardprint?/*

*          

*    D 

*  3 |      

*    |      

*    A           B 

*

*

*           C

**/ 

/*

*         

*    D

*  3 |     

*    |     

*    A           B

*

*

*           C

**/    然后，我们发现下面最小的边是B-C，

copy to clipboardprint?/*

*          

*    D 

*  3 |      

*    |      

*    A           B 

*                |

*                | 5

*           C----

**/ 

/*

*         

*    D

*  3 |     

*    |     

*    A           B

*                |

*                | 5

*           C----

**/    接着，我们发现最小的边是A-B，因为点A和点B位于不同的最小生成树上面，所以继续合并，

copy to clipboardprint?/*          

*    D 

*  3 |      

*    |     6 

*    A---------- B 

*                |

*                | 5

*           C----

**/ 

/*         

*    D

*  3 |     

*    |     6

*    A---------- B

*                |

*                | 5

*           C----

**/

    接下来，我们还会遍历A-C，B-D，但是我们发现此时边的节点都已经遍历过了，所以均忽略，最小生成树的结构就是上面的内容。

    那么最小生成树的数据结构是什么，应该怎么定义，不知道朋友们还记得否？我们曾经在prim算法中讨论过，

copy to clipboardprint?/* 直连边*/ 

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; 

/* 直连边*/

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;