clsprim.~h

最小生成树的算法范例

class clsNode{
public:
    int x;
    int y;
};
class clsPrim{
public:
    vector<vector<int> > MiniSpanTree(vector<clsNode> &, vector<vector<int> > &, vector<vector<int> > &);
};
vector<vector<int> > clsPrim::MiniSpanTree(vector<clsNode> &vecGraphNode, vector<vector<int> > &vecGraphNodeIndex, vector<vector<int> > &vecGraphEdge){
    vector<vector<int> > vecTreeEdge;
    vector<int> vecTempLineTreeEdge;
    vector<int> vecU;
    vector<int> vecV_U;
    int i, j;
    int m, n;
    float lowcost;
    float templowcost;
    for(i = 0; i < 2500; i++){
        for(j = 0; j < 2500; j++){
            vecTempLineTreeEdge.push_back(0);
        }
        vecTreeEdge.push_back(vecTempLineTreeEdge);
        vecTempLineTreeEdge.clear();
    }
    vecU.push_back(0);
    for(i = 1; i < vecGraphNode.size(); i++){
        vecV_U.push_back(i);
    }
    int xa, xb, ya, yb;
    while(vecU.size() != vecGraphNode.size()){
        lowcost = 999999;
        m = 0;
        n = 0;
        for(i = 0; i < vecU.size(); i++){
            for(j = 0; j < vecV_U.size(); j++){
                if(vecGraphEdge[vecU[i]][vecV_U[j]]){
                    xa = vecGraphNode[vecU[i]].x;
                    xb = vecGraphNode[vecV_U[j]].x;
                    ya = vecGraphNode[vecU[i]].y;
                    yb = vecGraphNode[vecV_U[j]].y;
                    templowcost = vecGraphEdge[vecU[i]][vecV_U[j]];//sqrt(float((xa - xb)*(xa - xb) + (ya - yb) * (ya - yb)));//
                    if(lowcost > templowcost){
                        m = i;
                        n = j;
                        lowcost = templowcost;
                    }
                }
            }
        }
        vecTreeEdge[vecU[m]][vecV_U[n]] = 1;//lowcost;
        vecTreeEdge[vecV_U[n]][vecU[m]] = 1;//lowcost;
        vecU.push_back(vecV_U[n]);
        vecV_U.erase(&vecV_U[n]);
    }
    return vecTreeEdge;
}