import scala.util.Random
class Graph(numNodes: Int) { private val adjacencyList: Array[List[Int]] = Array.fill(numNodes)(List()) private val random = new Random() def addEdge(u: Int, v: Int): Unit = { adjacencyList(u) ::= v adjacencyList(v) ::= u } def randomPathToCustomer(startNode: Int, customerNode: Int): List[Int] = { var current = startNode val visited = Array.fill(numNodes)(false) val path = scala.collection.mutable.ListBuffer[Int](startNode) while (current != customerNode) { visited(current) = true val neighbors = adjacencyList(current).filter(!visited(_)) if (neighbors.isEmpty) { // If there are no unvisited neighbors, backtrack to the previous node. if (path.size <= 1) { // If we're back at the start node with no path found, break the loop. return List() } path.remove(path.size - 1) current = path.last } else { // Randomly select the next neighbor. val nextNode = neighbors(random.nextInt(neighbors.length)) path += nextNode current = nextNode } } path.toList }
}
object Main { def main(args: Array[String]): Unit = { val graph = new Graph(6) graph.addEdge(0, 1) graph.addEdge(0, 2) graph.addEdge(1, 3) graph.addEdge(2, 4) graph.addEdge(3, 5) val startNode = 0 val customerNode = 5 val randomPath = graph.randomPathToCustomer(startNode, customerNode) if (randomPath.nonEmpty) { println(s"Random path from $startNode to customer $customerNode: ${randomPath.mkString(" -> ")}") } else { println(s"No path found from $startNode to customer $customerNode") } }
}