第8章第1节

第8章第1节

/*
首先按照边的权值进行从小到大排列，每次从剩余的边中选择权值较小且边的两个顶点不在同一个集合内的
边(就是不会产生回路的边),加到生成树之中，直到加入了n-1条边为止。
*/
#include "stdio.h"
struct edge
{
    int u;
    int v;
    int w;
};//为了方便排序，这里创建了一个结构体用来存储边的关系
struct edge e[10];//数组大小根据实际情况来设置，要比m最大值大1
int n,m;
int f[7] = {0},sum = 0,count = 0;//并查集需要用到的一些变量
//f数组大小更具实际情况来设置，要比n的最大值大1
void quicksort(int left,int right)
{
    int i,j;
    struct edge t;
    if(left > right)
    {
        return;
    }

    i = left;
    j = right;
    while(i != j)
    {
        //顺序很重要，要先从右边开始找
        while(e[j].w >= e[left].w && i < j)
        {
            j--;
        }
        //再从左边开始找
        while(e[i].w <= e[left].w && i