树的应用

灰太狼 2022-12-16 06:39 97阅读 0赞

# 最小生成树 #

**生成树**连通图包含全部顶点的一个极小连通子图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]  
对于带权无向连通图G= (V，E)，G的所有生成树当中边的权值之和最小的生成树为G的最小生成树(MST).

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 2]

## 性质 ##

1）最小生成树不一定唯一，即最小生成树的树形不一定唯一。当带权无向连通图G的各边权值不等时或G只有结点数减1条边时，MST唯一。
     2）最小生成树的权值是唯一的，且是最小。
     3）最小生成树的边数为顶点数减1

IGENRIC_MST《G)[
    	T=NULL;
    	while T未形成一棵生戍树:
    		do 找到一条最小代价边(u，v)并且加入T后不会产生回路:
    		T=Tu(u, v);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 3]

void prim(G,T){
        
    	T=空集;
    	U= {
        w};
    	while ( (v-u)!=空集》{
        
    	设（u, v)是使ueU与ve(v-U),且权值最小的边;
    	T=Tu{
         (u, v)};
    	U = Uu{
        v};
    	}
    }

void MsT_Prim(Graph Gi
    int min_weight[G.vexnum];
    int adjvex[G.vexnum];
    for(int i=0 ; i<G.vexnum; i++)(
    min_weight[i]= G.Edge [o][i];
    adjvex[i] =0;
    int min_arc;
    int min_vex;
    for(inti=l; i<G.vexnum; i++){
        
    	min_arc = MAX;
    	for(int j=1; j<G.vexnum;j++)
    	if (min_weight[j]!=0&& min_weight[j]<min_arc)t
    		min_arc = min_weight[j;
    		min_vex = j:
    	min_ weight[min_vex]= 0;
    	for(int j=0; j<G.vexnum; j++){
        
    	if(min_weight[j]!=0&tG.Edge [min_arc][j]<min_weight[j1)(
    		min_weighttj] = G.Edge [min_arc][j];
    		adjvex[j]= min_arc;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 4]

void Kruskal (V，T){
        
    T=V;
    numS=n;
    while (nums>1){
        
    从E中取出权值最小的边(v, u);
    if(v和u属于T中不同的连通分量){
        
    T= Tu{
         (v, u)};
    numS--;

typedef struct Edge{
        
    int a, b;
    int weight;
    );
    void MsT_Kruskal(Graph G，Edge* edges, int* parent) [
    heap_sort(edges) ;
    Initial(parent);
    for(int i=0; i<G.arcnum; i++){
        
    int a_root=Find (parent, edges[i].a);
    int b_root=Find (parent, edges[i].b);
    if(a_root!=b_root)
    Union (parent, a_root, b_root);

链接: [哈夫曼树、编码应用][Link 1].

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/991bcaae1dab4a1fb8cd6392aedfba3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/7669e8843f634cd29f7cc26f9be6b78f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/3d659db039cb49b286444747950f17e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/eec77f34acfb40658acbc2b80ddb023b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/8ccd87ba8f7b44d490bc730ed0b79de1.png
[Link 1]: https://blog.csdn.net/sf9090/article/details/109154652/