From Algorithms by professors Sedgewick and Wayne
Tremaux Exploration:
One trick for exploring a maze without getting lost that has been known since antiquity (dating back at least to the legend of Theseus and the Minotaur) is known as Tremaux exploration. To explore all passages in a maze:
- Take any unmarked passage, unrolling a string behind you.
- Mark all intersections and passages when you first visit them.
- Retrace steps (using the string) when approaching a marked intersection.
- Retrace steps when no unvisited options remain at an intersection encountered while retracing steps.
The string guarantees that you can always find a way out and the marks guarantee that you avoid visiting any passage or intersection twice.
public class DepthFirstSearch
{
private boolean[] marked;
private int count;
public DepthFirstSearch(Graph G, int s)
{
marked = new boolean[G.V()];
dfs(G, s);
}
private void dfs(Graph G, int v)
{
marked[v] = true;
count++;
for (int w : G.adj(v))
if (!marked[w]) dfs(G, w);
}
public boolean marked(int w)
{
return marked[w];
}
public int count()
{
return count;
}
}| Proposition A. DFS marks all the vertices connected to a given source in time proportional to the sum of their degrees. |
Proposition A. DFS marks all the vertices connected to a given source in time proportional to the sum of their degrees.
Proof: First, we prove that the algorithm marks all the vertices connected to the source s (and no others). Every marked vertex is connected to s, since the algorithm finds vertices only by following edges. Now, suppose that some unmarked vertex w is connected to s. Since s itself is marked, any path from s to w must have at least one edge from the set of marked vertices to the set of unmarked vertices, say v-x. But the algorithm would have discovered x after marking v, so no such edge can exist, a contradiction. The time bound follows because marking ensures that each vertex is visited once (taking time proportional to its degree to check marks).
13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3
Below is the syntax highlighted version of Graph.java from §4.1 Undirected Graphs. /****************************************************************************** * Compilation: javac Graph.java * Execution: java Graph input.txt * Dependencies: Bag.java In.java StdOut.java * Data files: http://algs4.cs.princeton.edu/41graph/tinyG.txt * * A graph, implemented using an array of sets. * Parallel edges and self-loops allowed. * * % java Graph tinyG.txt * 13 vertices, 13 edges * 0: 6 2 1 5 * 1: 0 * 2: 0 * 3: 5 4 * 4: 5 6 3 * 5: 3 4 0 * 6: 0 4 * 7: 8 * 8: 7 * 9: 11 10 12 * 10: 9 * 11: 9 12 * 12: 11 9 * * % java Graph mediumG.txt * 250 vertices, 1273 edges * 0: 225 222 211 209 204 202 191 176 163 160 149 114 97 80 68 59 58 49 44 24 15 * 1: 220 203 200 194 189 164 150 130 107 72 * 2: 141 110 108 86 79 51 42 18 14 * ... * ******************************************************************************/
/******************************************************************************
* Compilation: javac Graph.java
* Execution: java Graph input.txt
* Dependencies: Bag.java Stack.java In.java StdOut.java
* Data files: https://algs4.cs.princeton.edu/41graph/tinyG.txt
* https://algs4.cs.princeton.edu/41graph/mediumG.txt
* https://algs4.cs.princeton.edu/41graph/largeG.txt
*
* A graph, implemented using an array of sets.
* Parallel edges and self-loops allowed.
*
* % java Graph tinyG.txt
* 13 vertices, 13 edges
* 0: 6 2 1 5
* 1: 0
* 2: 0
* 3: 5 4
* 4: 5 6 3
* 5: 3 4 0
* 6: 0 4
* 7: 8
* 8: 7
* 9: 11 10 12
* 10: 9
* 11: 9 12
* 12: 11 9
*
* % java Graph mediumG.txt
* 250 vertices, 1273 edges
* 0: 225 222 211 209 204 202 191 176 163 160 149 114 97 80 68 59 58 49 44 24 15
* 1: 220 203 200 194 189 164 150 130 107 72
* 2: 141 110 108 86 79 51 42 18 14
* …
*
******************************************************************************/
package edu.princeton.cs.algs4;
import java.util.NoSuchElementException;
/**
* The {@code Graph} class represents an undirected graph of vertices
* named 0 through <em>V</em> – 1.
* It supports the following two primary operations: add an edge to the graph,
* iterate over all of the vertices adjacent to a vertex. It also provides
* methods for returning the number of vertices <em>V</em> and the number
* of edges <em>E</em>. Parallel edges and self-loops are permitted.
* By convention, a self-loop <em>v</em>-<em>v</em> appears in the
* adjacency list of <em>v</em> twice and contributes two to the degree
* of <em>v</em>.
* <p>
* This implementation uses an adjacency-lists representation, which
* is a vertex-indexed array of {@link Bag} objects.
* All operations take constant time (in the worst case) except
* iterating over the vertices adjacent to a given vertex, which takes
* time proportional to the number of such vertices.
* <p>
* For additional documentation, see <a href=”https://algs4.cs.princeton.edu/41graph”>Section 4.1</a>
* of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Graph {
private static final String NEWLINE = System.getProperty(“line.separator”);
private final int V;
private int E;
private Bag<Integer>[] adj;
/**
* Initializes an empty graph with {@code V} vertices and 0 edges.
* param V the number of vertices
*
* @param V number of vertices
* @throws IllegalArgumentException if {@code V < 0}
*/
public Graph(int V) {
if (V < 0) throw new IllegalArgumentException(“Number of vertices must be nonnegative”);
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>();
}
}
/**
* Initializes a graph from the specified input stream.
* The format is the number of vertices <em>V</em>,
* followed by the number of edges <em>E</em>,
* followed by <em>E</em> pairs of vertices, with each entry separated by whitespace.
*
* @param in the input stream
* @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range
* @throws IllegalArgumentException if the number of vertices or edges is negative
* @throws IllegalArgumentException if the input stream is in the wrong format
*/
public Graph(In in) {
try {
this.V = in.readInt();
if (V < 0) throw new IllegalArgumentException(“number of vertices in a Graph must be nonnegative”);
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>();
}
int E = in.readInt();
if (E < 0) throw new IllegalArgumentException(“number of edges in a Graph must be nonnegative”);
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
validateVertex(v);
validateVertex(w);
addEdge(v, w);
}
}
catch (NoSuchElementException e) {
throw new IllegalArgumentException(“invalid input format in Graph constructor”, e);
}
}
/**
* Initializes a new graph that is a deep copy of {@code G}.
*
* @param G the graph to copy
*/
public Graph(Graph G) {
this(G.V());
this.E = G.E();
for (int v = 0; v < G.V(); v++) {
// reverse so that adjacency list is in same order as original
Stack<Integer> reverse = new Stack<Integer>();
for (int w : G.adj[v]) {
reverse.push(w);
}
for (int w : reverse) {
adj[v].add(w);
}
}
}
/**
* Returns the number of vertices in this graph.
*
* @return the number of vertices in this graph
*/
public int V() {
return V;
}
/**
* Returns the number of edges in this graph.
*
* @return the number of edges in this graph
*/
public int E() {
return E;
}
// throw an IllegalArgumentException unless {@code 0 <= v < V}
private void validateVertex(int v) {
if (v < 0 || v >= V)
throw new IllegalArgumentException(“vertex ” + v + ” is not between 0 and ” + (V-1));
}
/**
* Adds the undirected edge v-w to this graph.
*
* @param v one vertex in the edge
* @param w the other vertex in the edge
* @throws IllegalArgumentException unless both {@code 0 <= v < V} and {@code 0 <= w < V}
*/
public void addEdge(int v, int w) {
validateVertex(v);
validateVertex(w);
E++;
adj[v].add(w);
adj[w].add(v);
}
/**
* Returns the vertices adjacent to vertex {@code v}.
*
* @param v the vertex
* @return the vertices adjacent to vertex {@code v}, as an iterable
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public Iterable<Integer> adj(int v) {
validateVertex(v);
return adj[v];
}
/**
* Returns the degree of vertex {@code v}.
*
* @param v the vertex
* @return the degree of vertex {@code v}
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public int degree(int v) {
validateVertex(v);
return adj[v].size();
}
/**
* Returns a string representation of this graph.
*
* @return the number of vertices <em>V</em>, followed by the number of edges <em>E</em>,
* followed by the <em>V</em> adjacency lists
*/
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + ” vertices, ” + E + ” edges ” + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + “: “);
for (int w : adj[v]) {
s.append(w + ” “);
}
s.append(NEWLINE);
}
return s.toString();
}
/**
* Unit tests the {@code Graph} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
StdOut.println(G);
}
}
/******************************************************************************
* Copyright 2002-2018, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/
</p[collapse]
GraphClient.java
Below is the syntax highlighted version of GraphClient.java from §4.1 Undirected Graphs.
/******************************************************************************
* Compilation: javac GraphClient.java
* Execution: java GraphClient graph.txt
* Dependencies: Graph.java
*
* Typical graph-processing code.
*
* % java GraphClient tinyG.txt
* 13 13
* 0: 6 2 1 5
* 1: 0
* 2: 0
* 3: 5 4
* 4: 5 6 3
* 5: 3 4 0
* 6: 0 4
* 7: 8
* 8: 7
* 9: 11 10 12
* 10: 9
* 11: 9 12
* 12: 11 9
*
* vertex of maximum degree = 4
* average degree = 2
* number of self loops = 0
*
******************************************************************************/
public class GraphClient {
// degree of v
public static int degree(Graph G, int v) {
int degree = 0;
for (int w : G.adj(v)) degree++;
return degree;
}
// maximum degree
public static int maxDegree(Graph G) {
int max = 0;
for (int v = 0; v < G.V(); v++)
if (degree(G, v) > max)
max = degree(G, v);
return max;
}
// average degree
public static int avgDegree(Graph G) {
// each edge incident on two vertices
return 2 * G.E() / G.V();
}
// number of self-loops
public static int numberOfSelfLoops(Graph G) {
int count = 0;
for (int v = 0; v < G.V(); v++)
for (int w : G.adj(v))
if (v == w) count++;
return count/2; // self loop appears in adjacency list twice
}
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
StdOut.println(G);
StdOut.println("vertex of maximum degree = " + maxDegree(G));
StdOut.println("average degree = " + avgDegree(G));
StdOut.println("number of self loops = " + numberOfSelfLoops(G));
}
}
Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne.
Last updated: Wed Aug 26 07:22:59 EDT 2015.
Below is the syntax highlighted version of AdjMatrixGraph.java from §4.1 Undirected Graphs.
/******************************************************************************
* Compilation: javac AdjMatrixGraph.java
* Execution: java AdjMatrixGraph V E
* Dependencies: StdOut.java
*
* A graph, implemented using an adjacency matrix.
* Parallel edges are disallowed; self-loops are allowd.
*
******************************************************************************/
import java.util.Iterator;
import java.util.NoSuchElementException;
public class AdjMatrixGraph {
private static final String NEWLINE = System.getProperty("line.separator");
private int V;
private int E;
private boolean[][] adj;
// empty graph with V vertices
public AdjMatrixGraph(int V) {
if (V < 0) throw new RuntimeException("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
this.adj = new boolean[V][V];
}
// random graph with V vertices and E edges
public AdjMatrixGraph(int V, int E) {
this(V);
if (E < 0) throw new RuntimeException("Number of edges must be nonnegative");
if (E > V*(V-1) + V) throw new RuntimeException("Too many edges");
// can be inefficient
while (this.E != E) {
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
addEdge(v, w);
}
}
// number of vertices and edges
public int V() { return V; }
public int E() { return E; }
// add undirected edge v-w
public void addEdge(int v, int w) {
if (!adj[v][w]) E++;
adj[v][w] = true;
adj[w][v] = true;
}
// does the graph contain the edge v-w?
public boolean contains(int v, int w) {
return adj[v][w];
}
// return list of neighbors of v
public Iterable adj(int v) {
return new AdjIterator(v);
}
// support iteration over graph vertices
private class AdjIterator implements Iterator, Iterable {
private int v;
private int w = 0;
AdjIterator(int v) {
this.v = v;
}
public Iterator iterator() {
return this;
}
public boolean hasNext() {
while (w < V) {
if (adj[v][w]) return true;
w++;
}
return false;
}
public Integer next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return w++;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
// string representation of Graph - takes quadratic time
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (int w : adj(v)) {
s.append(w + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
// test client
public static void main(String[] args) {
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]);
AdjMatrixGraph G = new AdjMatrixGraph(V, E);
StdOut.println(G);
}
}
Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne.
Last updated: Wed Aug 26 07:22:59 EDT 2015.
Below is the syntax highlighted version of DepthFirstSearch.java from §4.1 Undirected Graphs.
/******************************************************************************
* Compilation: javac DepthFirstSearch.java
* Execution: java DepthFirstSearch filename.txt s
* Dependencies: Graph.java StdOut.java
* Data files: http://algs4.cs.princeton.edu/41graph/tinyG.txt
*
* Run depth first search on an undirected graph.
* Runs in O(E + V) time.
*
* % java DepthFirstSearch tinyG.txt 0
* 0 1 2 3 4 5 6
* NOT connected
*
* % java DepthFirstSearch tinyG.txt 9
* 9 10 11 12
* NOT connected
*
******************************************************************************/
/**
* The DepthFirstSearch class represents a data type for
* determining the vertices connected to a given source vertex s
* in an undirected graph. For versions that find the paths, see
* {@link DepthFirstPaths} and {@link BreadthFirstPaths}.
*
* This implementation uses depth-first search. * The constructor takes time proportional to V + E * (in the worst case), * where V is the number of vertices and E is the number of edges. * 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. * * @author Robert Sedgewick * @author Kevin Wayne */ public class DepthFirstSearch { private boolean[] marked; // marked[v] = is there an s-v path? private int count; // number of vertices connected to s /** * Computes the vertices in graph G that are * connected to the source vertex s. * @param G the graph * @param s the source vertex */ public DepthFirstSearch(Graph G, int s) { marked = new boolean[G.V()]; dfs(G, s); } // depth first search from v private void dfs(Graph G, int v) { count++; marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } } /** * Is there a path between the source vertex s and vertex v? * @param v the vertex * @return true if there is a path, false otherwise */ public boolean marked(int v) { return marked[v]; } /** * Returns the number of vertices connected to the source vertex s. * @return the number of vertices connected to the source vertex s */ public int count() { return count; } /** * Unit tests the DepthFirstSearch data type. */ public static void main(String[] args) { In in = new In(args[0]); Graph G = new Graph(in); int s = Integer.parseInt(args[1]); DepthFirstSearch search = new DepthFirstSearch(G, s); for (int v = 0; v < G.V(); v++) { if (search.marked(v)) StdOut.print(v + ” “); } StdOut.println(); if (search.count() != G.V()) StdOut.println(“NOT connected”); else StdOut.println(“connected”); } } Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. Last updated: Wed Aug 26 07:33:08 EDT 2015.
Below is the syntax highlighted version of Date.java.
/******************************************************************************
* Compilation: javac Date.java
* Execution: java Date
* Dependencies: StdOut.java
*
* An immutable data type for dates.
*
******************************************************************************/
package edu.princeton.cs.algs4;
/**
* The {@code Date} class is an immutable data type to encapsulate a
* date (day, month, and year).
* <p>
* For additional documentation,
* see <a href="https://algs4.cs.princeton.edu/12oop">Section 1.2</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Date implements Comparable<Date> {
private static final int[] DAYS = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
private final int month; // month (between 1 and 12)
private final int day; // day (between 1 and DAYS[month]
private final int year; // year
/**
* Initializes a new date from the month, day, and year.
* @param month the month (between 1 and 12)
* @param day the day (between 1 and 28-31, depending on the month)
* @param year the year
* @throws IllegalArgumentException if this date is invalid
*/
public Date(int month, int day, int year) {
if (!isValid(month, day, year)) throw new IllegalArgumentException("Invalid date");
this.month = month;
this.day = day;
this.year = year;
}
/**
* Initializes new date specified as a string in form MM/DD/YYYY.
* @param date the string representation of this date
* @throws IllegalArgumentException if this date is invalid
*/
public Date(String date) {
String[] fields = date.split("/");
if (fields.length != 3) {
throw new IllegalArgumentException("Invalid date");
}
month = Integer.parseInt(fields[0]);
day = Integer.parseInt(fields[1]);
year = Integer.parseInt(fields[2]);
if (!isValid(month, day, year)) throw new IllegalArgumentException("Invalid date");
}
/**
* Return the month.
* @return the month (an integer between 1 and 12)
*/
public int month() {
return month;
}
/**
* Returns the day.
* @return the day (an integer between 1 and 31)
*/
public int day() {
return day;
}
/**
* Returns the year.
* @return the year
*/
public int year() {
return year;
}
// is the given date valid?
private static boolean isValid(int m, int d, int y) {
if (m < 1 || m > 12) return false;
if (d < 1 || d > DAYS[m]) return false;
if (m == 2 && d == 29 && !isLeapYear(y)) return false;
return true;
}
// is y a leap year?
private static boolean isLeapYear(int y) {
if (y % 400 == 0) return true;
if (y % 100 == 0) return false;
return y % 4 == 0;
}
/**
* Returns the next date in the calendar.
*
* @return a date that represents the next day after this day
*/
public Date next() {
if (isValid(month, day + 1, year)) return new Date(month, day + 1, year);
else if (isValid(month + 1, 1, year)) return new Date(month + 1, 1, year);
else return new Date(1, 1, year + 1);
}
/**
* Compares two dates chronologically.
*
* @param that the other date
* @return {@code true} if this date is after that date; {@code false} otherwise
*/
public boolean isAfter(Date that) {
return compareTo(that) > 0;
}
/**
* Compares two dates chronologically.
*
* @param that the other date
* @return {@code true} if this date is before that date; {@code false} otherwise
*/
public boolean isBefore(Date that) {
return compareTo(that) < 0;
}
/**
* Compares two dates chronologically.
*
* @return the value {@code 0} if the argument date is equal to this date;
* a negative integer if this date is chronologically less than
* the argument date; and a positive ineger if this date is chronologically
* after the argument date
*/
@Override
public int compareTo(Date that) {
if (this.year < that.year) return -1;
if (this.year > that.year) return +1;
if (this.month < that.month) return -1;
if (this.month > that.month) return +1;
if (this.day < that.day) return -1;
if (this.day > that.day) return +1;
return 0;
}
/**
* Returns a string representation of this date.
*
* @return the string representation in the format MM/DD/YYYY
*/
@Override
public String toString() {
return month + "/" + day + "/" + year;
}
/**
* Compares this date to the specified date.
*
* @param other the other date
* @return {@code true} if this date equals {@code other}; {@code false} otherwise
*/
@Override
public boolean equals(Object other) {
if (other == this) return true;
if (other == null) return false;
if (other.getClass() != this.getClass()) return false;
Date that = (Date) other;
return (this.month == that.month) && (this.day == that.day) && (this.year == that.year);
}
/**
* Returns an integer hash code for this date.
*
* @return an integer hash code for this date
*/
@Override
public int hashCode() {
int hash = 17;
hash = 31*hash + month;
hash = 31*hash + day;
hash = 31*hash + year;
return hash;
}
/**
* Unit tests the {@code Date} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
Date today = new Date(2, 25, 2004);
StdOut.println(today);
for (int i = 0; i < 10; i++) {
today = today.next();
StdOut.println(today);
}
StdOut.println(today.isAfter(today.next()));
StdOut.println(today.isAfter(today));
StdOut.println(today.next().isAfter(today));
Date birthday = new Date(10, 16, 1971);
StdOut.println(birthday);
for (int i = 0; i < 10; i++) {
birthday = birthday.next();
StdOut.println(birthday);
}
}
}
/******************************************************************************
* Copyright 2002-2018, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/
Last updated: Mon Jan 7 08:35:40 EST 2019.