1. 全探索

ここでは全探索のアルゴリズムを紹介する。

1.1. 深さ優先探索(DFS)

スタックを利用したDFSのコードを示す。このコードは1,2,3,4,5から3つの数字を選び出す。

stackによる実装例

#include <stack>
#include <vector>
#include <iostream>

int main()
{
	int N = 5, M = 3;

	std::stack<std::vector<int> > s;
	for(int n=1; n<=N; n++)//root nodeをすべてプッシュ
	{
		std::vector<int> tmp;
		tmp.push_back(n);
		s.push(tmp);
	}

	while(!s.empty())
	{
		std::vector<int> current = s.top(); s.pop();//現在の探索node
		if(current.size() == M)
		{
			for(const auto &x : current) std::cout << x << " ";
			std::cout << std::endl;
		}
		else if(current.size() < M)//子nodeをすべてプッシュ
		{
			for(int n=current.back()+1; n<=N; n++)
			{
				std::vector<int> tmp = current;
				tmp.push_back(n);
				s.push(tmp);
			}
		}
	}
	return 0;
}

1.2. 幅優先探索(BFS)

BFSは DFS のスタックをキューに置き換えれば実現できる。