template<class EdgeType>
int AdjGraph<EdgeType>::CircleDFS()
{
int v=0,*Num,n=0;
resetMark();/*重置所有顶点的标记*/
stack<int> s;
s.push(v);
while(!s.empty())
{
v=s.top();
s.pop();
n++;
Mark[v]=1;
/*将与v节点邻接的所有未访问的节点入栈，并将标记设为1*/
for(Edge<EdgeType> e=firstEdge(v);isEdge(e);e=nextEdge(e))
{
if(Mark[e.end]==0)/*如果此边的end节点未被访问则入栈*/
{
Mark[e.end]=1;
s.push(e.end);
}
}
}
return n;
}
template<class EdgeType>
Edge<EdgeType> *AdjGraph<EdgeType>::BreakCircle()
{
int n,i,MSTNum=0;
Edge<EdgeType> *MST;
n=vertexNum;
MST=new Edge<EdgeType>[n];
Edge<EdgeType> e,temp;
MaxHeap<Edge<EdgeType>> heap(100);
for(i=0;i<vertexNum;i++)
{
for(e=firstEdge(i);isEdge(e);e=nextEdge(e))
{
if(e.start<e.end)
{
heap.insert(e);
}
}
}
while(heap.currentSize>0)
{
e=heap.removeMax();
temp=e;
matrix[e.start][e.end]=1000;
matrix[e.end][e.start]=1000;
if(n!=CircleDFS())//如果图不连通,恢复
{
matrix[e.start][e.end]=e.weight;
matrix[e.end][e.start]=e.weight;
MST[MSTNum++]=e;
}
}
return MST;
}