最小生成树算法代码,C/C++代码库,德仔网

代码语言
代码分类
【C/C++】最小生成树算法
作者:文华 / 发布于2016/6/12/ 720
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
 
#define ll __int64
const int MAX = 2000000, INF = 0x7FFFFFFF;
int r[MAX], l[MAX], index[MAX], w[MAX], fa[2020];
 
int cmp(const int i, const int j)
{
    return w[i] < w[j];
}
 
int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
 
int main()
{
    // freopen("in.txt","r",stdin);
     
    int t, i, j;
    char a[2000][7];
 
    while (~scanf("%d", &t) && t)
    {
        int cout = 0;
 
        for (i = 0; i < t; i++)
            scanf("%s", a[i]);
 
        for (i = 0; i < t; i++)
            for (j = i + 1; j < t; j++)
            {
                int k, sum = 0;
 
                for (k = 0; k < 7; k++)
                    if (a[i][k] != a[j][k]) sum++;
 
                r[cout] = i;
                l[cout] = j;
                w[cout++] = sum;
            }
 
        int ans = 0;
 
        for (i = 0; i < t; i++) 
            fa[i] = i;
 
        for (i = 0; i < cout; i++)  
            index[i] = i;   //将边的序号按边长排序
 
        sort(index, index + cout, cmp);
 
        for (i = 0; i < cout; i++)
        {
            int num = index[i];
            int x = find(r[num]), y = find(l[num]);
 
            if (x != y) //如果不在同一分量就加上。同时并为同一分量
            {
                ans += w[num];
                fa[x] = y;
            }
        }
 
        printf("The highest possible quality is 1/%d.\n", ans);
    }
 
    return 0;
}



#include <stdio.h>
 
#define MAX_SIZE 2001     // 图的规模
#define INF      100
 
typedef struct {
    int edges[MAX_SIZE][MAX_SIZE];
     
    int n;   // 顶点数
    int e;   // 边数
} MGraph;    // 图的邻接矩阵类型
 
char str[MAX_SIZE][8]; 
MGraph g = { { 0 }, 0 };
 
int weight(int i, int j)  //返回两个字符串中不同字符的个数（返回边权）  
{  
    int w = 0;  
     
    int k;
    for(k = 0; k < 7; k++)  
        if(str[i][k] != str[j][k])  
            w++;  
 
    return w;  
}  
 
// Note: 如果不是MGraph* g，而是MGraph g，会造成Runtime Error。
int Prim(MGraph* g, int v0)  // v0：树中的第一个点
{
    int lowcost[MAX_SIZE], vset[MAX_SIZE];
    int i, j, k, min;
     
    int v = v0;
     
    for (i = 1; i <= (*g).n; i++)
    {
        lowcost[i] = (*g).edges[v0][i];
        vset[i] = 0;
    }
     
    vset[v0] = 1; // 将v0并入树中
    int sum = 0;  // sum：累计树的权值
     
    // 下面的循环用于选出候选边中最小者
    for (i = 1; i < (*g).n; i++)
    {
        min = INF; // INF：比所有边权值都大的常量
         
        for (j = 1; j <= (*g).n; j++)
        {
            if (vset[j] == 0 && lowcost[j] < min)
            {
                min = lowcost[j];
                k = j;
            }           
        }   
 
        vset[k] = 1;
        v = k;
        sum += min;
 
        // 下面的循环以刚并入的顶点v为媒介更新候选边
        for (j = 1; j <= (*g).n; j++)
        {
            if (vset[j] == 0 && (*g).edges[v][j] < lowcost[j])
                lowcost[j] = (*g).edges[v][j];
        }
    }   
     
    return sum;
}
 
 
int main(void)  
{  
    int i, j;  
    int n;
    // MGraph g = { { 0 }, 0 };
     
    scanf("%d", &n);
    while(n > 0)  
    {  
        for(i = 1; i <= n; i++)  
            scanf("%s", str[i]);
         
        g.n = n;
  
        for(i = 1; i <= n-1; i++)  
        {
            for(j = i + 1; j <= n; j++)  
            {
                g.edges[i][j] = g.edges[j][i] = weight(i, j);               
            }
        }
   
        printf("The highest possible quality is 1/%d.\n", Prim(&g, 1));
         
        scanf("%d", &n);  
    }  
         
    return 0;  
}
试试其它关键字
　生成树　
同语言下
可能有用的
文华贡献的其它代码(11)