470
A <-> D 120
D <-> C 71
C <-> E 93
E <-> G 107
G <-> B 129
B <-> A 83
F <-> C 125
C <-> A 122
C <-> G 118
X <-> O 85
O <-> Y 80
Y <-> D 113
D <-> P 101
P <-> H 112
H <-> Q 80
Q <-> R 86
R <-> I 67
I <-> E 75
E <-> H 74
H <-> I 108
I <-> Q 133
Q <-> Z 68
Z <-> P 83
P <-> C 161
C <-> H 86
E <-> J 101
J <-> S 87
S <-> R 119
I <-> S 68
I <-> J 105
G <-> J 112
J <-> T 70
T <-> K 84
K <-> G 63
G <-> T 83
F <-> K 96
G <-> U 141
U <-> F 82
F <-> B 59
B <-> L 87
L <-> U 53
L <-> V 74
V <-> B 114
B <-> M 101
M <-> W 79
W <-> N 68
N <-> A 76
A <-> M 96
M <-> N 91
M <-> V 61
N <-> X 83
X <-> A 115
A <-> O 99
O <-> D 85
Y <-> P 90
P <-> Q 86
U <-> K 103
B <-> D 147
A <-> L 157
X <-> C 211
O <-> P 137
D <-> H 89
B <-> C 104
C <-> J 181
W <-> A 130
W <-> X 143
N <-> O 128
O <-> B 169
M <-> L 113
L <-> F 65
F <-> G 89
F <-> E 172
H <-> G 167
Q <-> E 142
H <-> R 108
S <-> E 125
E <-> T 140
Q <-> D 137
D <-> E 141
E <-> B 180
O <-> C 142
Y <-> H 177
N <-> B 145
V <-> D 252

// windowsDesign.cpp : 定义应用程序的入口点。
//

#include "stdafx.h"
#include "windowsDesign.h"
#include "class.h"
#include "function.h"
#include "globalVariable.h"
#include "dis_algo_graph.h"
#include "SS_algo_graph.h"
#include <string>
#include "MST_PRIM.h"
#include "MST_KRUSKAL.h"

#define MAX_LOADSTRING 100

// 全局变量:
HINSTANCE hInst;								// 当前实例
TCHAR szTitle[MAX_LOADSTRING];					// 标题栏文本
TCHAR szWindowClass[MAX_LOADSTRING];			// 主窗口类名

// 全局变量 我自己的
static int nowState = CommondState::emptyState ; 
static WindowSize winsize ;
static DataSet graphData;

// 此代码模块中包含的函数的前向声明:
ATOM				MyRegisterClass(HINSTANCE hInstance);
BOOL				InitInstance(HINSTANCE, int);
LRESULT CALLBACK	WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK	About(HWND, UINT, WPARAM, LPARAM);

int APIENTRY _tWinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPTSTR    lpCmdLine,
                     int       nCmdShow)
{
	UNREFERENCED_PARAMETER(hPrevInstance);
	UNREFERENCED_PARAMETER(lpCmdLine);

 	// TODO: 在此放置代码。
	MSG msg;
	HACCEL hAccelTable;

	// 初始化全局字符串
	LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
	LoadString(hInstance, IDC_WINDOWSDESIGN, szWindowClass, MAX_LOADSTRING);
	MyRegisterClass(hInstance);

	// 执行应用程序初始化:
	if (!InitInstance (hInstance, nCmdShow))
	{
		return FALSE;
	}

	hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_WINDOWSDESIGN));

	// 主消息循环:
	while (GetMessage(&msg, NULL, 0, 0))
	{
		if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
		{
			TranslateMessage( &msg );
			DispatchMessage( &msg );
		}
	}

	return (int) msg.wParam;
}




//  函数: MyRegisterClass()
//  目的: 注册窗口类。
//  注释:
//    仅当希望
//    此代码与添加到 Windows 95 中的“RegisterClassEx”
//    函数之前的 Win32 系统兼容时，才需要此函数及其用法。调用此函数十分重要，
//    这样应用程序就可以获得关联的
//    “格式正确的”小图标。

ATOM MyRegisterClass(HINSTANCE hInstance)
{
	WNDCLASSEX wcex;

	wcex.cbSize = sizeof(WNDCLASSEX);

	wcex.style			= CS_HREDRAW | CS_VREDRAW;
	wcex.lpfnWndProc	= WndProc;
	wcex.cbClsExtra		= 0;
	wcex.cbWndExtra		= 0;
	wcex.hInstance		= hInstance;
	wcex.hIcon			= LoadIcon(hInstance, MAKEINTRESOURCE(IDI_WINDOWSDESIGN));
	wcex.hCursor		= LoadCursor(NULL, IDC_ARROW);
	wcex.hbrBackground	= (HBRUSH)(COLOR_WINDOW+1);
	wcex.lpszMenuName	= MAKEINTRESOURCE(IDC_WINDOWSDESIGN);
	wcex.lpszClassName	= szWindowClass;
	wcex.hIconSm		= LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

	return RegisterClassEx(&wcex);
}

//
//   函数: InitInstance(HINSTANCE, int)
//
//   目的: 保存实例句柄并创建主窗口
//
//   注释:
//
//        在此函数中，我们在全局变量中保存实例句柄并
//        创建和显示主程序窗口。
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   HWND hWnd;

   hInst = hInstance; // 将实例句柄存储在全局变量中
   

   hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

   if (!hWnd)
   {
      return FALSE;
   }




   long style = GetWindowLong(hWnd,GWL_STYLE);//获得窗口风格

   winsize.screenX = GetSystemMetrics(SM_CXSCREEN);//获取整个屏幕右下角X坐标
   winsize.screenY = GetSystemMetrics(SM_CYSCREEN)-40;//屏幕Y坐标
   
  
   SetWindowPos(hWnd, NULL,0,0,winsize.screenX,winsize.screenY,SWP_NOZORDER);//改变窗口位置、尺寸和Z序


   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

//
//  函数: WndProc(HWND, UINT, WPARAM, LPARAM)
//
//  目的: 处理主窗口的消息。
//
//  WM_COMMAND	- 处理应用程序菜单
//  WM_PAINT	- 绘制主窗口
//  WM_DESTROY	- 发送退出消息并返回

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	static Point * myPoint = new Point();
	static TCHAR greet[] = TEXT("A");
	static Line * myline = new Line();
	static Point start,end;
	static list<Line> result;
	static list<Line> result_kruskal;
	



	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;

	switch (message)
	{
	case WM_COMMAND:
		wmId    = LOWORD(wParam);
		wmEvent = HIWORD(wParam);
		// 分析菜单选择:
		switch ( wmId )
		{
		case IDM_GRAPH_CLEAR:
			{			
				clearWindow( hWnd,winsize );
				graphData.lineList.clear();
				graphData.pointList.clear();
			}
			break;
		case IDM_MST_PRIM:
			{
				//1.得到所有边
				//2.显示所有边
				if(! result_kruskal.empty())
				{
					for( list<Line>::iterator it = result_kruskal.begin(); it != result_kruskal.end(); it++ )
					{
						it -> penColor = green ;
						drawLine( hWnd,*it ) ;
					}
					result_kruskal.clear();
				}
				result_kruskal = mstPrim( graphData, graphData.pointList.front() );
				if( ! result_kruskal.empty() )
				{
					for( list<Line>::iterator it = result_kruskal.begin(); it != result_kruskal.end(); it++ )
					{
						it -> penColor = red ;
						drawLine( hWnd,*it ) ;
						Sleep(1000);
					}
				}

			}
			break;

		case IDM_MST_KEUSKAL:
			{
				////1.得到所有边
				////2.显示所有边
				if(! result_kruskal.empty())
				{
					for( list<Line>::iterator it = result_kruskal.begin(); it != result_kruskal.end(); it++ )
					{
						it -> penColor = green ;
						drawLine( hWnd,*it ) ;
					}
					result_kruskal.clear();
				}
				result_kruskal = mstKruskal( graphData );
				if( ! result_kruskal.empty() )
				{
					for( list<Line>::iterator it = result_kruskal.begin(); it != result_kruskal.end(); it++ )
					{
						it -> penColor = red ;
						drawLine( hWnd,*it ) ;
						Sleep(1000);
					}
				}
			}
			break;

		case IDM_SET_SEARCH:
			{
				int* ssdata = http://www.mamicode.com/setSsearchAlgorithm( graphData );>
class.h

#ifndef class_h
#define class_h



#include <list>
#include <iostream>
using namespace std;

#define green RGB(50,205,50)
#define red RGB(255,0,0)
#define blue RGB(0,0,255)
#define white RGB(255,255,255)


#define al_red 1
#define al_white 2
#define al_black 3


class WindowSize
{
public:
	int screenX ;
	int screenY ;
	WindowSize()
	{
		screenX = screenY = 0;
	}

};





class Point
{
public:
	int x;
	int y;
	int r;
	char key;
	COLORREF brushColor;


	

	Point( )
	{
		x = 0;
		y = 0;
		r = 10;
		key = '*';
		brushColor =  green;
	}

	Point(const int & x,const int & y,const char &key )
	{
		this->x = x;
		this->y = y;
		r = 10;
		this->key = key ;
		brushColor =   green;

	}

	Point(const int &x,const int & y)
	{
		this->x = x;
		this->y = y;
		r = 10;
		this->key = '*' ;
		brushColor =   green;


	}

	Point(const Point & point)
	{
		this->x = point.x;
		this->y = point.y;
		r = 10;
		this->key = point.key;
		brushColor = point.brushColor;
	}

	bool legal(const WindowSize  &mywin)
	{
		bool result = true ;
		if(x <= 0 || x >= mywin.screenX || y <= 0 || y >= mywin.screenY)
		{
			result = false;
		}
		return result;
	}

};


class Line
{
public:
	Point start;
	Point end;
	int weight;
	bool down ;
	bool realLine;
	int penWidth;
	COLORREF penColor;
	Line()
	{
		realLine = false;
		penWidth = 2;
		penColor = green;
		down = false;
		weight = -1;
	}




};





class DataSet
{
public:
	list<Point>  pointList ;
	list<Line>  lineList ;
};


#endif

#ifndef ALGO_H
#define ALGO_H


#include <iostream>
#include <list>
#include "class.h"
#include <utility>
#include <queue>
#include "function.h"
#include <string>
#include <map>
using namespace std;

static int ** graph_data ;
static char startkey;

class Node 
{
public: 
	
	char key;



	Node( char key )
	{
		this -> key = key;
	}
	
	Node()
	{
		key = '*';
	}


};

bool operator< (const Node & a,const Node & b)
{
	return graph_data[startkey-'A'][a.key-'A'] > graph_data[startkey-'A'][b.key-'A'];
}
list<Line> findByMap( list<char> & road, list<Line>& linelist );


list<Line> singleDistance( list<Point> & pointlist,list<Line> & linelist,const Point & start,const Point & end)
{
	//disktra algorithm
	//1.利用邻接矩阵存储数据
	//2.利用优先队列：
	//	1)放入起点
	//	2)以此寻找终点

	int* color = new int[pointlist.size()];
	int* parent = new int[pointlist.size()];

	for(int i=0; i<pointlist.size(); i++)
	{
		color[i] = al_white;
		parent[i] = -1;
	}
	
	graph_data = http://www.mamicode.com/new int*[ pointlist.size() ];>
function.h

#ifndef function_h
#define function_h


#include<iostream>
#include<math.h>
#include<fstream>
#include<list>
#include "class.h"
#include<map>
using namespace std;



void drawLine(HWND hwnd,Line  myline)
{
	HPEN pen,oldpen;
	pen = CreatePen(PS_SOLID,myline.penWidth,myline.penColor);
	HDC hdc = GetDC(hwnd);
	oldpen = (HPEN)SelectObject(hdc,pen);
	if(myline.realLine == false)
		SetROP2(hdc,R2_NOTXORPEN);
	else 
		SetROP2(hdc,R2_COPYPEN);
	MoveToEx(hdc,myline.start.x,myline.start.y,NULL);
	LineTo(hdc,myline.end.x,myline.end.y);


	SelectObject(hdc,oldpen);
	DeleteObject(pen);
	ReleaseDC(hwnd,hdc);
}


void drawPoint(HWND hwnd,const Point & mypoint)
{

	HBRUSH brush ;
	HPEN hpen,oldpen;
	hpen = CreatePen(PS_SOLID,4,mypoint.brushColor);
	brush = CreateSolidBrush(mypoint.brushColor);
	HDC hdc = GetDC(hwnd);
	oldpen = (HPEN) SelectObject( hdc,hpen);
	SelectObject( hdc,brush );
	SetROP2( hdc,R2_COPYPEN );

	Ellipse( hdc,mypoint.x - mypoint.r , mypoint.y - mypoint.r , mypoint.x + mypoint.r , mypoint.y + mypoint.r );

	SelectObject(hdc,oldpen);
	DeleteObject(hpen);
	ReleaseDC(hwnd,hdc);
}


bool checkTwoPoint(const Point & a,const Point & b)
{
	bool result = false;
	int abx = abs(a.x - b.x);
	int aby = abs(a.y - b.y);

	if(abx*abx + aby*aby < a.r*a.r )
		result = true ;
	return result;
}


bool checkPointInList( Point &a, list<Point> mylist )
{
	bool result = false ;
	list<Point>::iterator it ;
	if(! mylist.empty())
		for( it = mylist.begin(); it != mylist.end(); it ++ )
		{
			if( checkTwoPoint(a,*it) == true )
			{
				result = true ;
				a = (*it) ;
				break ;
			}
		}
	return result;
}

int disTwoPoint(const Point & start,const Point & end)
{
	int x_w = abs(end.x - start.x);
	int y_w = abs(start.y - end.y);
	return (int)sqrt(float(x_w*x_w + y_w*y_w));
}


void drawGraph(HWND hWnd, DataSet & graphData)
{
	TCHAR greet[1] ;
	if(! graphData.pointList.empty())
	{
		for(list<Point>::iterator it = graphData.pointList.begin(); it != graphData.pointList.end(); it++)
		{
			greet[0] = (*it).key ;
			TextOut( GetDC(hWnd),(*it).x - 5,(*it).y - (*it).r*3,greet,1 ) ;
			drawPoint(hWnd,*it) ;
		}
	}


	if(! graphData.lineList.empty())
	{
		for(list<Line>::iterator it = graphData.lineList.begin(); it!=graphData.lineList.end(); it++)
		{
			drawLine(hWnd,*it);
		}
	}
}

void saveGraph( DataSet & graphData )
{
	//1.保存所有节点
	//2.保存所有边

	ofstream writer;
	writer.open("graph.txt");
	writer<<graphData.pointList.size()<<endl;
	for(list<Point>::iterator it = graphData.pointList.begin();it != graphData.pointList.end();it++)
	writer<<(*it).key<<" "<<(*it).x<<" "<<(*it).y<<endl;
	writer<<graphData.lineList.size()<<endl;
	for(list<Line>::iterator it = graphData.lineList.begin(); it != graphData.lineList.end(); it++)
	writer<<(*it).start.key<<" "<<(*it).end.key<<endl;
	writer.close();
}

void openGraph( DataSet & graphData )
{
	//1.读取所有节点
	//2.读取所有边

	ifstream reader;
	reader.open("graph.txt");
	map<char,Point> mymap;
	int i;
	Point point ;
	Line line ;
	for( reader>>i;i>0;i-- )
	{
		reader>>point.key;
		reader>>point.x;
		reader>>point.y;
		graphData.pointList.push_back( point );
		mymap.insert( make_pair( point.key,point ) );
	}

	for( reader>>i; i>0; i-- )
	{
		reader>>line.start.key ;
		line.start = ( mymap.find(line.start.key) )-> second ;
		reader>>line.end.key ;
		line.end = ( mymap.find(line.end.key) )-> second ;

		line.realLine = true ;
		line.weight = disTwoPoint( line.start,line.end ) ;
		graphData.lineList.push_back( line );

	}

	reader.close();
}

void clearWindow( HWND hwnd,const WindowSize & winsize )
{
	HBRUSH brush;
	brush = CreateSolidBrush( white );
	SelectObject( GetDC(hwnd),brush );
	Rectangle( GetDC(hwnd),0,0,winsize.screenX,winsize.screenY );
	DeleteObject( brush );
}

#endif

#ifndef globalVariable_h
#define globalVariable_h



#include <list>
#include "class.h"


class CommondState
{
public:
	static const int emptyState = 0;
	static const int insertNodeState = 1;
	static const int insertLineState = 2;
	static const int selectStartState = 3;
	static const int selectEndState = 4;

};









#endif

#ifndef mst_kruskal
#define mst_kruskal

#include "class.h"
#include "function.h"
#include <iostream>
#include <list>
using namespace std;


int * mark;

bool linecom (const Line & a,const Line & b)
{
	return a.weight < b.weight;
}


void kruskal_union(const int & a,const int & b,const int & n);

list<Line> mstKruskal( DataSet dataset )
{
	/*
	1.对所有边排序
	2.依次找出最小的边，在保证不成环的情况下并连接
	3.返回边集合
	*/

	// 1
	const int n = dataset.pointList.size();
	mark = new int[n];
	for(int i=0;i<n;i++)
	{
		mark[i] = i;
	}
	dataset.lineList.sort( linecom );

	// 2 
	list<Line> result;
	Line edge;
	while( ! dataset.lineList.empty() )
	{
		edge = dataset.lineList.front();
		dataset.lineList.pop_front();
		if( mark[ edge.start.key - 'A' ] != mark[ edge.end.key - 'A' ] )
		{
			result.push_back(edge);
			kruskal_union(mark[ edge.start.key - 'A' ],mark[ edge.end.key - 'A' ],n);
		}
	}

	// 3
	return result;
}

void kruskal_union( const int & a,const int & b,const int & n )
{
	int min_num = min(a,b);
	int max_num = max(a,b);
	for(int i=0;i<n;i++)
	{
		if( mark[i] == max_num )
			mark[i] = min_num;
	}
}














#endif

#ifndef MST_PRIM
#define MST_PRIM

#include <iostream>
#include <list>
#include "class.h"
#include <utility>
#include <queue>
#include "function.h"
#include <string>
#include <map>
using namespace std;


static int * mst_prior_queue_key;
static int ** mst_graph_data;
static int n;

class PriorNode
{
public:
	int data;
	PriorNode()
	{
		data = http://www.mamicode.com/MAXINT;>


并查集算法
SS_algo_graph.h

#ifndef SS_H
#define SS_E

#include <iostream>
#include <list>
#include "class.h"
using namespace std;

//0.并查集
//1.给每个节点设置标志颜色位
//2.检查每一条边，是否可以合并
//3.合并边中的两个点所在的集合
//4.返回图的颜色集合

void set_union(const int & a,const int & b,const int & n);

int * pointset;
int * setSsearchAlgorithm( DataSet & graph ) 
{
	const int n = graph.pointList.size();
	const int m = graph.lineList.size();
	pointset = new int[ n ];
	bool ** edgeset = new bool*[ m ];
	for ( int i=0;i<n;i++ )
		pointset[i] = i;	
	for( int i=0;i<m;i++ )
	{
		edgeset[i] = new bool[m];
		for (int j =0;j<m;j++)
		{
			edgeset[i][j] = true;
		}
	}

	for(list<Line>::iterator it = graph.lineList.begin();it != graph.lineList.end();it++)
	{
		if(edgeset[(*it).start.key-'A'][(*it).end.key-'A'] == true)
		{
			if(pointset[(*it).start.key-'A'] != pointset[(*it).end.key-'A'])
			{
				set_union(pointset[(*it).start.key-'A'] , pointset[(*it).end.key-'A'],n);
			}
			edgeset[(*it).start.key-'A'][(*it).end.key-'A'] = false;
		}		
	}

	return pointset;
}

void set_union(const int & a,const int & b,const int & n)
{
	int min_num = min(a,b);
	int max_num = max(a,b);
	for(int i=0;i<n;i++)
	{
		if( pointset[i] == max_num )
			pointset[i] = min_num;
	}
}

#endif