男人去眼袋最快最有效:一步一步写算法(之prim算法 中)
来源:百度文库 编辑:偶看新闻 时间:2024/05/06 07:31:16
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
C)编写最小生成树,涉及创建、挑选和添加过程
view plaincopy to clipboardprint?
- MINI_GENERATE_TREE* get_mini_tree_from_graph(GRAPH* pGraph)
- {
- MINI_GENERATE_TREE* pMiniTree;
- DIR_LINE pDirLine;
- if(NULL == pGraph || NULL == pGraph->head)
- return NULL;
- pMiniTree = (MINI_GENERATE_TREE*)malloc(sizeof(MINI_GENERATE_TREE));
- assert(NULL != pMiniTree);
- memset(pMiniTree, 0, sizeof(MINI_GENERATE_TREE));
- pMiniTree->node_num = 1;
- pMiniTree->pNode = (int*)malloc(sizeof(int) * pGraph->count);
- memset(pMiniTree->pNode, 0, sizeof(int) * pGraph->count);
- pMiniTree->pNode[0] = pGraph->head->start;
- while(1){
- memset(&pDirLine, 0, sizeof(DIR_LINE));
- get_dir_line_from_graph(pGraph, pMiniTree, &pDirLine);
- if(pDirLine.start == 0)
- break;
- pMiniTree->line_num ++;
- insert_line_into_queue(&pMiniTree->pLine, pDirLine.start, pDirLine.end, pDirLine.weight);
- insert_node_into_mini_tree(&pDirLine, pMiniTree);
- }
- return pMiniTree;
- }
d) 构建挑选函数,选择最合适的边
view plaincopy to clipboardprint?
- void get_dir_line_from_graph(GRAPH* pGraph, MINI_GENERATE_TREE* pMiniTree, DIR_LINE* pDirLine)
- {
- DIR_LINE* pHead;
- DIR_LINE* prev;
- VECTEX* pVectex;
- LINE* pLine;
- int index;
- int start;
- pHead = NULL;
- for(index = 0; index < pMiniTree->node_num; index++){
- start = pMiniTree->pNode[index];
- pVectex = find_vectex_in_graph(pGraph->head, start);
- pLine = pVectex->neighbor;
- while(pLine){
- insert_line_into_queue(&pHead, start, pLine->end, pLine->weight);
- pLine = pLine->next;
- }
- }
- if(NULL == pHead)
- return;
- delete_unvalid_line_from_list(&pHead, pMiniTree);
- if(NULL == pHead)
- return;
- sort_for_line_list(&pHead);
- memmove(pDirLine, pHead, sizeof(DIR_LINE));
- while(pHead){
- prev = pHead;
- pHead = pHead->next;
- free(prev);
- }
- return;
- }
e)添加节点函数,将尚不是最小生成树的点纳入到最小生成树当中去
view plaincopy to clipboardprint?
- void insert_node_into_mini_tree(DIR_LINE* pLine, MINI_GENERATE_TREE* pMiniTree)
- {
- int index;
- for(index = 0; index < pMiniTree->node_num; index ++){
- if(pLine->start == pMiniTree->pNode[index]){
- pMiniTree->pNode[pMiniTree->node_num++] = pLine->end;
- return;
- }
- }
- pMiniTree->pNode[pMiniTree->node_num++] = pLine->start;
- return;
- }
注意事项:
(1)d、e是c中调用的子函数,如果大家观察一下就明白了
(2)最小生成树是按照自顶向下的顺序编写的,虽然c中的子函数完成了,但是d中还有两个子函数没有着落
(3)d中的函数delete_unvalid_line_from_list、sort_for_line_list会在下一篇中继续介绍
(4)算法只要能够按照手工计算的流程编写出来,基本上问题不大,但是一些细节还是要小心注意的
【待续】
prim算法求最小生成树
急急急!!!谁能告诉我怎么用prim算法求最小生成树
在接触数据结构的Prim算法,向大家请教一下什么是跳点可以吗?
matlab中prony算法
怎样才能把算法写好啊?
写者问题的算法
消隐算法中,z缓冲区算法和画家算法之间的区别是什么?谢谢
用C语言写一个排序算法。
帮忙 写个算法 用C++语言
遗传算法的编程 (有算法步骤) 有重赏
求24点算法思路(非穷举算法)
路线问题(求算法)
关于microsoft project2003 中资源调配算法
RAS算法中 mod运算的具体步骤?
matlab中prony算法如何实现?
求:数据结构中树的遍历算法
RFC文档中IP加速算法是什么
“算法” 在编程中什么意思?
求助数学中“配式“的算法!
求助:在数学中“配方”的算法!
VB中这个MD5算法怎么用?
C语言中排序的算法是什么
不同电路中电功率的算法
在VB中如何实现这个算法