问题 B: 图的最小生成树-Kruskal算法

题目描述

Kruskal算法是最小生成树的经典算法，其步骤为：
E1：将所有的边按权值排序；
E2：设每个顶点为一个独立的点集，生成树T为空集；
E3：依序扫描每一条边，直到已输出n-1条边：
E31：若vi、vj不在同一点集中，则将该边加入生成树T中，并合并这两个点集；否则舍弃该边；
本题要求读入带权图，对其所有边按权值排序后输出。

输入格式

输入为邻接矩阵存储的图，第一行为正整数n（小于100），表示图中顶点个数
接下来是n行，每行为n个空格隔开的非负整数。0表示两个顶点之间没有直达边，非0表示有直达边。且该数字为对应直达边的权重。

输出格式

对所有边按权重排序后输出。如果图只有1个点（即没有边），则直接输出空行。

输入样例

7
0 10 9 13 0 0 0
10 0 0 15 7 0 12
9 0 0 4 0 3 0
13 15 4 0 0 22 23
0 7 0 0 0 0 20
0 0 3 22 0 0 32
0 12 0 23 20 32 0

输出样例  

<2,5>:3
<5,2>:3
<3,2>:4
<2,3>:4
<4,1>:7
<1,4>:7
<2,0>:9
<0,2>:9
<1,0>:10
<0,1>:10
<1,6>:12
<6,1>:12
<0,3>:13
<3,0>:13
<1,3>:15
<3,1>:15
<4,6>:20
<6,4>:20
<3,5>:22
<5,3>:22
<6,3>:23
<3,6>:23
<5,6>:32
<6,5>:32

数据范围与提示

注意题目的测试数据构造时用的排序算法如下：
for(int i=0;i    for(int j=i+1;j         if(a[j]

代码展示 

#include
#include
using namespace std;
 
struct side{
	int row;
	int col;
	int weight;
};
 
struct allSides{
	int num;
	side * sides;
};
 
bool operator <(const side &side1,const side &side2){
    return side1.weight
}
 
 
int main(){
    //freopen("/config/workspace/test/test","r",stdin);
    int n;
    cin>>n;
	allSides sss;
	sss.num=n*n;
	sss.sides=new side[n*n];
 
   int matrix[n][n];
    for(int i=0;i
        for(int j=0;j
			cin>>matrix[i][j];
    }
 
    if(n==1){
        cout<
        return 0;
    }
    
    int k=0;
    for(int i=0;i
        for(int j=0;j
            if(matrix[i][j]!=0){
                sss.sides[k].row=i;
                sss.sides[k].col=j;
                sss.sides[k].weight=matrix[i][j];
                k++;
            }
        }
    }
 
    //test
    // for(int i=0;i
    //     cout<<"<"<:"<
    // }
    // cout<<"***************************"<
 
 
    int loc[k];
    for(int i=0;i
        loc[i]=i;
    
    for(int i=0;i
        for(int j=i+1;j
            if(sss.sides[loc[j]].weight
                int temp=loc[j];
                loc[j]=loc[i];
                loc[i]=temp;
            }
        }
    }
 
    for(int i=0;i
        cout<<"<"<","<">:"<
    }
 
    return 0;
}
 

//闲叙题外话：最近...的...睡眠...堪忧啊...