AI好きな人の備忘録

深さ優先探索（続き）ページでは実際のソースコードを書き、実行してもらったと思う。
実行結果が

4
5
3
2

となったはずなのでこのページでは、なぜこのような結果になったのかを解説していく。
深さ優先探索を行う上で必要な情報は以下の通り

	const Graph& m_Graph;
	std::vector<int> m_Visited;
	std::vector<int> m_Route;
	int m_iSource, m_iTarget;
	bool m_bFound;

実際に深さ優先探索を行うコードは以下の通り

	std::stack<const Edge*> stack;
	Edge Dummy(m_iSource, m_iSource);
	stack.push(&Dummy);
	while (!stack.empty())
	{
		const Edge* Next = stack.top();
		stack.pop();
		m_Route[Next->To()] = Next->From();
		m_Visited[Next->To()] = visited;
		if (Next->To() == m_iTarget)
			return true;
		Graph::ConstEdgeIterator ConstEdgeItr(m_Graph, Next->To());
		for (const Edge* pE = ConstEdgeItr.begin();
			!ConstEdgeItr.end();
			pE = ConstEdgeItr.next())
		{
			if (m_Visited[pE->To()] == unvisited)
				stack.push(pE);
		}
	}
	return false;

	std::stack<const Edge*> stack;
	Edge Dummy(m_iSource, m_iSource);
	stack.push(&Dummy);

ここでは

while(!stack.empty()) 

を true にするためだけにダミーエッジを作成し、スタックに格納している。

	while (!stack.empty())
	{
		const Edge* Next = stack.top();
		stack.pop();
		m_Route[Next->To()] = Next->From();
		m_Visited[Next->To()] = visited;
		if (Next->To() == m_iTarget)
			return true;
		Graph::ConstEdgeIterator ConstEdgeItr(m_Graph, Next->To());
		for (const Edge* pE = ConstEdgeItr.begin();
			!ConstEdgeItr.end();
			pE = ConstEdgeItr.next())
		{
			if (m_Visited[pE->To()] == unvisited)
				stack.push(pE);
		}
	}

ここではスタックに格納しているエッジを取り出しNextエッジへ格納し、m_Routeへ値を格納する。
m_Visitedの接続先ノードを訪問済みとして印を付ける。
ConstEdgeIteratorを用いてNext->To()ノードから伸びるエッジに繋がる接続先ノードに対し未訪問であればスタックへ格納し、訪問済みであれば無視する。
上記の処理を行ったあと、m_Routeやm_Visited、ConstEdgeIteratorは以下の図のようになる。