2007/05/03, kameda[at]iit.tsukuba.ac.jp
Breadth first search

----- Graph 3a --------------------------------
int edge[N][N] = {
/* 0 1 2 3 4 5 6 7 */
  {0,1,0,0,1,0,0,0},	/* 0 */
  {1,0,0,0,0,0,1,0},	/* 1 */
  {0,0,0,1,0,0,1,0},	/* 2 */
  {0,0,1,0,0,0,0,1},	/* 3 */
  {1,0,0,0,0,1,0,0},	/* 4 */
  {0,0,0,0,1,0,1,0},	/* 5 */
  {0,1,1,0,0,1,0,1},	/* 6 */
  {0,0,0,1,0,0,1,0} 	/* 7 */
};

< An output example (with "from" node) >
 0: 0[-1] 
 1: 1[0] 4[0] 
 2: 6[1] 5[4] 
 3: 2[6] 7[6] 
 4: 3[2] 

----- Graph 3b --------------------------------
int edge[N][N] = {
/* 0 1 2 3 4 5 6 7 */
  {0,1,0,0,1,0,0,0},	/* 0 */
  {1,0,1,1,0,0,0,0},	/* 1 */
  {0,1,0,0,0,0,0,1},	/* 2 */
  {0,1,0,0,0,1,0,1},	/* 3 */
  {1,0,0,0,0,1,0,1},	/* 4 */
  {0,0,0,1,1,0,1,0},	/* 5 */
  {0,0,0,0,0,1,0,0},	/* 6 */
  {0,0,1,1,1,0,0,0} 	/* 7 */
};

< An output example (with "from" node) >
 0: 0[-1] 
 1: 1[0] 4[0] 
 2: 2[1] 3[1] 5[4] 7[4] 
 3: 6[5] 

----- Graph 3c --------------------------------
int edge[N][N] = {
/* 0 1 2 3 4 5 6 7 */
  {0,1,0,0,0,0,0,0},	/* 0 */
  {1,0,1,0,0,0,0,0},	/* 1 */
  {0,1,0,1,0,0,0,0},	/* 2 */
  {0,0,1,0,1,0,0,0},	/* 3 */
  {0,0,0,1,0,1,0,0},	/* 4 */
  {0,0,0,0,1,0,1,0},	/* 5 */
  {0,0,0,0,0,1,0,1},	/* 6 */
  {0,0,0,0,0,0,1,0} 	/* 7 */
};

< An output example (with "from" node) >
 0: 0[-1] 
 1: 1[0] 
 2: 2[1] 
 3: 3[2] 
 4: 4[3] 
 5: 5[4] 
 6: 6[5] 
 7: 7[6]