BFS、重み付け図最短経路のc++実現

4878 ワード
algorithm
一、テストデータ
頂点数と辺数を入力してください:7 12入力辺:1条辺:1 2第2条辺:1 4第3条辺:2 4第3条辺:2 4第4条辺:2 5第5条辺:3 1 4第6条辺:3 6第7条辺:4 3 2第8条辺:4 5第9条辺:4 6 8第10条辺:4 7第11条辺:5 6第12条辺:7 6 6開始接点と終了接点:1 6 BFS:14 4 7 6第6 BFS経路:to 1 to 4 to 6 Dijkstra:142 3 5 7 6 Dijkstraパス:to 1 to 4 to 7 to 6 Press any key to continue
二、ソースコード
//BFS
#include 
#include 
#include 
#include 

using namespace std;

#define MAX_VERTEXS 100
#define INFINITY	10000 //     

class Graph
{
public:
	typedef struct _ArcNode //  
	{
		int key;
		int weight;
		_ArcNode* next;
		_ArcNode(int k, int w):next(NULL), key(k), weight(w){}; 
	}ArcNode, *pArcNode;

	typedef struct _Adj //   
	{
		int dist;
		bool IsKnow;
		pArcNode head;
		int path;
		_Adj():head(NULL), dist(INFINITY), IsKnow(false), path(0){};
	}Adj, AdjArray[MAX_VERTEXS+1];

	Graph(int vertex, int edge);
	void SetBeginEnd(int b);//      
	void InsertNode(int vVertex, int uVertex, int w); //    
	void BFS(); //        ;
	void Dijkstra(); //        ;
	void PrintPath(int nEnd);//    ;nEnd        

private:
	//       :    ，   ，  
	AdjArray	m_AdjArray;
	int			m_Vertex; //   
	int			m_Edge;   //  
	int			m_nBegin;
};

Graph::Graph(int vertex, int edge)
	: m_Vertex(vertex)
	, m_Edge(edge)
{
}

void Graph::SetBeginEnd(int b)
{
	m_nBegin = b;
}

void Graph::InsertNode(int vVertex, int uVertex, int w)
{
	pArcNode pNode = new ArcNode(uVertex, w);
	pNode->next = m_AdjArray[vVertex].head;
	m_AdjArray[vVertex].head = pNode;
}

void Graph::BFS()
{
	for (int i = 1; i <= m_Vertex; ++ i)
	{
		m_AdjArray[i].dist = INFINITY;
		m_AdjArray[i].path = 0;
	}
	queue q;
	q.push(m_nBegin);
	m_AdjArray[m_nBegin].dist = 0;
	pArcNode pNode;
	cout << m_nBegin << " ";
	while (!q.empty())
	{
		int nTmp = q.front();
		q.pop();
		for (pNode = m_AdjArray[nTmp].head; pNode != NULL; pNode = pNode->next)
		{
			if (m_AdjArray[pNode->key].dist == INFINITY)
			{
				m_AdjArray[pNode->key].dist = m_AdjArray[nTmp].dist + 1;
				cout << pNode->key << " ";
				m_AdjArray[pNode->key].path = nTmp;
				q.push(pNode->key);
			}
		}
	}
	cout << endl;
}

void Graph::Dijkstra()
{
	for (int i = 1; i <= m_Vertex; ++ i)
	{
		m_AdjArray[i].dist = INFINITY;
		m_AdjArray[i].path = 0;
	}
	m_AdjArray[m_nBegin].dist = 0;
	int nIsOver = m_Vertex;
	map mSort; //map
	map::iterator it;
	pArcNode pNode;
	while (nIsOver)
	{		
		// map           ,  map         
		for (i = 1; i <= m_Vertex; ++ i)
			if (!m_AdjArray[i].IsKnow)
				mSort.insert(make_pair(m_AdjArray[i].dist, i));
		it = mSort.begin();
		cout << it->second << " ";
		m_AdjArray[it->second].IsKnow = true;
		int nTmp = it->second;
		-- nIsOver;
		mSort.clear();
		
		for (pNode = m_AdjArray[nTmp].head; pNode != NULL; pNode = pNode->next)
			if (!m_AdjArray[pNode->key].IsKnow)
				if ((m_AdjArray[nTmp].dist + pNode->weight) < m_AdjArray[pNode->key].dist)
				{
					m_AdjArray[pNode->key].dist = m_AdjArray[nTmp].dist + pNode->weight;
					m_AdjArray[pNode->key].path = nTmp;				
				}
	}
	cout << endl;
}

void Graph::PrintPath(int nEnd)
{
	static int isEnd = nEnd;
	if (nEnd != 0)
	{
		PrintPath(m_AdjArray[nEnd].path);
		cout << " to ";
		cout << nEnd;
	}
	if (isEnd == nEnd)
		cout << endl;
}

int main()
{
	ifstream ifile("a.txt"); //      
	int vertex, edge;
	cout << "        :";
	ifile >> vertex >> edge; 
	cout << vertex << " " << edge << endl;
	Graph graph(vertex, edge);

	int vVertex, uVertex, w;
	cout << "    :" << endl;
	for (int i = 1; i <= edge; ++ i)
	{
		cout << " " << i << "  :";
		ifile >> vVertex >> uVertex >> w;
		cout << vVertex << " " << uVertex  << " " << w << endl;
		graph.InsertNode(vVertex, uVertex, w);
	}

	int nBegin, nEnd;
	cout << "            :";
	cin >> nBegin >> nEnd;
	graph.SetBeginEnd(nBegin);
	cout << "BFS:";
	graph.BFS();
	cout << "BFS  :";
	graph.PrintPath(nEnd);
	cout << "Dijkstra:";
	graph.Dijkstra();
	cout << "Dijkstra  :";
	graph.PrintPath(nEnd);
	return 0;
}

三、アルゴリズムの原理
BFS:初期条件は、出発ノードの距離を0とし、キューに挿入することである.ループ中にキューをポップアップし、1つのキーワードに対応する隣接テーブルを取得し、そのキーワードに対応する頂点の隣接頂点距離が無限でなければ(隣接テーブルに格納されている)、頂点の距離をキーワード頂点の距離に1を加え、距離をリセットした頂点をスタックに割り当てる.
Dijkstraアルゴリズム:初期条件は出発ノードの距離付与値が0であり、すべての頂点の最短距離がIsknowによって識別されFALSEに初期化されるかどうかを決定する.ループでは、距離がまだ決定されていない頂点の中で最も距離が小さい頂点を見つけ、既知(Isknow=TRUE)として識別し、その頂点に隣接するすべての頂点を巡り、距離(Isknow=FALSE)がまだ決定されていない頂点を巡り、新しい距離(pre.dist+weight)を古い距離(current.dist)と比較し、小さい場合は隣接する頂点の距離を更新する.
Opencvソース解析の(4):GaussianBlue()
ユーザーログイン操作