// Path: src/main/java/io/github/marioluan/datastructures/graph/Graph.java
// public interface Graph {
// 
//     /**
//      * Adds an edge v-w.
//      *
//      * @param v vertex v
//      * @param w vertex w
//      */
//     void addEdge(int v, int w);
// 
//     /**
//      * Returns the vertices adjacent to v.
//      *
//      * @param v vertex v
//      * @return vertices adjacent to v
//      */
//     Iterable<Integer> adj(int v);
// 
//     /**
//      * Returns the number of vertices.
//      *
//      * @return number of vertices
//      */
//     int V();
// 
//     /**
//      * Returns the number of edges.
//      *
//      * @return number of edges
//      */
//     int E();
// 
//     /**
//      * Returns its reverse order.
//      *
//      * @return its reverse order
//      */
//     Graph reverse();
// 
//     /**
//      * Returns its string representation.
//      *
//      * @return string representation
//      */
//     String toString();
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/queue/Deque.java
// public class Deque<T extends Comparable<T>> implements Iterable<T> {
// 
//     private Node<T> head;
//     private Node<T> tail;
//     private int     size;
// 
//     /**
//      * Construct an empty deque.
//      */
//     public Deque() {
//         this.head = null;
//         this.tail = null;
//         this.size = 0;
//     }
// 
//     /**
//      * Is the deque empty?
//      * 
//      * @return returns if it is empty or not
//      */
//     public boolean isEmpty() {
//         return this.size == 0;
//     }
// 
//     /**
//      * Return the number of items on the deque.
//      * 
//      * @return the size
//      */
//     public int size() {
//         return this.size;
//     }
// 
//     /**
//      * Add the {@link T data} to the front.<br>
//      * <strong>Time complexity:</strong> O(1)<br>
//      * 
//      * @param data
//      */
//     public void addFirst(T data) {
//         if (data == null)
//             throw new NullPointerException();
// 
//         Node<T> oldHead = this.head;
//         this.head = new Node<T>(data);
//         this.head.next = oldHead;
// 
//         if (oldHead != null)
//             oldHead.prev = this.head;
// 
//         // when the dequeue is empty, head == tail
//         if (this.isEmpty())
//             this.tail = this.head;
// 
//         this.size++;
// 
//     }
// 
//     /**
//      * Add the {@link T data} to the end.<br>
//      * <strong>Time complexity:</strong> O(1)<br>
//      * 
//      * @param data
//      */
//     public void addLast(T data) {
//         if (data == null)
//             throw new NullPointerException();
// 
//         Node<T> oldTail = this.tail;
//         this.tail = new Node<T>(data);
//         this.tail.prev = oldTail;
// 
//         if (oldTail != null)
//             oldTail.next = this.tail;
// 
//         // when the deque is empty, head == tail
//         if (this.isEmpty())
//             this.head = this.tail;
// 
//         this.size++;
//     }
// 
//     /**
//      * Remove and return the data from the front.
//      * <strong>Time complexity:</strong> O(1)<br>
//      * 
//      * @return returns the first data
//      */
//     public T removeFirst() {
//         if (this.isEmpty())
//             throw new NoSuchElementException();
// 
//         Node<T> oldHead = this.head;
//         this.head = this.head.next;
// 
//         if (this.head != null)
//             this.head.prev = null;
// 
//         this.size--;
// 
//         // when the dequeue becomes empty, head == tail
//         if (this.isEmpty())
//             this.tail = null;
// 
//         return oldHead.data;
//     }
// 
//     /**
//      * Remove and return the data from the end.
//      * <strong>Time complexity:</strong> O(1)<br>
//      * 
//      * @return returns the last data
//      */
//     public T removeLast() {
//         if (this.isEmpty())
//             throw new NoSuchElementException();
// 
//         Node<T> oldTail = this.tail;
//         this.tail = this.tail.prev;
// 
//         if (this.tail != null)
//             this.tail.next = null;
// 
//         this.size--;
// 
//         // when the dequeue becomes empty, head == tail
//         if (this.isEmpty())
//             this.head = null;
// 
//         return oldTail.data;
//     }
// 
//     /**
//      * Return the iterator over items in order from front to end.
//      * 
//      * @return returns a new instance
//      */
//     @Override
//     public Iterator<T> iterator() {
//         return new LinkedListIterator<T>(this.head);
//     }
// }


import io.github.marioluan.datastructures.graph.Graph;
import io.github.marioluan.datastructures.queue.Deque;
package io.github.marioluan.datastructures.graph.search;


/**
 * Bread-first search implementation. <br>
 * Put unvisited vertices on a queue. <br>
 * Goal: Find path from s to v that uses fewest number of edges.
 * Category: single-source reachability.
 */
public class BreadthFirstSearch extends PathDecorator {
    private final Graph graph;
    private final int s;
    private boolean[] marked;
    private Integer[] edgeTo;
    private Integer[] disTo;

    /**
     * Performs a BFS.
     *
     * @param graph the given graph
     * @param s     the source vertex
     */
    public BreadthFirstSearch(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        marked = new boolean[graph.V()];
        edgeTo = new Integer[graph.V()];
        disTo = new Integer[graph.V()];

        search();
    }

    // Time complexity: O(V + E)
    private void search() {
// Path: src/main/java/io/github/marioluan/datastructures/graph/Graph.java
// public interface Graph {
// 
//     /**
//      * Adds an edge v-w.
//      *
//      * @param v vertex v
//      * @param w vertex w
//      */
//     void addEdge(int v, int w);
// 
//     /**
//      * Returns the vertices adjacent to v.
//      *
//      * @param v vertex v
//      * @return vertices adjacent to v
//      */
//     Iterable<Integer> adj(int v);
// 
//     /**
//      * Returns the number of vertices.
//      *
//      * @return number of vertices
//      */
//     int V();
// 
//     /**
//      * Returns the number of edges.
//      *
//      * @return number of edges
//      */
//     int E();
// 
//     /**
//      * Returns its reverse order.
//      *
//      * @return its reverse order
//      */
//     Graph reverse();
// 
//     /**
//      * Returns its string representation.
//      *
//      * @return string representation
//      */
//     String toString();
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/queue/Deque.java
// public class Deque<T extends Comparable<T>> implements Iterable<T> {
// 
//     private Node<T> head;
//     private Node<T> tail;
//     private int     size;
// 
//     /**
//      * Construct an empty deque.
//      */
//     public Deque() {
//         this.head = null;
//         this.tail = null;
//         this.size = 0;
//     }
// 
//     /**
//      * Is the deque empty?
//      * 
//      * @return returns if it is empty or not
//      */
//     public boolean isEmpty() {
//         return this.size == 0;
//     }
// 
//     /**
//      * Return the number of items on the deque.
//      * 
//      * @return the size
//      */
//     public int size() {
//         return this.size;
//     }
// 
//     /**
//      * Add the {@link T data} to the front.<br>
//      * <strong>Time complexity:</strong> O(1)<br>
//      * 
//      * @param data
//      */
//     public void addFirst(T data) {
//         if (data == null)
//             throw new NullPointerException();
// 
//         Node<T> oldHead = this.head;
//         this.head = new Node<T>(data);
//         this.head.next = oldHead;
// 
//         if (oldHead != null)
//             oldHead.prev = this.head;
// 
//         // when the dequeue is empty, head == tail
//         if (this.isEmpty())
//             this.tail = this.head;
// 
//         this.size++;
// 
//     }
// 
//     /**
//      * Add the {@link T data} to the end.<br>
//      * <strong>Time complexity:</strong> O(1)<br>
//      * 
//      * @param data
//      */
//     public void addLast(T data) {
//         if (data == null)
//             throw new NullPointerException();
// 
//         Node<T> oldTail = this.tail;
//         this.tail = new Node<T>(data);
//         this.tail.prev = oldTail;
// 
//         if (oldTail != null)
//             oldTail.next = this.tail;
// 
//         // when the deque is empty, head == tail
//         if (this.isEmpty())
//             this.head = this.tail;
// 
//         this.size++;
//     }
// 
//     /**
//      * Remove and return the data from the front.
//      * <strong>Time complexity:</strong> O(1)<br>
//      * 
//      * @return returns the first data
//      */
//     public T removeFirst() {
//         if (this.isEmpty())
//             throw new NoSuchElementException();
// 
//         Node<T> oldHead = this.head;
//         this.head = this.head.next;
// 
//         if (this.head != null)
//             this.head.prev = null;
// 
//         this.size--;
// 
//         // when the dequeue becomes empty, head == tail
//         if (this.isEmpty())
//             this.tail = null;
// 
//         return oldHead.data;
//     }
// 
//     /**
//      * Remove and return the data from the end.
//      * <strong>Time complexity:</strong> O(1)<br>
//      * 
//      * @return returns the last data
//      */
//     public T removeLast() {
//         if (this.isEmpty())
//             throw new NoSuchElementException();
// 
//         Node<T> oldTail = this.tail;
//         this.tail = this.tail.prev;
// 
//         if (this.tail != null)
//             this.tail.next = null;
// 
//         this.size--;
// 
//         // when the dequeue becomes empty, head == tail
//         if (this.isEmpty())
//             this.head = null;
// 
//         return oldTail.data;
//     }
// 
//     /**
//      * Return the iterator over items in order from front to end.
//      * 
//      * @return returns a new instance
//      */
//     @Override
//     public Iterator<T> iterator() {
//         return new LinkedListIterator<T>(this.head);
//     }
// }


// Path: src/main/java/io/github/marioluan/datastructures/graph/search/BreadthFirstSearch.java
import io.github.marioluan.datastructures.graph.Graph;
import io.github.marioluan.datastructures.queue.Deque;

package io.github.marioluan.datastructures.graph.search;


/**
 * Bread-first search implementation. <br>
 * Put unvisited vertices on a queue. <br>
 * Goal: Find path from s to v that uses fewest number of edges.
 * Category: single-source reachability.
 */
public class BreadthFirstSearch extends PathDecorator {
    private final Graph graph;
    private final int s;
    private boolean[] marked;
    private Integer[] edgeTo;
    private Integer[] disTo;

    /**
     * Performs a BFS.
     *
     * @param graph the given graph
     * @param s     the source vertex
     */
    public BreadthFirstSearch(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        marked = new boolean[graph.V()];
        edgeTo = new Integer[graph.V()];
        disTo = new Integer[graph.V()];

        search();
    }

    // Time complexity: O(V + E)
    private void search() {
        Deque<Integer> queue = new Deque<>();