4.

 
 #-------------------------------BFS---------------------------
bfs <- function(graph, start){
    #' Implementation of Breadth-First-Search (BFS) using adjacency matrix.
    #' This returns nothing (yet), it is meant to be a template for whatever you want to do with it,
    #' e.g. finding the shortest path in a unweighted graph.
    #' This has a runtime of O(|V|^2) (|V| = number of Nodes), for a faster implementation see @see ../fast/BFS.java (using adjacency Lists)
    #' @param graph an adjacency-matrix-representation of the graph where (x,y) is TRUE if the the there is an edge between nodes x and y.
    #' @param start the node to start from.
    #' @return Array array containing the shortest distances from the given start node to each other node

  # A Queue to manage the nodes that have yet to be visited, intialized with the start node
  queue = c(start)
  # A boolean array indicating whether we have already visited a node
  visited = rep(FALSE, nrow(graph))
  # (The start node is already visited)
  visited[start] = TRUE
  # Keeping the distances (might not be necessary depending on your use case)
  distances = rep(Inf, nrow(graph))  # Technically no need to set initial values since every node is visted exactly once
  # (the distance to the start node is 0)
  distances[start] = 0
  # While there are nodes left to visit...
  while(length(queue) > 0) {
    cat("Visited nodes: ", visited, "\n")
    cat("Distances: ", distances, "\n")
    node = queue[1] # get...
    queue = queue[-1] # ...and remove next node
    cat("Removing node ", node, " from the queue...", "\n")
    # ...for all neighboring nodes that haven't been visited yet....
    for(i in seq_along(graph[node,])) {
      if(graph[node,i] && !visited[i]){
        # Do whatever you want to do with the node here.
        # Visit it, set the distance and add it to the queue
        visited[i] = TRUE
        distances[i] = distances[node] + 1
        queue = c(queue, i)
        cat("Visiting node ", i, ", setting its distance to ", distances[i], " and adding it to the queue", "\n")
      }
    }
  }
  cat("No more nodes in the queue. Distances: ", distances, "\n")
  return (distances)
}

#source("src/bfs/r/simple/BFS.R")

graph = matrix(c(
  FALSE, TRUE, TRUE, FALSE, FALSE, FALSE,
  FALSE, FALSE, FALSE, TRUE, TRUE, FALSE,
  FALSE, TRUE, FALSE, TRUE, FALSE, FALSE,
  FALSE, FALSE, FALSE, FALSE, TRUE, TRUE,
  FALSE, FALSE, FALSE, FALSE, FALSE, TRUE,
  FALSE, FALSE, FALSE, FALSE, FALSE, FALSE
), nrow=6, ncol=6, byrow=TRUE)

# Should be [0, 1, 1, 2, 2, 3]
print(bfs(graph, 1))

#-------------------------------DFS---------------------------




dfs <- function(start, target) {
  #' Implementation of DFS (depth-first search) algorithm to find the shortest path from a start to a target node..
  #' Given a start node, this returns the node in the tree below the start node with the target value (or null if it doesn't exist)
  #' Runs in O(n), where n is the number of nodes in the tree, or O(b^d), where b is the branching factor and d is the depth.
  #' @param start  the node to start the search from
  #' @param target the value to search for
  #' @return The node containing the target value or null if it doesn't exist.
  
  cat("Visiting Node ", start$value, "\n")
  if(start$value == target){
    # We have found the goal node we we're searching for
    print("Found the node we're looking for!")
    return (start)
  }

  # Recurse with all children
  for(i in seq_along(start$children)) {
    result = dfs(start$children[[i]], target)
    if (!is.null(result)) {
      # We've found the goal node while going down that child
      return (result)
    }
  }
  
  # We've gone through all children and not found the goal node
  cat("Went through all children of ", start$value, ", returning to it's parent.", "\n")
  return (NULL)
}







#source("src/dfs/r/simple/DFS.R")

# Smaller graph used for dfs
start = list(value=0, children=list(
  list(value=1, children=list(
    list(value=3, children=list()),
    list(value=4, children=list())
  )),
  list(value=2, children=list(
    list(value=5, children=list()),
    list(value=6, children=list())
  ))
))

# Bigger graph specifically for this algorithm
# TODO

# Should be 6
print(dfs(start, 6)$value)