程序包 edu.princeton.cs.algs4

类 BreadthFirstDirectedPaths

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

    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 digraph) proportional to V.

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

    • 构造器概要

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

    • 方法概要

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

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

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

    • 构造器详细资料

      • BreadthFirstDirectedPaths

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

      • BreadthFirstDirectedPaths

        public BreadthFirstDirectedPaths​(Digraph G,
                                 java.lang.Iterable<java.lang.Integer> sources)
        Computes the shortest path from any one of the source vertices in sources to every other vertex in graph G.
        参数:
        G - the digraph
        sources - the source vertices
        抛出:
        java.lang.IllegalArgumentException - unless each vertex v in sources satisfies 0 <= v < V

    • 方法详细资料

      • hasPathTo

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

      • distTo

        public int distTo​(int v)
        Returns the number of edges in a shortest path from the source s (or sources) to 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 from s (or sources) to 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 BreadthFirstDirectedPaths data type.
        参数:
        args - the command-line arguments