Package edu.princeton.cs.algs4

Class Graph

  • public class Graph
extends Object
    The Graph class represents an undirected graph of vertices named 0 through V – 1. It supports the following two primary operations: add an edge to the graph, iterate over all of the vertices adjacent with a given vertex. It also provides methods for returning the degree of a vertex, the number of vertices V in the graph, and the number of edges E in the graph. Parallel edges and self-loops are permitted. By convention, a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v.

    This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. It uses Θ(E + V) space, where E is the number of edges and V is the number of vertices. All instance methods take Θ(1) time. (Though, iterating over the vertices returned by adj(int) takes time proportional to the degree of the vertex.) Constructing an empty graph with V vertices takes Θ(V) time; constructing a graph with E edges and V vertices takes Θ(E + V) time.

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

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Summary

      Constructors 
      Constructor Description
      Graph​(int V)
      Initializes an empty graph with V vertices and 0 edges.
      Graph​(Graph graph)
      Initializes a new graph that is a deep copy of graph.
      Graph​(In in)
      Initializes a graph from the specified input stream.

    • Constructor Detail

      • Graph

        public Graph​(int V)
        Initializes an empty graph with V vertices and 0 edges. param V the number of vertices
        Parameters:
        V - number of vertices
        Throws:
        IllegalArgumentException - if V < 0

      • Graph

        public Graph​(In in)
        Initializes a graph from the specified input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices, with each entry separated by whitespace.
        Parameters:
        in - the input stream
        Throws:
        IllegalArgumentException - if in is null
        IllegalArgumentException - if the endpoints of any edge are not in prescribed range
        IllegalArgumentException - if the number of vertices or edges is negative
        IllegalArgumentException - if the input stream is in the wrong format

      • Graph

        public Graph​(Graph graph)
        Initializes a new graph that is a deep copy of graph.
        Parameters:
        graph - the graph to copy
        Throws:
        IllegalArgumentException - if graph is null

    • Method Detail

      • V

        public int V()
        Returns the number of vertices in this graph.
        Returns:
        the number of vertices in this graph

      • E

        public int E()
        Returns the number of edges in this graph.
        Returns:
        the number of edges in this graph

      • addEdge

        public void addEdge​(int v,
                    int w)
        Adds the undirected edge v-w to this graph.
        Parameters:
        v - one vertex in the edge
        w - the other vertex in the edge
        Throws:
        IllegalArgumentException - unless both 0 <= v < V and 0 <= w < V

      • adj

        public Iterable<Integer> adj​(int v)
        Returns the vertices adjacent with vertex v.
        Parameters:
        v - the vertex
        Returns:
        the vertices adjacent with vertex v, as an iterable
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • degree

        public int degree​(int v)
        Returns the degree of vertex v.
        Parameters:
        v - the vertex
        Returns:
        the degree of vertex v
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • toString

        public String toString()
        Returns a string representation of this graph.
        Overrides:
        toString in class Object
        Returns:
        the number of vertices V, followed by the number of edges E, followed by the V adjacency lists

      • toDot

        public String toDot()
        Returns a string representation of this graph in DOT format, suitable for visualization with Graphviz. To visualize the graph, install Graphviz (e.g., "brew install graphviz"). Then use one of the graph visualization tools - dot (hierarchical or layer drawing) - neato (spring model) - fdp (force-directed placement) - sfdp (scalable force-directed placement) - twopi (radial layout) For example, the following commands will create graph drawings in SVG and PDF formats - dot input.dot -Tsvg -o output.svg - dot input.dot -Tpdf -o output.pdf To change the graph attributes (e.g., vertex and edge shapes, arrows, colors) in the DOT format, see https://graphviz.org/doc/info/lang.html
        Returns:
        a string representation of this graph in DOT format

      • main

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