#include <cstdint>
#include<iostream>
#include<vector>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


struct Edge{
    int u;
    int v;
    int val;
    bool b;
    Edge(int u,int v,int val):u(u),v(v),val(val){
        b = 0;
    }
    bool operator==( const Edge& objstruct) const
{
return objstruct.val==val && objstruct.u==u && objstruct.v==v;
}


};


vector<Edge> mp; 
vector<int> s; //点集合
map<int,int> Length; //点集合



vector<Edge> findx(int x){
    vector<Edge> res;
    for(Edge edge:mp){
        if(edge.u == x || edge.v ==x)res.push_back(edge);
    }
    return res;
}

void findE(){
    vector<Edge> allEdgeg;
    Edge minEdge =  Edge(0,0,99999);
    for(int x:s){
        // 寻找与x顶点相接的边
        cout<<"与 "<<x<<" 相接的边:"<<endl;

        vector<Edge> temp = findx(x);
        for(Edge edge:temp){
            cout<<edge.u<<" "<<edge.v<<" "<<edge.val<<endl;
            if(edge.val <= minEdge.val){
                minEdge = edge; //最小的边
            }
        }
        cout<<"×××××××××××"<<endl;
    }

    // 把最小的边从mp中删除
    // 把顶点加入到s中
    // 计算 路径长度
    if(find(s.begin(),s.end(),minEdge.u)==s.end()){
        s.push_back(minEdge.u);
        Length[minEdge.u] = Length[minEdge.v]+minEdge.val;
    }    
    if(find(s.begin(),s.end(),minEdge.v)==s.end()){
        s.push_back(minEdge.v);
        Length[minEdge.v] = Length[minEdge.u]+minEdge.val;

    }
    cout<<"在mp中把删除!!"<<minEdge.u<<" "<<minEdge.v<<" "<<minEdge.val<<endl;
    mp.erase(find(mp.begin(),mp.end(),minEdge));
    //mp.erase()
    cout<<"找到一条最短的边:"<<minEdge.u<<" "<<minEdge.v<<" "<<minEdge.val<<endl;
    cout<<"S:";
    for(int x:s)cout<<x<<" ";
    cout<<endl;
    cout<<endl;
    cout<<endl;
    
}




int main(){
    mp.push_back(Edge(1,2,2));
    mp.push_back(Edge(1,3,3));
    mp.push_back(Edge(1,4,6));
    mp.push_back(Edge(3,4,2));
    mp.push_back(Edge(2,5,4));
    mp.push_back(Edge(2,6,6));
    mp.push_back(Edge(4,5,1));
    mp.push_back(Edge(4,6,3)); //边集合

    for(Edge temp:mp)cout<<"mp:"<<temp.u<<" "<<temp.v<<" "<<temp.val<<endl;
    int n = 6; // 总共的顶点
    s.push_back(1); // 把1加入原点
    while(s.size()<n){
        // 寻找所有与S集合点 相接的边
        findE();//2
    }
    cout<<Length[1]<<endl;
    cout<<Length[2]<<endl;
    cout<<Length[3]<<endl;
    cout<<Length[4]<<endl;
    cout<<Length[5]<<endl;
    cout<<Length[6]<<endl;
    return 0;
}
Last modification:October 25th, 2020 at 04:14 pm
如果觉得我的文章对你有用,请随意赞赏