AI好きな人の備忘録

深さ優先探索のページでツリー状に展開されたグラフに対し深さ優先探索を行うとどのような動きになるかを解説したので、次はゲームっぽいグラフに対し深さ優先探索を行う。
では深さ優先探索を行うために必要なソースコードを載せる。

DFS.h

#pragma once

#include <vector>
#include <list>
#include <stack>
#include "Graph.h"

class PathFindDFS
{
private:
	// ノードに対する印。左から「訪問済み」「未訪問」「親なし」
	enum{ visited, unvisited, no_parent_assigned };

public:
	// コンストラクタ
	PathFindDFS(const Graph& graph, int source, int target = -1);

	// getter & setter
	bool Found()const{ return m_bFound; }
	std::list<int> GetPathToTarget()const;

private:
	// 実際にDFSを行うメソッド
	bool Search();

private:
	// ノード情報とエッジ情報を包含するグラフ
	const Graph& m_Graph;
	// グラフが持つノードに対し「訪問済み」「未訪問」等の印を保持する配列
	std::vector<int> m_Visited;
	// 最終的な経路上にあるノードのインデックスを格納する
	std::vector<int> m_Route;
	// 探索を開始するノードのインデックスと目標となるノードのインデックス
	int m_iSource, m_iTarget;
	// ゴールノードへと繋がる経路が見つかれば true、見つからなければ false
	bool m_bFound;
};

DFS.cpp

#include "PathFindAlgorithms.h"
#include "Edge.h"
#include "Node.h"

// コンストラクタ
PathFindDFS::PathFindDFS(const Graph& graph, int source, int target)
: m_Graph(graph)
, m_iSource(source)
, m_iTarget(target)
, m_bFound(false)
, m_Visited(m_Graph.NumNodes(), unvisited)
, m_Route(m_Graph.NumNodes(), no_parent_assigned)
{
	m_bFound = Search();
}
std::list<int> PathFindDFS::GetPathToTarget()const
{
	std::list<int> path;
	if (!m_bFound || m_iTarget < 0)
		return path;
	int nd = m_iTarget;
	path.push_front(nd);
	while (nd != m_iSource)
	{
		nd = m_Route[nd];
		path.push_front(nd);
	}
	return path;
}
// 実際にDFSを行うメソッド
bool PathFindDFS::Search()
{
	// スタックを作成
	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());
		// Next->To()ノードから伸びるエッジに対し処理を行う
		for (const Edge* pE = ConstEdgeItr.begin();
			!ConstEdgeItr.end();
			pE = ConstEdgeItr.next())
		{
			// 接続先ノードが「未訪問」であればスタックへ格納する
			if (m_Visited[pE->To()] == unvisited)
				stack.push(pE);
		}
	}
	// 探索失敗
	return false;
}

以上が深さ優先探索を行うソースコードである。

作成するグラフは以下のとおり。

実際のソースコード

main.cpp

#include <iostream>
#include <conio.h>
#include "Node.h"
#include "Edge.h"
#include "Graph.h"
#include "DFS.h"

void main()
{
	Graph G = Graph(false);

	G.AddNode(Node(0));
	G.AddNode(Node(1));
	G.AddNode(Node(2));
	G.AddNode(Node(3));
	G.AddNode(Node(4));
	G.AddNode(Node(5));
	G.AddEdge(Edge(0, 1));
	G.AddEdge(Edge(0, 2));
	G.AddEdge(Edge(1, 4));
	G.AddEdge(Edge(2, 3));
	G.AddEdge(Edge(3, 4));
	G.AddEdge(Edge(3, 5));
	G.AddEdge(Edge(4, 5));

	PathFindDFS* DFS = new PathFindDFS(G, 4, 2);
	std::list<int> Path = DFS->GetPathToTarget();
	for (int index : Path)
		std::cout << index << std::endl;

	std::cout << "何かキーを入力してください" << std::endl;
	while (!_kbhit()){}
}

実行した結果が

4
5
3
2

となればOK

次は上記のコードに深さ優先探索を行った場合どのような動きをするか解説していく。