mstscr.cpp

运筹学最小支撑树的求解方法。该程序共有两种计算方法

		//重新初始化集合C中所有元素的最小值。
		index=0; 
		do{
			( (CStruct_C *)Set_C_Array.GetAt( index ++ ) )->SetMin();	
		}while( index != Set_C_Array.GetSize() ); 
		
		//对于网络中的每一条边，匹配集合C中的元素。
		for(icount=0; icount < pointCoupleArray.GetSize(); icount++)
		{	//ptrCouple—取得的当前边(点对)的指针
			CPointCouple * ptrCouple = (CPointCouple *)pointCoupleArray.GetAt(icount);
			int index1=-1,index2=-1;	//对于取出的点对的一个点位于集合C中的元素的索引。
			//ptrSet_C_Locate—取得的集合C的当前元素指针。
			for(jcount=0; jcount<Set_C_Array.GetSize(); jcount++)
			{
				CStruct_C * ptrSet_C_Locate=(CStruct_C *)Set_C_Array.GetAt(jcount);
				for(index=0; index < ptrSet_C_Locate->PotArray.GetSize(); index++ )
				{
					if( ptrSet_C_Locate->PotArray.GetAt(index) == ptrCouple->indexpoint1 ) index1 = jcount;
					if( ptrSet_C_Locate->PotArray.GetAt(index) == ptrCouple->indexpoint2 ) index2 = jcount;
				}
				if( index1 == index2 && index1 != -1 && index2 != -1) break;
			}
			ASSERT( index1 != -1 || index2 != -1 );  //必然会在其中找到。
			if( index1 != index2 )//找到了分属于不同的点集合。
			{
				int D_uv = ptrCouple->value;
				int & MinPot1 = ((CStruct_C *)Set_C_Array.GetAt(index1))->MinPot;
				if( D_uv < MinPot1 )
				{
					MinPot1=D_uv;
					//记录了该点对在点对集合中的位置
					((CStruct_C *)Set_C_Array.GetAt(index1))->Shortest = icount;
				}
				int & MinPot2 = ((CStruct_C *)Set_C_Array.GetAt(index2))->MinPot;
				if( D_uv < MinPot2 )
				{
					MinPot2 = D_uv;
					//记录了该点对在点对集合中的位置
					((CStruct_C *)Set_C_Array.GetAt(index2))->Shortest = icount;
				}
			}
		}
		//for all Sj属于C, do T:T并{shortest[j]};
		for(icount=0; icount<Set_C_Array.GetSize(); icount++)
		{
			CStruct_C * ptrSet_C_Locate=(CStruct_C *)Set_C_Array.GetAt(icount);
			ptrSet_C_Locate->AddShortest(pointCoupleArray);
		}
		//找出（V，T）的连通分图集合C
		icount=0;
		while(icount <Set_C_Array.GetSize())
		{
			CStruct_C * ptrSet_C_Locate=(CStruct_C *)Set_C_Array.GetAt(icount);
			if(ptrSet_C_Locate->UniteSort){
				jcount = icount+1;
				BOOL UnintOK = FALSE;
				while(jcount < Set_C_Array.GetSize() )
				{
					CStruct_C * ptrSet_C_tmp=(CStruct_C *)Set_C_Array.GetAt(jcount);
					if(ptrSet_C_tmp->UniteSort)
					{
						if( ptrSet_C_Locate->UniteSet( * ptrSet_C_tmp) )
						{
							Set_C_Array.RemoveAt(jcount);
							UnintOK = TRUE;
							break;
						}else jcount++;
					}else  jcount++;

				}
				if( !UnintOK ) icount++;
			}else icount++;
		}
		icount=0;
		while(icount <Set_C_Array.GetSize()){
			CStruct_C * ptrSet_C_Locate=(CStruct_C *)Set_C_Array.GetAt(icount);
			if(ptrSet_C_Locate->UniteSort){
				jcount=0;
				while(jcount<Set_C_Array.GetSize()){
					CStruct_C * ptrSet_C_tmp = (CStruct_C *)Set_C_Array.GetAt(jcount);
					if( !ptrSet_C_tmp->UniteSort ){
						if( ptrSet_C_tmp->UniteSet1(* ptrSet_C_Locate )){
							Set_C_Array.RemoveAt(icount);
							break;							
						}else jcount++;
					}else jcount++;
				}
				if(jcount == Set_C_Array.GetSize()) icount ++;
			}else icount++;
			
			if( icount == Set_C_Array.GetSize() )
			{
				BOOL find_Not_Unite=FALSE;
				for(index=0;index<Set_C_Array.GetSize();index++){
					if( ((CStruct_C *)Set_C_Array.GetAt(index))->UniteSort ){
						find_Not_Unite = TRUE;	icount = index;	 break;
					}
				}
			}
		}

		for(icount=0; icount < Set_C_Array.GetSize(); icount++ )
		{
			CStruct_C * ptrOK=(CStruct_C *)Set_C_Array.GetAt( icount );
			for(jcount=0; jcount<ptrOK->BorderArray.GetSize(); jcount++)
			{
				int isTreeIndex=ptrOK->BorderArray.GetAt(jcount);
				((CPointCouple *)pointCoupleArray.GetAt(isTreeIndex))->isTree=TRUE;
			}
		}

		for(icount=0; icount<pointCoupleArray.GetSize();icount++)
		{
			CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(icount);
			if(ptrCouple->isTree)
			{
				structPot * ptrCurPot;
				ptrCurPot=(structPot *)ptrView->PointArray.GetAt(ptrCouple->indexpoint1);
				for( jcount=0; jcount < ptrCurPot->neighborhood.GetSize(); jcount++)
				{
					border Border=ptrCurPot->neighborhood.GetAt(jcount);
					if( Border.index == ptrCouple->indexpoint2 )
					{
						Border.isTree=TRUE;
						ptrCurPot->neighborhood.SetAt(jcount,Border);
					}
				}
				ptrCurPot=(structPot *)ptrView->PointArray.GetAt(ptrCouple->indexpoint2);
				for( jcount=0; jcount < ptrCurPot->neighborhood.GetSize(); jcount++)
				{
					border Border=ptrCurPot->neighborhood.GetAt(jcount);
					if( Border.index == ptrCouple->indexpoint1 )
					{
						Border.isTree=TRUE;
						ptrCurPot->neighborhood.SetAt(jcount,Border);
					}
				}
			}
		}
		ptrView->Invalidate();
		Sleep(2000);
	}

	ptrView->MessageBox("显示完毕!","最小支撑树",MB_OK|MB_ICONINFORMATION);
	do{
		if(pointCoupleArray.GetSize())
		{
			CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(0);
			pointCoupleArray.RemoveAt(0);
			delete ptrCouple;
			ptrCouple=NULL;
		}else break;
	}while(1);

	do{
		if(Set_C_Array.GetSize())
		{
			CStruct_C * ptrPot=(CStruct_C *)Set_C_Array.GetAt(0);
			Set_C_Array.RemoveAt(0);
			delete ptrPot;
			ptrPot=NULL;
		}else break;
	}while(1);
	return 0;
}

UINT Step1_Proc( LPVOID pParam )
{
	CMSTScr * ptrView=(CMSTScr *)pParam;

	if( !ptrView->PointArray.GetSize() ) return 0; //网络图中没有顶点

	int icount=0,jcount=0,index=0;
	
	//构造点对集合pointCoupleArray，包含点对的两个点和权重
	CPtrArray pointCoupleArray;
	for(icount=0;icount<ptrView->PointArray.GetSize();icount++){
		structPot *ptrPot=(structPot *)ptrView->PointArray.GetAt(icount);
		if( ! ptrPot->neighborhood.GetSize() )
		{
			ptrView->MessageBox("网络中存在孤立点！","Input Error!",MB_OK|MB_ICONINFORMATION);
			do{
				if(pointCoupleArray.GetSize())
				{
					CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(0);
					pointCoupleArray.RemoveAt(0);
					delete ptrCouple;
					ptrCouple=NULL;
				}else break;
			}while(1);
			return 0;
		}
		for(jcount=0;jcount<ptrPot->neighborhood.GetSize();jcount++){
			//icount当前顶点的索引，
			//ptrPot->neighborhood.GetAt(jcount).index,从当前节点出发的边的另一个顶点的索引
			CPointCouple * ptrCouple=new CPointCouple(icount,
				ptrPot->neighborhood.GetAt(jcount).index,ptrPot->neighborhood.GetAt(jcount).value);
			for(index=0; index<pointCoupleArray.GetSize(); index++ )
				if( ( * ( (CPointCouple *)pointCoupleArray.GetAt(index) ) ) == ( * ptrCouple) )	break;
			if( index == pointCoupleArray.GetSize() )	pointCoupleArray.Add(ptrCouple);
			else delete ptrCouple;
		}
	}
	if( ! ptrView->PointArray.GetSize() ) return 0;//网络图中没有边
	ptrView->UndoTree();

	//构造集合U，包含最小支撑树的节点。初始化时只包含节点1
	CPtrArray Pot_Array;
	Pot * ptrPot=new Pot(0,-1);
	Pot_Array.Add(ptrPot);

	for(icount=1; icount<ptrView->PointArray.GetSize(); icount++)
	{
		ptrPot=new Pot(icount,0);
		Pot_Array.Add(ptrPot);
	}

	//程序主体。判断当U==V时，循环推出。
	do{
		int min=-1,minInVindex=-1,minIntreeindex=-1;
		index=0;//循环索引
		int numindex=0; //计数索引；
		do{
			if( ( (Pot *)Pot_Array.GetAt(index) )->NearDistance != -1 )//判断当前点是否属于V－U
			{
				//构造点对
				Pot * tmpPot=(Pot *)Pot_Array.GetAt(index);
				CPointCouple pointcouple(tmpPot->index,tmpPot->NearDistance,-1);
				//带入到点对集合pointCoupleArray中进行查找。
				//如果找到该点，则minIntreeindex参数返回该点在点对集合中的位置。
				int Intreeindex=0;
				int retValue=ptrView->ComparePointCouple(pointCoupleArray,pointcouple,Intreeindex);
				if( retValue != -1 )//网络中存在该点对
				{
					if(min == -1){	min = retValue;  minInVindex = index; minIntreeindex = Intreeindex; }
					else if( min > retValue && min != -1 )
					{  min = retValue;  minInVindex = index; minIntreeindex = Intreeindex; }
				}
			}
			else numindex++;
			index++;
		}while( index < Pot_Array.GetSize() );
		if( numindex == Pot_Array.GetSize() ) break;//表示所有的点都加入到了U集合。

		( (Pot *)Pot_Array.GetAt(minInVindex) )->NearDistance=-1;
		(*( (CPointCouple* )pointCoupleArray.GetAt(minIntreeindex))).isTree=TRUE;

		CPointCouple * ptrCouple=(CPointCouple* )pointCoupleArray.GetAt(minIntreeindex);
		structPot * ptrCurPot;
		ptrCurPot=(structPot *)ptrView->PointArray.GetAt(ptrCouple->indexpoint1);
		for( jcount=0; jcount < ptrCurPot->neighborhood.GetSize(); jcount++)
		{
			border Border=ptrCurPot->neighborhood.GetAt(jcount);
			if( Border.index == ptrCouple->indexpoint2 )
			{
				Border.isTree=TRUE;
				ptrCurPot->neighborhood.SetAt(jcount,Border);
			}
		}
		ptrCurPot=(structPot *)ptrView->PointArray.GetAt(ptrCouple->indexpoint2);
		for( jcount=0; jcount < ptrCurPot->neighborhood.GetSize(); jcount++)
		{
			border Border=ptrCurPot->neighborhood.GetAt(jcount);
			if( Border.index == ptrCouple->indexpoint1 )
			{
				Border.isTree=TRUE;
				ptrCurPot->neighborhood.SetAt(jcount,Border);
			}
		}

		ptrView->Invalidate();
		Sleep(2000);
		index=0;
		do{				//minInVindex
			if( ( (Pot *)Pot_Array.GetAt(index) )->NearDistance != -1 )//判断当前点是否属于V－U
			{
				int findindex1=0,findindex2=0;
				Pot * tmpPot=(Pot *)Pot_Array.GetAt(index);
				CPointCouple pointcouple1(tmpPot->index,tmpPot->NearDistance,-1);
				CPointCouple pointcouple2(tmpPot->index,minInVindex,-1);
				int retValue1=ptrView->ComparePointCouple(pointCoupleArray,pointcouple1,findindex1);
				int retValue2=ptrView->ComparePointCouple(pointCoupleArray,pointcouple2,findindex2);
				if( retValue2 != -1 )
					if( retValue1 ==-1 || retValue2 < retValue1 )
						tmpPot->NearDistance = minInVindex;
			}
			index++;
		}while( index < Pot_Array.GetSize() );
	}while(1);

	ptrView->MessageBox("显示完毕!","最小支撑树",MB_OK|MB_ICONINFORMATION);
	//结束释放内存。
	do{
		if(pointCoupleArray.GetSize())
		{
			CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(0);
			pointCoupleArray.RemoveAt(0);
			delete ptrCouple;
			ptrCouple=NULL;
		}else break;
	}while(1);

	do{
		if(Pot_Array.GetSize())
		{
			Pot * ptrPot=(Pot *)Pot_Array.GetAt(0);
			Pot_Array.RemoveAt(0);
			delete ptrPot;
			ptrPot=NULL;
		}else break;
	}while(1);
	return 0;
}

int CStruct_C::FindPot(int pot)
{
	int index=0;
	do{
		if(pot == PotArray.GetAt(index) )	return index;
		else index ++;
	}while( index != PotArray.GetSize() );
	return -1;
}

void CStruct_C::AddShortest(CPtrArray & ptrArray)
{
	CPointCouple * ptrCouple=(CPointCouple *)ptrArray.GetAt(Shortest);
	if( FindPot(ptrCouple->indexpoint1) == -1 )
		PotArray.Add(ptrCouple->indexpoint1);
	else PotArray.Add(ptrCouple->indexpoint2);
	BorderArray.Add(Shortest);
	Shortest=-1;
}

BOOL CStruct_C::UniteSet(CStruct_C & val)
{
	ASSERT(val.UniteSort && UniteSort);//val要求合并，首先val必须是可以合并的。
	//如果val可以合并，则valPotArray的最后一个顶点必为新加入的成员。
	//如果在该对象中找不到valPotArray的最后一个顶点，则不能合并。
	int ret=0;
	int icount=0;
	ret=FindPot( val.PotArray.GetAt( val.PotArray.GetSize()-1 ) );
	if( ret == -1 || ret == PotArray.GetSize() - 1 ) return FALSE; 
	ret=val.FindPot( PotArray.GetAt( PotArray.GetSize()-1 ) );
	if( ret == -1 || ret == val.PotArray.GetSize() - 1 ) return FALSE;

	int compare1=val.BorderArray.GetAt(val.BorderArray.GetSize()-1);
	int compare2=BorderArray.GetAt(BorderArray.GetSize()-1);
	ASSERT(compare1==compare2);
	UniteSort=FALSE;
	PotArray.RemoveAt( PotArray.GetSize()-1 );
	val.PotArray.RemoveAt( val.PotArray.GetSize()-1 );
	for(icount=0; icount < val.PotArray.GetSize(); icount++)
		PotArray.Add( val.PotArray.GetAt(icount) );
	for(icount=0; icount < val.BorderArray.GetSize()-1; icount++)
		BorderArray.Add( val.BorderArray.GetAt(icount) );
	return TRUE;
}

BOOL CStruct_C::UniteSet1(CStruct_C & val)
{
	ASSERT(val.UniteSort &&  ! UniteSort );//val要求合并，首先val必须是可以合并的。
	int icount=0;
	if( FindPot( val.PotArray.GetAt( val.PotArray.GetSize()-1 ) ) == -1 ) return FALSE; 
	UniteSort=FALSE;
	for(icount=0; icount < val.PotArray.GetSize()-1; icount++)
		PotArray.InsertAt(0,val.PotArray.GetAt(icount));
	for(icount=0; icount < val.BorderArray.GetSize(); icount++)
		BorderArray.InsertAt(0,val.BorderArray.GetAt(icount));
	return TRUE;
}