例年だと解説していないんだけど、大学編入試験あたりで出題されている場合もあるし、 探索方法にこだわらなければ、難しい内容でもないので、グラフについて説明。

(0)--(1)--(3)--(4)--(5)--(7)
|              |    |
(2)------------(6)---+

上図のような、ノード間の接続状況を覚える場合、各ノードの接続を0/1で覚える 隣接行列がよく使われる。この例では、無向グラフだけれど、 ノードi番からｊ番につながっているものをa[i][j]=1で覚えれば、 有向グラフでも扱える。 実際のプログラミングでは、ノードを駅、路線を隣接行列で覚えるが、 隣接行列に、駅間の運賃を保存する場合も考えられる。(重み付きグラフ)

この隣接行列で、始点を与えた時のすべての経路を求めるプログラムは、 以下のようになる。

#include <stdio.h>
#define N 8
int a[N][N] = { // 隣接行列(無向グラフ)
{0,1,0,0,0,0,0,0} ,
{1,0,1,1,0,0,0,0} ,
{0,1,0,0,0,0,1,0} ,
{0,1,0,0,1,0,0,0} ,
{0,0,0,1,0,1,0,0} ,
{0,0,0,0,1,0,1,1} ,
{0,0,1,0,0,1,0,1} ,
{0,0,0,0,0,1,1,0}
} ;
// 訪問フラグ
int flag[N] = {0,0,0,0,0,0,0,0} ;
void visit( int i ) {
flag[i] = 1 ;
for( int j = 0 ; j < N ; j++ ) {
if ( a[i][j] == 1 && flag[j] == 0 ) {
printf( "%d->%d " , i , j ) ;
visit( j ) ;
}
}
}
int main() {
visit( 0 ) ;
return 0 ;
}

このプログラムでは、訪問可能な先が、未訪問であれば訪問する…という処理を、 再帰によって行っている。

メモリ節約のために2進数で…

このプログラムでは、隣接行列や訪問フラグには、0/1の論理値しか保存していないのに、 int型(32bit-CPUで4byte)を消費してもったいない。 論理値0/1の配列を、2進数のbit列で扱えば、メモリを節約できる。
# 節約目的というより、2進数の取り扱いは、情報処理試験や
# 大学の編入試験での出題もあるから…

各種試験を考えると、下の赤線部あたりが理解できる/書けるというのがキモ。

#define N 8
int a[N] = {
0x02 , // {0,1,0,0,0,0,0,0} → 0000,0010
0x0D , // {1,0,1,1,0,0,0,0} → 0000,1101
0x42 , // {0,1,0,0,0,0,1,0} → 0100,0010
0x12 , // {0,1,0,0,1,0,0,0} → 0001,0010
0x28 , // {0,0,0,1,0,1,0,0} → 0010,1000
0xD0 , // {0,0,0,0,1,0,1,1} → 1101,0000
0xA4 , // {0,0,1,0,0,1,0,1} → 1010,0100
0x60 , // {0,0,0,0,0,1,1,0} → 0110,0000
} ;
int flag = 0 ;
void visit( int i ) {
flag |= (1<<i) ;
for( int j = 0 ; j < N ; j++ ) {
if ( (a[i] & (1<<j)) && (flag & (1<<j))==0 ) {
printf( "%d->%d " , i , j ) ;
visit( j ) ;
}
}
}
int main() {
visit( 0 ) ;
return 0 ;
}

ちょうど、C++のテンプレートなどを使ったプログラミングを確認していたので、 STLを使って書いてみた。 配列宣言とか初期化以外の部分は、最初のプログラムと同じように書けるのが C++のテンプレート機能のおかげ。 bitsetは、論理値の配列を内部的にはbit演算で行ってくれるクラス。 vectorは、指定型で配列サイズが動的なもの。

#include <iostream>
#include <bitset>
#include <vector>
#define N 8
using namespace std;
vector< bitset<N> > a ;
bitset<N>           flag( 0x00 ) ;
void visit( int i ) { // 最初のプログラムとまるっきり同じ
flag[i] = 1 ;       // 内部的にはbitsetのおかげで2進数演算
for( int j = 0 ; j < N ; j++ ) {
if ( a[i][j] == 1 && flag[j] == 0 ) {
cout << i << "->" << j << " " ;
visit( j ) ;
}
}
}
int main() {
a.push_back( bitset<N>( 0x02 ) ) ;
a.push_back( bitset<N>( 0x0D ) ) ;
a.push_back( bitset<N>( 0x42 ) ) ;
a.push_back( bitset<N>( 0x12 ) ) ;
a.push_back( bitset<N>( 0x28 ) ) ;
a.push_back( bitset<N>( 0xD0 ) ) ;
a.push_back( bitset<N>( 0xA4 ) ) ;
a.push_back( bitset<N>( 0x60 ) ) ;
visit(0) ;
return 0 ;
}

プログラム末尾の配列a[]の初期化が、ちょっと美しくない。 C++では、配列は、無引数のデフォルトコンストラクタで初期化される。 しかし、引数付きで初期化したい時もあるんで、調べてみたら、 "placement new"なんて機能があるみたい。

vector< bitset<N> > a( 8 ) ;
int table[N] = {
0x02 , 0x0D , 0x42 , 0x12 , 0x28 , 0xD0 , 0xA4 , 0x60 ,
} ;
int main() {
for( int i = 0 ; i < N ; i++ )
new( &a[i] ) bitset<N>( table[i] ) ;
:
}

たしかに便利なコンストラクタの強制呼び出しなんだけど、 このコードだと、要素についてデフォルトコンストラクタと、 placement new のコンストラクタの2回が呼び出される。 placement new の実行前に、デストラクタって呼び出されるの？ なんか気持ち悪い…
# 試してみたけど、placement new の前にデストラクタが呼ばれることはないようだ…