DFS <- function(G, g, s) { # 深さ優先探索 (Depth First Search) # G 木…上三角の接続行列 # g 目標点 s 探索を開始する点 # OpenList stack LIFO (Last In First Out) OpenList.pointer <- 0 OpenList <- list() OpenList.push <- function(v){ # OpenListに要素を加える OpenList[[OpenList.pointer + 1]] <<- v OpenList.pointer <<- (OpenList.pointer + 1) } OpenList.pop <- function(){ # OpenListから、最後に加えた要素を取り除く if (OpenList.pointer == 0){ return(NULL) } else{ v <- OpenList[[OpenList.pointer]] OpenList[[OpenList.pointer]] <<- NULL OpenList.pointer <<- (OpenList.pointer - 1) return(v) } } OpenList.length <- function() { return(OpenList.pointer) } # スタック終わり # キュー queue FIFO (First In First Out) ClosedList <- list() ClosedList.len <- 0 ClosedList.enqueue <- function(v) { # ClosedListに要素を加える ClosedList[[ClosedList.len + 1]] <<- v ClosedList.len <<- ClosedList.len + 1 } ClosedList.dequeue <- function() { # ClosedListから最初に加えた要素を取り除く if (ClosedList.len == 0) { return(NULL) } v <- ClosedList[[1]] ClosedList <<- ClosedList[-1] ClosedList.len <<- ClosedList.len - 1 return(v) } ClosedList.length <- function() { return(length(ClosedList.len)) } dfs <- function(G, g, s) { OpenList.push(s) while (OpenList.length() > 0) { n <- OpenList.pop() # OpenListの先頭からnを取り除く ClosedList.enqueue(n) # nをClosedListに入れる print(sprintf("visit %d", n)) if (n == g) { # nが目標点なら print(sprintf("found %d", n)) return(TRUE) } else { for (i in ncol(G):1) { if (G[n, i] == 1 & !is.element(i, OpenList) & !is.element(i, ClosedList)) { OpenList.push(i) } } } # print(OpenList) ## print(ClosedList) } print("not found") return(FALSE) } res <- dfs(G, g, s) return(res) } ## G <- matrix(c(0,1,1,0,0,0,0,0,0, 0,0,0,1,1,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,1,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,1, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0), ncol=9, byrow=T) ## g <- floor(runif(1, 1, ncol(G)+1)) ## print("グラフの隣接行列") ## print(G) ## print("探索対象となる点") ## print(g) ## DFS(G, g, 1)