/*
 * BFS.kt
 * 
 * This is Dave Musicant's BFS.kt from Fall 2024,
 * which was ported by Dave from the BFS code at
 * https://www.programiz.com/dsa/graph-bfs.
 * 
 * Modified lightly by Tanya Amert for Spring 2025.
 * 
 * Illustrates an implementation of the BFS algorithm.
 */

class Graph(var vertices: Int) {

    // The graph is represented using adjacency lists
    val adj = MutableList(vertices, {mutableListOf<Int>()})

    // Add an edge to the graph
    fun addEdge(src: Int, dest: Int) {
        adj[src].add(dest)
    }

    // BFS algorithm: not quite a search for a specific location,
    // but more of an example of the traversal pattern
    fun BFS(start: Int) {

        // We'll keep track of visited and our queue of nodes
        val visited = MutableList(vertices, {false})
        val queue = ArrayDeque<Int>()

        // The starting node is both visited and added
        // to our queue
        visited[start] = true
        queue.addLast(start)

        // Loop until we run out of options (queue is empty)
        while (queue.isNotEmpty()) {
            // Remove the first node from the queue (it's already
            // been marked as visited)
            val s = queue.removeFirst()
            System.out.print("$s ")

            // Now go through its neighbors, adding each to the queue
            // if we haven't visited it already
            for (n in adj[s]) {
                if (!visited[n]) {
                    visited[n] = true
                    queue.addLast(n)
                }
            }
        }
    }
}

fun main() {
    val g = Graph(4)

    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)

    println("Following is Breadth First Traversal " + "(starting from vertex 2)")

    g.BFS(2)
}