これまでは、Javaやc++を使って幅優先探索アルゴリズムを実装していましたが、今回はフロントエンドの最前線であるReact上で完結するような幅優先探索アルゴリズムを実装していきます。
目次
データ構造の実装
探索に必要なスタックとキューを実装します。
import
{React}
from "react";
class NodeT{
constructor(data,next){
this.data = data;
this.next = next;
}
getData(){
return this.data;
}
getNext(){
return this.next;
}
setNext(node){
this.next = node;
}
setData(data){
this.data = data;
}
}
class Queue{
constructor(){
this.head = null;
this.len = 0;
}
push(data){
if (this.len === 0){
this.head = new NodeT(data,null);
this.len ++;
}else{
var currNode = this.head;
while(currNode.getNext() !== null){
currNode = currNode.getNext();
}currNode.setNext(new NodeT(data,null));
this.len ++;
}
}
repr(){
var currNode = this.head;
var result = "->";
while(currNode !== null){
result += currNode.getData();
currNode = currNode.getNext();
}
return result;
}
pop(){
if (this.len === 0){
return null;
}
this.len -- ;
var currNode = this.head;
const tmp = currNode;
currNode = currNode.getNext();
this.head = currNode;
return tmp.getData();
}
size(){
return this.len;
}
peek(){
return this.head.getData();
}
isEmpty(){
if (this.len<=0){
return true;
}
return false;
}
}
class Stack{
constructor(){
this.head = null;
this.len = 0;
}
repr(){
var currNode = this.head;
var result = "->";
while(currNode !== null){
result += currNode.getData();
currNode = currNode.getNext();
}
return result;
}
push(data){
if (this.len === 0){
this.head = new NodeT(data,null);
this.len ++;
}else{
var currNode = this.head;
while(currNode.getNext() !== null){
currNode = currNode.getNext();
}currNode.setNext(new NodeT(data,null));
this.len ++;
}
}
pop(){
var currNode = this.head;
if (currNode == null){
return null;
}
if(currNode.getNext() == null){
this.len--;
return currNode.getData();
}
if(currNode.getNext().getNext() == null){
this.len--;
const returnVal = currNode.getNext().getData();
currNode.setNext(null);
return returnVal;
}
while(currNode.getNext().getNext() != null){
currNode = currNode.getNext();
}
const resutnVal = currNode.getNext().getData();
currNode.setNext(null);
this.len--;
return resutnVal;
}
size(){
return this.len;
}
peek(){
if (this.len < 0){
return null;
}
var currNode = this.head;
while(currNode.getNext() != null){
currNode = currNode.getNext();
}
return currNode.getData();
}
isEmpty(){
if (this.len<=0){
return true;
}
return false;
}
}
function Test(){
var result1 = "";
var result2 = "";
const queue = new Queue();
const stack = new Stack();
for(let i = 0;i<7;i++){
queue.push(i);
stack.push(i);
}
var s = queue.repr();
var s2 = stack.repr();
while(!stack.isEmpty()){
result1 += "(peek:" +stack.peek() + ")";
result1 += stack.pop() + "->";
}
while(!queue.isEmpty()){
result2 += "(peek:" +queue.peek() + ")";
result2 += queue.pop() + "->";
}
const a = Math.floor( Math.random() * (10 + 1 - 3) ) + 3;
return <div>
<p>{s}</p>
<p>{result1}</p>
<br></br>
<p>{s2}</p>
<p>{result2}</p>
</div>
}
export default Test;
>>>
->2->3->4->5->6->7->8->9->10->11->
->0123456
(peek:6)6->(peek:5)5->(peek:4)4->(peek:3)3->(peek:2)2->(peek:1)1->(peek:0)0
->0123456
(peek:0)0->(peek:1)1->(peek:2)2->(peek:3)3->(peek:4)4->(peek:5)5->(peek:6)6探索空間の生成と探索
幅優先探索を利用して、ランダムな探索区間を生成します。
class Cell{
constructor(){
this.hasRight = false;
this.hasBottom = false;
this.isVisited = false;
}
setVisitedStatus(boolStatement){
this.isVisited = boolStatement;
}
setRightStatus(boolStatement){
this.hasRight = boolStatement;
}
setBottomStatus(boolStatement){
this.hasBottom = boolStatement;
}
getVisited(){
return this.isVisited;
}
getHasRight(){
return this.hasRight;
}
getHasBottom(){
return this.hasBottom;
}
}
class BFSfield{
constructor(r,c,startRow,endRow){
this.space2D = new Array(r);
for(let i = 0;i<r;i++){
var tmp = new Array(c);
for(let j = 0;j<r;j++){
tmp[j] = new Cell();
}
this.space2D[i] = tmp;
}
this.startRow = startRow;
this.endRow = endRow;
}
}
function generateField(r,c,startRow,endRow){
const mymaze = new BFSfield(r, c, startRow, endRow);
mymaze.space2D[startRow][0].setVisitedStatus(true);
const firstElement = [startRow,0]
const stack = new Stack();
stack.push(firstElement);
var top = stack.peek();
var x = firstElement[0];
var y = firstElement[1];
console.log("checkpoint0");
while(!stack.isEmpty()) {
console.log("checkpoint1");
x = top[0];
y = top[1];
var coordinates = new Array(
[x - 1, y ],
[x + 1, y ],
[x , y - 1],
[x , y + 1]
);
var valid_coordinates = new Array(Array(2),Array(2),Array(2),Array(2));
var valid_coordinate_index = 0;
for (let i = 0;i<coordinates.length;i++) {
var coord = coordinates[i];
var x_prime = coord[0];
var y_prime = coord[1];
// is a valid coordinate.
if (x_prime >= 0 && y_prime >= 0 && x_prime < r && y_prime < c) {
console.log("checkpoint2");
if(mymaze.space2D[x_prime][y_prime].getVisited() === true) {
// visited, does nothing
} else {
valid_coordinates[valid_coordinate_index] =[x_prime, y_prime];
valid_coordinate_index++;
console.log("checkpoint3");
}
} else {
console.log("checkpoint4");
// invalid coordinate does nothing
}
}
if (valid_coordinate_index === 0) {
// no valid neighbors
top = stack.pop();
console.log("checkpoint5");
} else {
console.log("checkpoint6");
var random_neighbor = valid_coordinates[Math.floor(Math.random() * valid_coordinate_index)];
mymaze.space2D[random_neighbor[0]][random_neighbor[1]].setVisitedStatus(true);
// TODO: write the break the wall code
var dx = random_neighbor[0]-x;
var dy = random_neighbor[1]-y;
if (dx == -1){
console.log("checkpoint7");
mymaze.space2D[x-1][y].setBottomStatus(false);
}else if(dx == 1){
mymaze.space2D[x][y].setBottomStatus(false);
console.log("checkpoint8");
}else if (dy == -1 ){
console.log("checkpoint9");
mymaze.space2D[x][y-1].setRightStatus(false);
}else if (dy == 1 ){
console.log("checkpoint10");
mymaze.space2D[x][y].setRightStatus(false);
}
stack.push(random_neighbor);
top = stack.peek();
console.log("checkpoint11");
}
}
return mymaze;
}
function soutSpace(showPath,field,endRow){
const m = field.space2D;
var marker = " ";
if (showPath){
marker = "*";
}
var result = "|";
for (let k =0;k<m[0].length;k++){
result += "---|";
}
for (let i = 0;i<m.length;i++){
if (i!=0){
result += "\n|";
}else{
result += "\n ";
}
for (let j = 0;j<m[0].length;j++){
if (m[i][j].getVisited()){
if (m[i][j].getHasRight()){
if (j == m[0].length-1 && i == endRow){
result += " " + marker + " ";
}else{
result += " " + marker + " |";
}
}else if(!m[i][j].getHasRight()) {
result += " " + marker + " ";
}
}else if(!m[i][j].getVisited()) {
result += " |";
}
}
result += "\n";
result += "|";
for (let k = 0;k<m[0].length;k++){
if (m[i][k].getHasBottom()){
result += "---|";
}else{
result += " |";
}
}
}
return result;
}
function BFS(startRow,endRow,field){
const queue = new Queue();
queue.push([startRow,0]);
var isSolved = false;
while(queue.size() > 0 && !isSolved){
var tmp = queue.pop();
field.space2D[tmp[0]][tmp[1]].setVisitedStatus(true);
if(field.space2D[0].length > tmp[1] +1){
if (!field.space2D[tmp[0]][tmp[1]+1].getVisited() && !field.space2D[tmp[0]][tmp[1]].getHasRight()){
if (tmp[0] === endRow && tmp[1]+1 === field.space2D[0].length-1){
field.space2D[tmp[0]][tmp[1]+1].setVisited(true);
}
queue.push([tmp[0],tmp[1]+1]);
}
}
if (tmp[1] -1 >=0){
if (!field.space2D[tmp[0]][tmp[1]-1].getVisited() && !field.space2D[tmp[0]][tmp[1]-1].getHasRight()){
if (tmp[0] == endRow && tmp[1]-1 == field.space2D[0].length-1){
field.space2D[tmp[0]][tmp[1]-1].setVisited(true);
}
queue.push([tmp[0], tmp[1]-1]);
}
}
if (field.space2D.length> tmp[0]+1){
if (!field.space2D[tmp[0]+1][tmp[1]].getVisited() && !field.space2D[tmp[0]][tmp[1]].getHasBottom()){
if (tmp[0]+1 == endRow && tmp[1] == field.space2D[0].length-1){
field.space2D[tmp[0]+1][tmp[1]].setVisited(true);
}
queue.push([tmp[0]+1, tmp[1]]);
}
}
if (tmp[0]-1>=0){
if (!field.space2D[tmp[0]-1][tmp[1]].getVisited() && !field.space2D[tmp[0]-1][tmp[1]].getHasBottom()){
if (tmp[0]-1 == endRow && tmp[1] == field.space2D[0].length-1){
field.space2D[tmp[0]-1][tmp[1]].setVisited(true);
}
queue.add([tmp[0]-1, tmp[1]]);
}
}
}
return field;
}
function BFsearch(){
var a = generateField(30,30,0,0);
var result = soutSpace(true,a,0);
var solved = BFS(0,0,a);
result = soutSpace(true,solved,0);
console.log(result)
;
return (<div style={{whiteSpace: 'normal'}}>{result}
</div>
)
}
export default BFsearch;
>>>
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |Reactだと改行がうまく入らないようなので、今度また考え直します。
