程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 一步一步寫算法(之克魯斯卡爾算法 上)

一步一步寫算法(之克魯斯卡爾算法 上)

編輯:關於C

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱: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;

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved