GraphTraversal.zip

通过QT把图绘制出来，并且通过深度优先搜索和广度优先搜索分别实现对图中的每一个节点进行搜索。在搜索过程中使用一个线程进行搜索，提高搜索效率，提高用户体验

#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< VERTEX_NUM;i++）{
		for （int j =0;j< VERTEX_NUM;j++）{
			if （i == j）{
				_vertex[i][j] = 0;//自己到自己为0
			} else {
				_vertex[i][j] = -1;//-1代表无穷距离
			}
		}
	}

	for （int i = 0; i < VERTEX_NUM; i++） {
		_book[i] = false;
	}
}

void Graph::initGrah（） {
	for （int i = 0; i < VERTEX_NUM; 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 < VERTEX_NUM; 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 < VERTEX_NUM; i++） {
		for （int j = 0; j < VERTEX_NUM; 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 < VERTEX_NUM; 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 < VERTEX_NUM; 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\