## poj2395Kruscal最小生成树

2019年04月18日 算法 ⁄ 共 2726字 ⁄ 字号 评论关闭

水题一道，关键是理解题目为最小生成树。纯粹为了复习并查集和Kruscal最小生成树。

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Edge
{
public:
int nId1,nId2;
int length;
};

{
public:
{
nodeID=-1;
length=-1;
nextNode=NULL;
}
int nodeID;
int length;
};

class Node
{
public:
Node()
{
nodeID=0;
parent=NULL;
rank=0;
}
int nodeID;
Node* parent;
int rank;
};

{
if(edge.nId1==nodeID)
{
}
else
{
}

{
return true;
}
else
{
{
}
{
return true;
}
else
{
{
return true;
}
}
}
return false;
}

class Graph
{
public:
vector<Node> nodeVec;
vector<Edge> edgeVec;
int iNodeNum;
int iEdgeNum;
bool InsertEdge(Edge edge);
};

bool Graph::InsertEdge(Edge edge)
{
{
edgeVec.push_back(edge);
return true;
}

return false;
}

bool SortEdge(Edge e1,Edge e2)
{
return e1.length<e2.length;
}

void MakeSet(Node& x)
{
x.parent=&x;
x.rank=0;
}

Node* FindSet(Node* node)
{
if(node->parent != node)
{
node->parent=FindSet(node->parent);
}
return node->parent;
}

{
if(pNode1->rank>pNode2->rank)
{
pNode2->parent=pNode1;
}
else if(pNode1->rank<pNode2->rank)
{
pNode1->parent=pNode2;
}
else
{
pNode1->parent=pNode2;
pNode2->rank++;
}
}

void UnionSets(Node* pNode1,Node* pNode2)
{
}

vector<Edge>* MinSpanTree_Kruscal(Graph graph)
{
vector<Edge> *mSpanTree=new vector<Edge>();
for(vector<Node>::iterator nodeIter=graph.nodeVec.begin();nodeIter!=graph.nodeVec.end();nodeIter++)
{
MakeSet(*nodeIter);
}

sort(graph.edgeVec.begin(),graph.edgeVec.end(),SortEdge);
int iUnionNumber=0;
for(vector<Edge>::iterator edgeIter=graph.edgeVec.begin();edgeIter!=graph.edgeVec.end();edgeIter++ )
{
if(FindSet( &graph.nodeVec[edgeIter->nId1-1] ) != FindSet(&graph.nodeVec[edgeIter->nId2-1]))
{
UnionSets(&graph.nodeVec[edgeIter->nId1-1],&graph.nodeVec[edgeIter->nId2-1]);
mSpanTree->push_back(*edgeIter);
}
}
return mSpanTree;
}

int main()
{
Graph graph;
int ai,bi,len;
int n,m;
cin>>n>>m;
graph.iNodeNum=n;
graph.iEdgeNum=m;

for(int i=0;i<n;i++)
{
graph.nodeVec.push_back(Node());
}

for(int i=0;i<m;i++)
{
cin>>ai>>bi>>len;
Edge edge;
edge.nId1=ai;
edge.nId2=bi;
edge.length=len;
graph.edgeVec.push_back(edge);
}

vector<Edge>mSpanTree=*MinSpanTree_Kruscal(graph);
cout<<mSpanTree[mSpanTree.size()-1].length<<endl;
return 0;

}```