graph.cpp

我写的,画出最短路径,及最小生成树 Prim Dijistra算法+ GDI实现

// Graph.cpp: implementation of the CGraph class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "MapGuid.h"
#include "Graph.h"
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CGraph::CGraph()
{
	Head=new(Point);
	Head->Next=0;
	Latest=new(Point);
	PathValue=1000;
	StartIndex=0;
    Max=0;
	this->Orient=false;
}
void CGraph::ReDraw()
{
	Now=Head->Next;
	while(Now!=0)
	{
		Bridge=Now;
		Now=Now->Next;
		delete(Bridge);
	}
	Head->Next=0;
	Max=0;
}
CGraph::~CGraph()
{
   Now=Head;
	while(Now!=0)
	{
		Bridge=Now;
		Now=Now->Next;
		delete(Bridge);
	}

}
void CGraph::AddNew(int x,int y)
{
    	
    	Now=new(struct Point);
		Now->First=0;
        Now->x=x;
		Now->y=y;		
		Now->Index=Max++;
		if(Head->Next==0)
		{
		   Head->Next=Now;
		   Latest=Now;
		}
		else
		{
			Latest->Next=Now;
			Latest=Now;
		}
		Now->Next=0;
}
bool CGraph::SetPath(int & x1,int & y1,int & x2,int & y2)
{
	int Index1=-1,Index2=-1,i;
	for(i=0;i<2;i++)
	{
		Now=Head->Next;
	    while(Now!=0)
		{
			if(i==0)
			{
				if((Now->x-10)<x1&&x1<(Now->x+10)&&(Now->y-10)<y1&&y1<(Now->y+10))
				{
					Index1=Now->Index;
					x1=Now->x;//interfere the outside value
					y1=Now->y;
					break;
				}
				else
				{
					Now=Now->Next;
				}
			}
             if(i==1)
			{
				if((Now->x-10)<x2&&x2<(Now->x+10)&&(Now->y-10)<y2&&y2<(Now->y+10))
				{
					Index2=Now->Index;
					x2=Now->x;
					y2=Now->y;
					break;
				}
				else
				{
					Now=Now->Next;
					
				}
			}
		}
	}
	if(Index1!=-1&&Index2!=-1)
	{
         this->SetAdj(Index1,Index2);
		 return(true);
	}
	else
	{
		return(false);
	}

}
bool CGraph::StartToEnd(int &x1,int &y1,int &x2,int &y2)
{
   	int Index1=-1,Index2=-1,i;
	for(i=0;i<2;i++)
	{
		Now=Head->Next;
	    while(Now!=0)
		{
			if(i==0)
			{
				if((Now->x-10)<x1&&x1<(Now->x+10)&&(Now->y-10)<y1&&y1<(Now->y+10))
				{
					Index1=Now->Index;
					x1=Now->x;//interfere the outside value
					y1=Now->y;
					break;
				}
				else
				{
					Now=Now->Next;
				}
			}
             if(i==1)
			{
				if((Now->x-10)<x2&&x2<(Now->x+10)&&(Now->y-10)<y2&&y2<(Now->y+10))
				{
					Index2=Now->Index;
					x2=Now->x;
					y2=Now->y;
					break;
				}
				else
				{
					Now=Now->Next;
					
				}
			}
		}
	}
	if(Index1!=-1&&Index2!=-1)
	{
			if(Index1>Index2)
			{
		       this->StartIndex=Index2;
			   this->EndIndex=Index1;
			}
        	else
			{
               this->StartIndex=Index1;
			   this->EndIndex=Index2;
			}
			this->SearchPath();
			return(true);
	}
	else
	{
           return(false);
	}
   

}
void CGraph::SetAdj(int Index1,int Index2)
{
	Now=new(struct Point);
	SNow=new(struct Point);
	double weight;
	    Now=Head->Next;
		SNow=Head->Next;
        do
		{
				if(Now->Index==Index1)
				{
                   break;
				}
				Now=Now->Next;

		}while(Now!=0);
		do
		{
                if(SNow->Index==Index2)
				{
                   break;
				}
                SNow=SNow->Next;

		}while(SNow!=0);   
	 	weight=sqrt(pow((Now->x-SNow->x),2)+pow((Now->y-SNow->y),2));
		if(Now->First==0)
		{
			 Now->First=new(Point::Adj);
		     Now->First->Address=SNow;
             Now->First->Next=0;
			 Now->First->Weight=weight;
			 Now->First->Visited=false;
		}
		else
		{
			 Now->AjNow=new(Point::Adj);
			 Now->AjNow->Address=SNow;
			 Now->AjNow->Visited=false;
			 Now->AjNow->Weight=weight;
             Now->AjNow->Next=Now->First;
			 Now->First=Now->AjNow;
		}
		if(this->Orient==false)
		{
			  if(SNow->First==0)
			{
				 SNow->First=new(Point::Adj);
				 SNow->First->Address=Now;
				 SNow->First->Next=0;
				 SNow->First->Weight=weight;
				 SNow->First->Visited=false;
			}
			else
			{
				 SNow->AjNow=new(Point::Adj);
				 SNow->AjNow->Address=Now;
				 SNow->AjNow->Visited=false;
				 SNow->AjNow->Weight=weight;
				 SNow->AjNow->Next=SNow->First;
				 SNow->First=SNow->AjNow;
			}

		}
      
}
void CGraph::Prim()
{
    int i,j,k;
	Now=Head->Next;
	for(i=1;i<Max;++i)
	{
	
		Now->AjNow=Now->First;
		while(Now->AjNow!=0)
		{
			if(Now->AjNow->Address->Index!=i)
			{
				Now->AjNow=Now->AjNow->Next;
					LowCost[i]=100000.0;
			}     
			else
			{
					if(Now->AjNow->Address->Index==i)
					{
						LowCost[i]=Now->AjNow->Weight;
						
					}
					break;
			}
		
		}
			CloseVertex[i]=0;
	}
	LowCost[0]=0.0;
	CloseVertex[0]=1;
	 for(i=1;i<Max;++i)
	 {

		 Min=100000;
		 j=1,k=0;
		 while(j<Max)
		 {
			 if(LowCost[j]!=0&&LowCost[j]<Min)
			 {
                   Min=LowCost[j];
				   k=j;
			 }
			 j++;

		 }
		 LowCost[k]=0;
		 Now=Head->Next;
            while(Now->Index!=k)
			{
        	 Now=Now->Next;
			}		
		 for(j=1;j<Max;++j)
		 {
			 Now->AjNow=Now->First;
			 while(Now->AjNow!=0)
			 {
				 if(Now->AjNow->Address->Index!=j)
                   Now->AjNow=Now->AjNow->Next;
				 else
				 {
         
					if(LowCost[j]!=0&&(Now->AjNow->Weight<LowCost[j]))
					{
			        	 LowCost[j]=Now->AjNow->Weight;
			        	 CloseVertex[j]=k;
					} 
					break;
				 }	
			 }
			 
		 }
	 }
}
void CGraph::SearchPath()
{
    int v=0,w=0,i;
	Now=Head->Next;
	while(Now->Index!=StartIndex)
	{
		 Now=Now->Next;
	}
	for(v=0;v<Max;++v)
	{
		Final[v]=false;
		Now->AjNow=Now->First;
		while(Now->AjNow!=0)
		{
			if(Now->AjNow->Address->Index!=v)
			{
				Now->AjNow=Now->AjNow->Next;
			}     
			else
			{
					if(Now->AjNow->Address->Index==v)
					{
						D[v]=Now->AjNow->Weight;
						P[v]=StartIndex;
						
					}
					break;
			}
		}
		if(Now->AjNow==0)
		{
			D[v]=1000000;
			P[v]=-2;
		}
	
	}
	 P[StartIndex]=-1;
	 D[StartIndex]=0;
	 Final[StartIndex]=true;
	 for(i=0;i<Max;++i)
	 {
		 Min=10000;
		 for(w=0;w<Max;++w)
		 {
			 if(!Final[w])
				 if(D[w]<Min)
				 {
					 v=w;
					 Min=D[w];
				 }
		 }

		 	 Final[v]=true;
			 Now=Head->Next;
            while(Now->Index!=v)
			{
        	 Now=Now->Next;
			}		
		 for(w=0;w<Max;++w)
		 {
			 Now->AjNow=Now->First;
			 while(Now->AjNow!=0)
			 {
				 if(Now->AjNow->Address->Index!=w)
                   Now->AjNow=Now->AjNow->Next;
				 else
				 {
         
					if(!Final[w]&&((Min+Now->AjNow->Weight)<D[w]))
					{
			        	 D[w]=Min+Now->AjNow->Weight;
			        	 P[w]=v;
					} 
					break;
				 }	
			 }
			 
		 }
	 }
}