图Graph--最小生成树

struct CloseEdge    //最短的边
{
    int startV;
    int endV;
    int minWeight;  //最小的权值
    bool operator < (const CloseEdge &s) const
    {//符号重载
        return minWeight < s.minWeight;
    }
};

//----------prim最小生成树---------------
void MiniSpanTree_Prim(char ch)
{
    int s = findPos(ch);
    if(s >= v)
        return;
    cout << "从 " << ch << " 开始的Prim最小生成树：" << endl;
    int i, j, k, x, w, minid, sum = 0;
    for(i = 0; i < v; ++i)
        visited[i] = 0;//访问标志置0
    visited[s] = 1;
    vector<int> q;
    vector<int>::iterator it;
    q.push_back(s);
    for(i = 0; i < v-1; ++i)
    {
        for(it = q.begin(),x = 0; it != q.end(); ++it,++x)
        {
            w = MaxValue;
            for(j = 0; j < v; ++j)
            {
                if (!visited[j] && ew[*it][j] < w)
                {
                    w = ew[*it][j];
                    minid = j;//记录较小的权的序号为k
                }
            }
            close_edge[x].minWeight = w;
            close_edge[x].startV = *it;
            close_edge[x].endV = minid;
        }
        sort(close_edge,close_edge+x);
        visited[close_edge[0].endV] = 1;
        cout << vertex[close_edge[0].startV] << "-" << vertex[close_edge[0].endV] << 
        	" 权值 " << close_edge[0].minWeight << endl;
        sum += close_edge[0].minWeight;
        q.push_back(close_edge[0].endV);
    }
    cout << "最小生成树权重总和为：" << sum << endl;
    }

int main()
{
//------------以下测试Prim最小生成树------------------
//    A -40- B -50- C
//  30|  \10 5|    20|
//    D -35- E -45- F
//  10|    55|    10|
//    I -15- G -25- H
//请输入以下数据生成上面的图
//A B C D E F G H I  A B 40 B C 50 A D 30 B E 5 C F 20 D E 35 E F 45 E G 55 F H 10 G H 25 A E 10 D I 10 I G 15
    arrGraph bg(9,13);    //9个顶点，13条边，默认生成无向图
    bg.creatGraph();
    bg.printArrOfGraph();
    bg.MiniSpanTree_Prim('A');
    bg.MiniSpanTree_Prim('I');//从任一点出发，最小花费都一样
    return 0;
}

void MiniSpanTree_Prim_O_n2(char ch)
{
    int s = findPos(ch);
    if (s >= v)
        return;
    cout << "从 " << ch << " 开始的Prim最小生成树：" << endl;
    int i, j, k, minweight, sum = 0;
    int adjvex[v];  //保存顶点下标
    int lowcost[v]; //保存相关顶点见的权值
    lowcost[s] = 0; //=0，加入了生成树
    adjvex[s] = s;  //起点下标为自己
    for(i = 0; i < v; ++i)
    {
        if(i == s)
            continue;
        lowcost[i] = ew[s][i];//将s起点与其他点的权值初始化
        adjvex[i] = s;//到达i的前一个点初始化为起点
    }
    for(i = 0; i < v-1; ++i)
    {
        minweight = MaxValue;
        for(j = 0, k = 0; j < v; ++j)
        {
            if(lowcost[j] != 0 && lowcost[j] < minweight)//未加入生成树的，且j点的比较小
            {
                minweight = lowcost[j];//更新最小值
                k = j;//下标记录入k
            }
        }
        cout << vertex[adjvex[k]] << "-" << vertex[k] << " 权值 " << ew[adjvex[k]][k] << endl;
        lowcost[k] = 0;//最小的权值点k加入生成树
        sum += ew[adjvex[k]][k];
        for(j = 0; j < v; ++j)
        {
            if(lowcost[j] != 0 && ew[k][j] < lowcost[j])//k加入生成树后，对k周围的权与最小权lowcost比较
            {
                lowcost[j] = ew[k][j];//更小的权更新lowcost数组
                adjvex[j] = k;//并记录j的前一位是k
            }
        }
    }
    cout << "最小生成树权重总和为：" << sum << endl;
}

//----------Kruskal最小生成树---------------
void MiniSpanTree_Kruskal()
{
    cout << "Kruskal最小生成树：" << endl;
    int i, j, k = 0, sum = 0;
    CloseEdge edges[MaxEdgeNum];    //边数据集
    for(i = 0; i < v; ++i)  //把边信息输入到edges数组
        for(j = 0; j < v; ++j)
            if(ew[i][j] != MaxValue && i > j)//无向图，i>j 矩阵中一半就可获取全部信息
            {
                edges[k].startV = i;
                edges[k].endV = j;
                edges[k].minWeight = ew[i][j];
                k++;
            }
    sort(edges,edges+k);//边排序
    int parent[e];             //作用，判断边与边是否形成回路
    int vf1, vf2;
    for(i = 0; i < k; ++i)
        parent[i] = 0;
    for(i = 0; i < k; ++i)
    {
        vf1 = Find(parent, edges[i].startV);
        vf2 = Find(parent, edges[i].endV);
        if(vf1 != vf2)//没有回路，可以选入生成树
        {
            parent[vf2] = vf1;
            cout << vertex[edges[i].startV] << "-" << vertex[edges[i].endV]
                << " 权重 " << edges[i].minWeight << endl;
            sum += edges[i].minWeight;
        }
    }
    cout << "最小生成树权重总和为：" << sum << endl;
}
int Find(int* parent, int v)
{
    int t = v;
    while(parent[t] > 0)
        t = parent[t];
    return t;
}