程序包 edu.princeton.cs.algs4

类 BreadthFirstPaths

  • public class BreadthFirstPaths
extends java.lang.Object
    The BreadthFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or a set of source vertices) to every other vertex in an undirected graph.

    This implementation uses breadth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. Each call to distTo(int) and hasPathTo(int) takes constant time; each call to pathTo(int) takes time proportional to the length of the path. It uses extra space (not including the graph) proportional to V.

    For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • 构造器概要

      构造器 
      构造器 说明
      BreadthFirstPaths​(Graph G, int s)
      Computes the shortest path between the source vertex s and every other vertex in the graph G.
      BreadthFirstPaths​(Graph G, java.lang.Iterable<java.lang.Integer> sources)
      Computes the shortest path between any one of the source vertices in sources and every other vertex in graph G.

    • 方法概要

      修饰符和类型 方法 说明
      int distTo​(int v)
      Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v?
      boolean hasPathTo​(int v)
      Is there a path between the source vertex s (or sources) and vertex v?
      static void main​(java.lang.String[] args)
      Unit tests the BreadthFirstPaths data type.
      java.lang.Iterable<java.lang.Integer> pathTo​(int v)
      Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.

      • 从类继承的方法 java.lang.Object

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

    • 构造器详细资料

      • BreadthFirstPaths

        public BreadthFirstPaths​(Graph G,
                         int s)
        Computes the shortest path between the source vertex s and every other vertex in the graph G.
        参数:
        G - the graph
        s - the source vertex
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= s < V

      • BreadthFirstPaths

        public BreadthFirstPaths​(Graph G,
                         java.lang.Iterable<java.lang.Integer> sources)
        Computes the shortest path between any one of the source vertices in sources and every other vertex in graph G.
        参数:
        G - the graph
        sources - the source vertices
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= s < V for each vertex s in sources

    • 方法详细资料

      • hasPathTo

        public boolean hasPathTo​(int v)
        Is there a path between the source vertex s (or sources) and vertex v?
        参数:
        v - the vertex
        返回:
        true if there is a path, and false otherwise
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • distTo

        public int distTo​(int v)
        Returns the number of edges in a shortest path between the source vertex s (or sources) and vertex v?
        参数:
        v - the vertex
        返回:
        the number of edges in a shortest path
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • pathTo

        public java.lang.Iterable<java.lang.Integer> pathTo​(int v)
        Returns a shortest path between the source vertex s (or sources) and v, or null if no such path.
        参数:
        v - the vertex
        返回:
        the sequence of vertices on a shortest path, as an Iterable
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • main

        public static void main​(java.lang.String[] args)
        Unit tests the BreadthFirstPaths data type.
        参数:
        args - the command-line arguments