绣春刀修罗战场豆瓣:一步一步写算法（之prim算法 中）

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

C）编写最小生成树，涉及创建、挑选和添加过程

view plaincopy to clipboardprint?

1. MINI_GENERATE_TREE* get_mini_tree_from_graph(GRAPH* pGraph)
2. {
3. MINI_GENERATE_TREE* pMiniTree;
4. DIR_LINE pDirLine;
6. if(NULL == pGraph || NULL == pGraph->head)
7. return NULL;
9. pMiniTree = (MINI_GENERATE_TREE*)malloc(sizeof(MINI_GENERATE_TREE));
10. assert(NULL != pMiniTree);
11. memset(pMiniTree, 0, sizeof(MINI_GENERATE_TREE));
13. pMiniTree->node_num = 1;
14. pMiniTree->pNode = (int*)malloc(sizeof(int) * pGraph->count);
15. memset(pMiniTree->pNode, 0, sizeof(int) * pGraph->count);
16. pMiniTree->pNode[0] = pGraph->head->start;
18. while(1){
19. memset(&pDirLine, 0, sizeof(DIR_LINE));
20. get_dir_line_from_graph(pGraph, pMiniTree, &pDirLine);
21. if(pDirLine.start == 0)
22. break;
24. pMiniTree->line_num ++;
25. insert_line_into_queue(&pMiniTree->pLine, pDirLine.start, pDirLine.end, pDirLine.weight);
26. insert_node_into_mini_tree(&pDirLine, pMiniTree);
27. }
29. return pMiniTree;
30. }

view plaincopy to clipboardprint?

1. void get_dir_line_from_graph(GRAPH* pGraph, MINI_GENERATE_TREE* pMiniTree, DIR_LINE* pDirLine)
2. {
3. DIR_LINE* pHead;
4. DIR_LINE* prev;
5. VECTEX* pVectex;
6. LINE* pLine;
7. int index;
8. int start;
10. pHead = NULL;
11. for(index = 0; index < pMiniTree->node_num; index++){
12. start = pMiniTree->pNode[index];
13. pVectex = find_vectex_in_graph(pGraph->head, start);
14. pLine = pVectex->neighbor;
16. while(pLine){
17. insert_line_into_queue(&pHead, start, pLine->end, pLine->weight);
18. pLine = pLine->next;
19. }
20. }
22. if(NULL == pHead)
23. return;
25. delete_unvalid_line_from_list(&pHead, pMiniTree);
26. if(NULL == pHead)
27. return;
29. sort_for_line_list(&pHead);
30. memmove(pDirLine, pHead, sizeof(DIR_LINE));
32. while(pHead){
33. prev = pHead;
34. pHead = pHead->next;
35. free(prev);
36. }
37. return;
38. }

e）添加节点函数，将尚不是最小生成树的点纳入到最小生成树当中去

view plaincopy to clipboardprint?

1. void insert_node_into_mini_tree(DIR_LINE* pLine, MINI_GENERATE_TREE* pMiniTree)
2. {
3. int index;
5. for(index = 0; index < pMiniTree->node_num; index ++){
6. if(pLine->start == pMiniTree->pNode[index]){
7. pMiniTree->pNode[pMiniTree->node_num++] = pLine->end;
8. return;
9. }
10. }
12. pMiniTree->pNode[pMiniTree->node_num++] = pLine->start;
13. return;
14. }

（1）d、e是c中调用的子函数，如果大家观察一下就明白了

（2）最小生成树是按照自顶向下的顺序编写的，虽然c中的子函数完成了，但是d中还有两个子函数没有着落

（3）d中的函数delete_unvalid_line_from_list、sort_for_line_list会在下一篇中继续介绍

（4）算法只要能够按照手工计算的流程编写出来，基本上问题不大，但是一些细节还是要小心注意的

【待续】