#include?“Graph.h“
#include?
#include?
#include?
#include?
#include?“QtTraversal.h“
#include?“ITraversal.h“
#include?“IUpdateGraph.h“

Graph::Graph（）?{
	init（）;
	initGrah（）;
	_traversalThread?=?new?QtTraversal（this）;
}

Graph::~Graph（）?{
}

void?Graph::setCallback（IUpdateGraph*?update）?{
	_update?=?update;
}

void?Graph::drawGraph（QPainter*?painter）?{
	//繪制邊
	drawEdge（painter）;
	//繪制頂點
	drawVertex（painter）;
}

void?Graph::ergodic（）?{
	_traversalThread->start（）;
}

void?Graph::startErgodic（）?{
#if?1
	bfs（）;
#else
	_graphVertex[0].setDrawBK（true）;
	_book[0]?=?true;
	dfs（_graphVertex[0]）;
#endif
}

void?Graph::init（）?{
	for?（int?i?=0;i		for?（int?j?=0;j			if?（i?==?j）{
				_vertex[i][j]?=?0;//自己到自己為0
			}?else?{
				_vertex[i][j]?=?-1;//-1代表無窮距離
			}
		}
	}

	for?（int?i?=?0;?i?		_book[i]?=?false;
	}
}

void?Graph::initGrah（）?{
	for?（int?i?=?0;?i?		_graphVertex[i].setID（i）;
	}
	_vertex[0][1]?=?1;
	_vertex[1][0]?=?1;

	_vertex[0][2]?=?1;
	_vertex[2][0]?=?1;

	_vertex[0][5]?=?1;
	_vertex[5][0]?=?1;

	_vertex[2][4]?=?1;
	_vertex[4][2]?=?1;

	_vertex[3][4]?=?1;
	_vertex[4][3]?=?1;
}

QPoint?Graph::getCirclePoint（QPoint?center?double?r?double?angle）?{
	QPoint?pt;
	pt.setX（center.x（）?+?r*cos（qDegreesToRadians（angle）））;
	pt.setY（center.y（）?+?r*sin（qDegreesToRadians（angle）））;
	return?pt;
}

void?Graph::drawVertex（QPainter*?painter）?{
	for?（int?i?=?0;?i?		double?a?=?i?*?360.0?/?VERTEX_NUM;
		QPoint?vertexPt?=?getCirclePoint（QPoint（200?200）?100?a）;
		_graphVertex[i].setCenter（vertexPt）;
		_graphVertex[i].drawVertex（painter）;
	}
}

void?Graph::drawEdge（QPainter*?p）?{
	QPen?penLine（QBrush（Qt::red）?2?Qt::SolidLine）;
	p->setPen（penLine）;

	for?（int?i?=?0;?i?		for?（int?j?=?0;?j?			if?（_vertex[i][j]?!=?0?&&?_vertex[i][j]?!=?-1）?{
				p->drawLine（_graphVertex[i].getCenter（）?_graphVertex[j].getCenter（））;
			}
		}
	}
}

void?Graph::dfs（GraphVertex?vertex）?{
	for?（int?i?=?0;?i?		if?（_vertex[i][vertex.getID（）]?==?1?&&?_book[i]?==?false）?{
			_book[i]?=?true;
			_graphVertex[i].setDrawBK（true）;
			_update->updateMap（）;
			QThread::msleep（1000）;
			dfs（_graphVertex[i]）;
		}
	}
}

void?Graph::bfs（）?{
	std::queue?queueVertex;

	queueVertex.push（_graphVertex[0]）;
	_graphVertex[0].setDrawBK（true）;
	_book[0]?=?true;
	_update->updateMap（）;
	QThread::msleep（1000）;

	while?（queueVertex.size（））?{

		GraphVertex?first?=?queueVertex.front（）;

		for?（int?i?=?0;?i?			if?（_vertex[i][first.getID（）]?==?1?&&?_book[i]?==?false）?{
				_book[i]?=?true;
				_graphVertex[i].setDrawBK（true）;
				_update->updateMap（）;
				QThread::msleep（1000）;
				queueVertex.push（_graphVertex[i]）;
			}
		}

		queueVertex.pop（）;
	}
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2020-01-14?00:11??GraphTraversal\
?????文件????????3018??2020-01-14?00:11??GraphTraversal\Graph.cpp
?????文件?????????850??2020-01-13?23:52??GraphTraversal\Graph.h
?????文件?????????827??2020-01-13?23:42??GraphTraversal\GraphTraversal.cpp
?????文件?????????527??2020-01-13?23:41??GraphTraversal\GraphTraversal.h
?????文件??????????74??2020-01-13?20:41??GraphTraversal\GraphTraversal.qrc
?????文件????????2119??2020-01-13?22:50??GraphTraversal\GraphTraversal.ui
?????文件????????5413??2020-01-13?22:43??GraphTraversal\GraphTraversal.vcxproj
?????文件????????2753??2020-01-13?22:43??GraphTraversal\GraphTraversal.vcxproj.filters
?????文件????????1020??2020-01-13?23:44??GraphTraversal\GraphVertex.cpp
?????文件?????????519??2020-01-13?23:08??GraphTraversal\GraphVertex.h
?????文件??????????94??2020-01-13?22:46??GraphTraversal\ITraversal.cpp
?????文件?????????137??2020-01-13?22:45??GraphTraversal\ITraversal.h
?????文件?????????104??2020-01-13?22:24??GraphTraversal\IUpdateGraph.cpp
?????文件?????????138??2020-01-13?22:23??GraphTraversal\IUpdateGraph.h
?????文件?????????231??2020-01-13?22:48??GraphTraversal\QtTraversal.cpp
?????文件?????????237??2020-01-13?22:48??GraphTraversal\QtTraversal.h
?????目錄???????????0??2020-01-14?00:15??GraphTraversal\Resources\
?????文件?????????187??2020-01-13?20:41??GraphTraversal\main.cpp
?????目錄???????????0??2020-01-13?20:41??GraphTraversal\x64\
?????目錄???????????0??2020-01-14?00:15??GraphTraversal\x64\Debug\
?????文件????????2267??2020-01-14?00:15??GraphTraversal\x64\Debug\GraphTraversal.Build.CppClean.log
?????文件???????????3??2020-01-14?00:15??GraphTraversal\x64\Debug\GraphTraversal.log
?????目錄???????????0??2020-01-14?00:15??GraphTraversal\x64\Debug\GraphTraversal.tlog\
?????目錄???????????0??2020-01-14?00:15??GraphTraversal\x64\Debug\moc\
?????目錄???????????0??2020-01-14?00:15??GraphTraversal\x64\Debug\rcc\
?????目錄???????????0??2020-01-14?00:15??GraphTraversal\x64\Debug\uic\