一步一步写算法（之prim算法 上）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
前面我们讨论了图的创建、添加、删除和保存等问题。今天我们将继续讨论图的一些其他问题，比如说如何在图的环境下构建最小生成树。为什么要构建最小生成树呢？其实原理很简单。打个比方，现在某一个乡镇有n个村，那么这n个村肯定是联通的。现在我们打算在各个村之间搭建网线，实现村村通的工程。那么有什么办法可以实现村村互通，同时又使得最后的总距离最小呢？要达到这个目的，就必须在已有的图中构建最小生成树。
生成最小生成树的方法很多，prim方法就是其中的一种。那么生成最小生成树的基本步骤是什么呢？很简单，听我慢慢道来：
1）以某一个点开始，寻找当前该点可以访问的所有的边；
2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；
3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；
4）此时由所有边构成的树即为最小生成树。
那么，代码应该怎么编写呢？朋友们可以自己好好思考一下。
a）首先，我们定义基本的数据结构。
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 _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;
b）DIR_LINE的基本操作
view plaincopy to clipboardprint?STATUS insert_line_into_queue(DIR_LINE** ppLine, int start, int end, int weight)
{
DIR_LINE* pLine;
if(NULL == ppLine)
return FALSE;
if(NULL == *ppLine){
*ppLine = create_new_dir_line(start, end, weight);
return TRUE;
}
pLine = create_new_dir_line(start, end, weight);
pLine->next = *ppLine;
*ppLine = pLine;
return TRUE;
}
STATUS delete_line_from_queue(DIR_LINE** ppLine, DIR_LINE* pLine)
{
DIR_LINE* prev;
if(NULL == ppLine || NULL == *ppLine || NULL == pLine)
return FALSE;
if(pLine == *ppLine){
*ppLine = pLine->next;
goto final;
}
prev = *ppLine;
while(pLine != prev->next)
prev = prev->next;
prev->next = pLine->next;
final:
free(pLine);
return TRUE;
}
STATUS insert_line_into_queue(DIR_LINE** ppLine, int start, int end, int weight)
{
DIR_LINE* pLine;
if(NULL == ppLine)
return FALSE;
if(NULL == *ppLine){
*ppLine = create_new_dir_line(start, end, weight);
return TRUE;
}
pLine = create_new_dir_line(start, end, weight);
pLine->next = *ppLine;
*ppLine = pLine;
return TRUE;
}
STATUS delete_line_from_queue(DIR_LINE** ppLine, DIR_LINE* pLine)
{
DIR_LINE* prev;
if(NULL == ppLine || NULL == *ppLine || NULL == pLine)
return FALSE;
if(pLine == *ppLine){
*ppLine = pLine->next;
goto final;
}
prev = *ppLine;
while(pLine != prev->next)
prev = prev->next;
prev->next = pLine->next;
final:
free(pLine);
return TRUE;
}
补充：软件开发 , C语言 ,
