Package dsa

Class BFSPaths

java.lang.Object
dsa.BFSPaths
All Implemented Interfaces:
Paths
public class BFSPaths extends Object implements Paths
An immutable data type to compute the shortest paths between a fixed source vertex and any other vertex in an undirected graph.

  • Constructor Summary

    Constructors
    Constructor
    Description
    BFSPaths(Graph G, int s)
    Computes shortest paths between source vertex s and every other vertex in the graph G.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    distTo(int v)
    Returns the shortest distance between a designated source vertex and vertex v, or infinity.
    boolean
    hasPathTo(int v)
    Returns true if there is a path between a designated source vertex and vertex * v, and false otherwise.
    static void
    main(String[] args)
    Unit tests the data type.
    Iterable<Integer>
    pathTo(int v)
    Returns a path between a designated source vertex and vertex v, or null.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • BFSPaths

      public BFSPaths(Graph G, int s)
      Computes shortest paths between source vertex s and every other vertex in the graph G.
      Parameters:
      G - the graph.
      s - the source vertex.

  • Method Details

    • hasPathTo

      public boolean hasPathTo(int v)
      Returns true if there is a path between a designated source vertex and vertex * v, and false otherwise.
      Specified by:
      hasPathTo in interface Paths
      Parameters:
      v - the vertex.
      Returns:
      true if there is a path between a designated source vertex and vertex v, and false otherwise.

    • pathTo

      public Iterable<Integer> pathTo(int v)
      Returns a path between a designated source vertex and vertex v, or null.
      Specified by:
      pathTo in interface Paths
      Parameters:
      v - the vertex.
      Returns:
      a path between a designated source vertex and vertex v, or null.

    • distTo

      public double distTo(int v)
      Returns the shortest distance between a designated source vertex and vertex v, or infinity.
      Specified by:
      distTo in interface Paths
      Parameters:
      v - the vertex.
      Returns:
      the shortest distance between a designated source vertex and vertex v, or infinity.

    • main

      public static void main(String[] args)
      Unit tests the data type.
      Parameters:
      args - the command-line arguments.