横型探索（幅優先探索）

/****************************/
/* 横型探索（幅優先探索）   */
/*      coded by Y.Suganuma */
/****************************/
#include <stdio.h>
#include <queue>
using namespace std;

void print(queue<char> &q) {
	printf("   queue の状態： ");
	if (q.empty())
		printf("空です\n");
	else
		printf("先頭及び最後尾： %c %c，　要素数： %d\n", q.front(), q.back(), q.size());
}

int main()
{
	queue<char> q;

	printf("S の追加\n");
	q.push('S');
	print(q);

	printf("先頭 S を削除し，A, B, C を追加\n");
	q.pop();
	q.push('A');
	q.push('B');
	q.push('C');
	print(q);

	printf("先頭 A を削除し，D, E を追加\n");
	q.pop();
	q.push('D');
	q.push('E');
	print(q);

	printf("先頭 B を削除\n");
	q.pop();
	print(q);

	printf("先頭 C を削除し，F, G を追加\n");
	q.pop();
	q.push('F');
	q.push('G');
	print(q);

	printf("先頭 D を削除\n");
	q.pop();
	print(q);

	printf("先頭 E を削除\n");
	q.pop();
	print(q);

	printf("先頭 F を削除\n");
	q.pop();
	print(q);

	printf("先頭 G を削除\n");
	q.pop();
	print(q);

	return 0;
}

----------------再帰関数の利用----------------

/*****************************************/
/* 横型探索（幅優先探索）                */
/*      n : ノードの数                   */
/*      r : ノードからノードへの接続状況 */
/*      node : ノードの名前              */
/*      d : 深さ                         */
/*      m : 深さdにあるノードの数        */
/*      nd : 深さdにあるノード           */
/*           coded by Y.Suganuma         */
/*****************************************/
#include <stdio.h>

void width(int n, int **r, char *node, int d, int m, int *nd)
{
	int i1, i2, k, m1, *nd1 = new int [n];

	printf("深さ： %d\n", d);
	for (i1 = 0; i1 < m; i1++)
		printf("%c ", node[nd[i1]]);
	printf("\n");

	if (d < 3) {
		m1 = 0;
		for (i1 = 0; i1 < m; i1++) {
			k = nd[i1];
			for (i2 = 0; i2 < n; i2++) {
				if (r[k][i2] > 0) {
					nd1[m1] = i2;
					m1++;
				}
			}
		}
		if (m1 > 0)
			width(n, r, node, d+1, m1, nd1);
	}

	delete [] nd1;
}

int main()
{
	int i1, i2, **r, *nd;
	char *node = "SABCDEFG";

	nd = new int [4];
	r  = new int * [8];
	for (i1 = 0; i1 < 8; i1++) {
		r[i1] = new int [8];
		for (i2 = 0; i2 < 8; i2++)
			r[i1][i2] = 0;
	}

	r[0][1] = 1;
	r[0][2] = 1;
	r[0][3] = 1;
	r[1][4] = 1;
	r[1][5] = 1;
	r[3][6] = 1;
	r[3][7] = 1;

	nd[0] = 0;
	width(8, r, node, 1, 1, nd);

	return 0;
}