横型探索（幅優先探索）

/****************************/
/* 横型探索（幅優先探索）   */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

class Search
{
	void print(ArrayDeque <Character> q) {
		System.out.printf("   queue の状態： ");
		if (q.size() <= 0)
			System.out.printf("空です\n");
		else
			System.out.printf("先頭及び最後尾： %c %c，　要素数： %d\n", q.peekFirst(), q.peekLast(), q.size());
	}

	void width()
	{
		ArrayDeque <Character> q = new ArrayDeque <Character> ();

		System.out.printf("S の追加\n");
		q.add(new Character('S'));
		print(q);

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

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

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

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

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

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

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

		System.out.printf("先頭 G を削除\n");
		q.remove();
		print(q);
	}
}

public class Test
{
	public static void main (String[] args)
	{
		Search ss = new Search();
		ss.width();
	}
}

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

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

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

		System.out.printf("深さ： %d\n", d);
		for (i1 = 0; i1 < m; i1++)
			System.out.printf("%s ", node.substring(nd[i1], nd[i1]+1));
		System.out.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);
		}
	}
}

public class Test
{
	public static void main (String[] args)
	{
		int i1, i2, r[][] = new int [8][8], nd[] = new int [4];
		String node = "SABCDEFG";

		for (i1 = 0; i1 < 8; i1++) {
			for (i2 = 0; i2 < 8; i2++)
				r[i1][i2] = 0;
		}

		nd[0]   = 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;

		Search ss = new Search();
		ss.width(8, r, node, 1, 1, nd);
	}
}