Course Name: Algorithms, Part II

Instructor: Professor Kevin Wayne, Professor Robert Sedgewick

Books: Algorithms(4th edition)

Week 1

Undirected Graphs

Introduction to Graphs
- Graph: set of vertices connected pairwise by edges
- Graph terminology:
  - Degree: the degree of a vertex is the number of edges incident on it.
  - Path: sequence of vertices connected by edges, with no repeated edges
  - Cycle: path whose first and last vertices are the same
  - Length: the length or a path or a cycle is its number of edges
  - Connected graph: if there is a path from every vertex to every other vertex
  - Acyclic graph: a graph with no cycles
  - Tree: an acyclic connected graph
  - Spanning tree: a spanning tree of a connected graph is a subgraph that contains all of that graph's vertices and is a single tree. A spanning forest of a graph is the union of the spanning trees of its connected components.
- Some problems:
  - Path: is there a path between \(s\) and \(t\)
  - Shortest path: what is the shortest path between \(s\) and \(t\)
  - Cycle: is there a cycle in the graph
  - Euler tour: is there a cycle that uses each edge exactly once
  - Hamilton tour: is there a cycle that uses each vertex exactly once
  - Connectivity: is there a way to connect all of the vertices
  - MST(minimal spanning tree): what is the best way to connect all of the vertices
  - Biconnectivity: is there a vertex whose removal disconnects the graph
  - Planarity: can you draw the graph in the plane with no crossing edges
  - Graph isomorphism: do two adjacency lists represent the same graph

Graph API

Graph representation
- Vertex representation:
  - Integers between \(0\) and \(V - 1\)
  - Convert between names and integers with symbol table
- Anomalies: self-loop and parallel edges

Graph API

public class Graph {
  // create an empty graph with V vertices
  Graph(int V);
  // create a graph from input stream
  Graph(In in);
  // add an edge v-w
  void addEdge(int v, int w);
  // vertices adjacent to v
  Iterable<Integer> adj(int v);
  // number of vertices
  int V();
  // number of edges
  int E();
  // string representation of a graph
  String toString();
}

Some graph-processing code:

// degree of vertex v
public static int degree(Graph G, int v) {
  int degree = 0;
  for (int w: G.adj(v)) {
    degree ++;
  }
  return degree;
}
// max degree of all vertices 
public static int maxDegree(Graph G) {
  int maxDeg = 0;
  for (int v = 0; v < G.V(); v++) {
    if (degree(G, v) > maxDeg) {
      maxDeg = degree(G, v);
    }
  }
  return maxDeg;
}
// average degree of all vertices
public static double avgDegree(Graph G) {
  return 2.0 * 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 (w == v) {
        count ++;
      }
    }
  }
  return count / 2;
}

Graph representation

Self-of-edges graph representation: maintain an array to store every edge in the graph. To implement adj() method, you need to travel all edges, which is unacceptable
Adjacency-matrix graph representation: maintain a two-dimensional V-by-V boolean array, for each edge v-w in graph, adj[v][w] = adj[w][v] = true. Storing \(O(V^2)\) boolean conditions is unacceptable
Adjacency-list graph representation: maintain vertex-indexed array of lists, at each position of the list, it stores a list of adjacent vertices to the current vertex

Java implementation of adjacency-list graph

public class Graph {
  private final int V;
  private Bag<Integer>[] adj;

  public Graph(int V) {
    this.V = V;
    adj = (new Bag<Integer>[]) new Bag[V];
    for (int v = 0; v < V; V++) {
      adj[v] = new Bag<Integer>();
    }
  }

  public void addEdge(int v, int w) {
    adj[v].add(w);
    adj[w].add(v);
  }

  public Iterable<Integer> adj(int v) {
    return adj[v];
  }
}

Performance analysis

representation	space	add edge	edge between v and w	iterate over vertices adjacent to v
list of edges	\(E\)	\(1\)	\(E\)	\(E\)
adjacency matrix	\(V^2\)	\(1\)	\(1\)	\(V\)
adjacency lists	\(E+V\)	\(1\)	\(degree(v)\)	\(degree(v)\)

Depth-First Search

Example: Tremaux maze exploration
DFS idea: recursively travel through all vertices, when visiting vertex v
- Mark v as visited
- Recursively visit all unmarked vertices w adjacent to v
Applications
- Connectivity: if two vertices are connected, if there is a connected subgraph
- Single-point path: given a graph G and a start vertex s, if there is a path from s to a specific vertex v, find the path if there is one
Design pattern for graph processing: decouple graph data type from graph processing
- Steps:
  - Create a graph object
  - Pass the graph to a graph-processing routine
  - Query the graph-processing routine for information

Search API:

public class Search {
  // find vertices connected to a source vertex s
  Search(Graph G, int s);
  // is v connected to s
  boolean marked(int v);
  // how many vertices are connected to s
  int count();
}

DFS search implementation

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 v) {
    return marked[v];
  }

  public int count() {
    return count;
  }
}

Paths

Path API:

public class Paths {
  // find paths in G from source s
  Paths(Graph G, int s);
  // is there a path from s to v
  boolean hasPathTo(int v);
  // path from s to v; null if no such path
  Iterable<Integer> pathTo(int v);
}

DFS paths implementation

public class DepthFirstPaths {
  private boolean[] marked;
  // it gives a way to find a path back to s for every vertex connected to s,  
  // alternatively speaking, if w in G.adj(v) and w is unvisited, then edgeTo[w] = v
  private int[] edgeTo;
  private final int s;

  public DepthFirstPaths(Graph G, int s) {
    marked = new boolean[G.V()];
    edgeTo = new int[G.V()];
    this.s = s;
    dfs(G, s);
  }

  private void dfs(Graph G, int v) {
    marked[v] = true;
    for (int w: G.adj(v)) {
      if (!marked[w]) {
        edgeTo[w] = v;
        dfs(G, w);
      }
    }

    public boolean hasPathTo(int v) {
      return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
      is (!hasPathTo(v)) {
        return null;
      }
      Stack<Integer> path = new Stack<Integer>();
      for (int x = v; x != s; x = edgeTo(x)) {
        path.push(x);
      }
      path.push(s);
      return path;
    }
  }
}

Performance analysis:
- DFS marks all vertices connected to \(s\) in time proportional to the sum of their degrees
- After DFS, can find vertices connected to \(s\) in constant time and can find a path to \(s\) (if one exists) in time proportional to its length
- The time complexity of DFS is \(O(V + E)\)

Breadth-First-Search

BFS: use an auxiliary queue to do BFS
- add start vertex to the queue and mark it
- remove a vertex from the queue, add all adjacent unmarked vertices to the queue and mark them
- repeat the process until the queue is empty
Applications
- Single-source shortest path: given a graph G and a source vertex s, find if there is a path from s to a specific vertex v, if there are paths from s to v, find the shortest one
Compare DFS and BFS
- DFS: put unvisited vertices on a stack
- BFS: put unvisited vertices on a queue

BFS java implementation:

public class BreadthFirstSearch {
  private boolean[] marked;
  private int[] edgeTo;
  private final int s;

  public BreadthFirstSearch(Graph G, int s) {
    marked = new boolean[G.V()];
    edgeTo = new int[G.V()];
    this.s = s;
    bfs(G, s);
  }

  private void bfs(Graph G, int s) {
    Queue<Integer> queue = new Queue<Integer>();
    marked[s] = true;
    queue.enqueue(s);
    while (!queue.isEmpty()) {
      int v = queue.dequeue();
      for (int w: G.adj(v)) {
        if (!marked[w]) {
          edgeTo[w] = v;
          marked[w] = true;
          queue.enqueue(w);
        }
      }
    }
  }

  public boolean hasPathTo(int v) {
    return marked[v];
  }

  public Iterable<Integer> pathTo(int v) {
    if (!hasPathTo(v)) {
      return null;
    }
    Stack<Integer> path = new Stack<Integer>(); 
    for (int x = v; x != s; x = edgeTo[x]) {
      path.push(x);
    }
    path.push(s);
    return path;
  }
}

Performance analysis:
- For any vertex v reachable from s, BFS computes a shortest path from s to v (no path from s to v has fewer edges). BFS takes time proportional to V + E in the worst case
- The time complexity of BFS is \(O(V + E)\)

Connected Components

Connectivity queries
- Definition: vertices v and w are connected if there is a path between them
- Goal: process graph to answer queries of the form is v connected to w in constant time

Connected Components API

public class CC{
  // find connected components in G
  CC(Graph G);
  // are v and w connected
  boolean connected(int v, int w);
  // number of connected components
  int count();
  // component identifier for v, vertices in the one CC have a same identifier
  int id(int v);
}

The relation "is connected to" is an equivalence relation: reflexive, symmetric, transitive

Connected components:

Definition: a CC is a maximal set of connected vertices
Goal: partition vertices into CC
Steps:
- Initialize all vertices v as unmarked
- For each unmarked vertex v, run DFS to identify all vertices discovered as part of the same component, mark points in the same CC with a same id

Java implementation:

public class CC {
  private boolean[] marked;
  private int[] id;
  private int count;

  public CC(Graph G) {
    marked = new int[G.V()];
    id = new int[G.V()];
    for (int v = 0; v < G.V(); v++) {
      if (!marked[v]) {
        dfs(G, v);
        count++;
      }
    }
  }

  private void dfs(Graph G, int v) {
    marked[v] = true;
    id[v] = count;
    for (int w: G.adj(v)) {
      if (!marked[w]) {
        dfs(G, w);
      }
    }
  }

  public int count() {
    return count;
  }

  public int id(int v) {
    return id[v];
  }
}

Preposition: DFS uses preprocessing time and space proportional to V + E to support constant-time connectivity queries in a graph

Graph Challenges

Problem 1: Is a graph bipartite(二分图)

Bipartite graph: a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V

Java DFS implementation

public class TwoColor {
  private boolean[] marked;
  private boolean[] color;
  private boolean twoColorable = true;

  public TwoColor(Graph G) {
    marked = new boolean[G.V()];
    color = new boolean[G.V()];
    for (int v = 0; v < G.V(); v++) {
      if (!marked[v]) {
        dfs(G, v);
      }
    }
  }

  private void dfs(Graph G, int v) {
    marked[v] = true;
    for (int w: G.adj(v)) {
      if (!marked[w]) {
        dfs (G, w);
      } else if (color[w] == color[v]) {
        twoColorable = false;
      }
    }
  }

  public boolean isBipartite() {
    return twoColorable;
  }
}

Problem 2: Does an undirected graph have a cycle

Java DFS implementation:

public class Cycle {
  private boolean[] marked;
  private boolean hasCycle;

  public Cycle(Graph G) {
    marked = new boolean[G.V()];
    for (int v = 0; v < G.V(); v++) {
      if (!marked[v]) {
        dfs(G, v, v);
      }
    }
  }

  private void dfs(Graph G, int v, int u) {
    marked[v] = true;
    for (int w: G.adj(v)) {
      if (!marked[w]) {
        dfs(G, w, v);
      } else if (w != u) { // in this situation, w is connected to v and has been visited by inner loop of DFS
        hasCycle = true;
      }
    }
  }

  public boolean hasCycle() {
    return hasCycle;
  }
}

Problem 3: Find a general cycle that uses every edge exactly once
- Eulerian cycle: a cycle in a graph that uses every edge exactly once
- A graph is called Eulerian if it has an Eulerian cycle
- Conditions for a graph has a Eulerian cycle:
  - All vertices with non-zero degree are connected, this can be done using DFS
  - All vertices have even degree
- Fleury's algorithm:
Problem 4: Find a general cycle that uses every vertex exactly once(traveling salesperson problem)
- This travel is called Hamiltonian travel
- The problem is intractable, it's NP-complete problem
Problem 5: Are two graphs identical except for vertex names
- This graph isomorphism problem a open problem
Problem 6: Lay out a graph in the plane without crossing edges
- There is a linear-time DFS-based planarity algorithm discovered by Tarjan in 1970

Interview Questions:

Problem 1: Implement depth-first search in an undirected graph without using recursion

Difference with BFS:
- It uses a stack instead of a queue
- It should mark elements only after popping the vertex, not before pushing it

Java implementation

public class IterativeDFS {
  private boolean[] marked;
  private final int s;

  public IterativeDFS(Graph G, int s) {
    marked = new boolean[G.V()];
    this.s = s;
    dfs(G, s);
  }

  private void dfs(Graph G, int v) {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(v);
    while (!stack.isEmpty()) {
      int v = stack.pop();
      marked[v] = true;
      for (int w: G.adj(v)) {
        if (!marked[w]) {
          stack.push(w);
        }
      }
    }
  }
}

Directed Graph

Introduction to Digraphs
- Directed graphs
  - Definition: set of vertices connected pairwise by directed edges
  - For edge \(v \rightarrow w\), v is head, w is tail, we say v points to w
  - Reachable: w is reachable from v if there is a directed path from v to w
  - Indegree: the number of edges pointing to a vertex
  - Outdegree: the number of edges pointing from a vertex
  - Strongly connected: two vertices are strongly connected if they are mutually reachable
  - Directed acyclic graph: a DAG is a digraph with no directed cycles
- Some digraph problems
  - Path: is there a directed path from s to t
  - Shortest path: what is the shortest directed path from s to t
  - Topological sort: can you draw a digraph so that all edges point upwards
  - Strong connectivity: is there a directed path between all pairs of vertices
  - Transitive closure: for which vertices v and w is there a path from v to w
  - PageRank: what is the importance of a web page

Digraph API

Digraph API：

public class Digraph {
  // create an empty digraph with V vertices
  Digraph(int V);
  // create a digraph from input stream
  Digraph(In in);
  // add a directed edge v -> w
  void addEdge(int v, int w);
  // vertices pointing from v
  Iterable<Integer> adj(int v);
  // number of vertices
  int V();
  // number of edges
  int E();
  // reverse of the digraph
  Digraph reverse();
  // string representation
  String toString();
}

Adjacent-lists digraph representation: maintain vertex-indexed array of lists

Java implementation

public class Digraph {
  private final int V;
  private final Bag<Integer>[] adj;

  public Digraph(int V) {
    this.V = V;
    adj = (Bag<Integer>[]) new Bag[V];
    for (int v = 0; v < V; v++) {
      adj[v] = new Bag<Integer>();
    }
  }

  public void addEdge(int v, int w) {
    adj[v].add(w);
  }

  public Iterable<Integer> adj(int v) {
    return adj[v];
  }
}

Performance analysis

representation	space	add edge	edge between v and w	iterate over vertices adjacent to v
list of edges	\(E\)	\(1\)	\(E\)	\(E\)
adjacency matrix	\(V^2\)	\(1\)	\(1\)	\(V\)
adjacency lists	\(E+V\)	\(1\)	\(doutegree(v)\)	\(outdegree(v)\)

Digraph Search

DFS in digraphs: same as the one in DFS for undirected graph

Algorithm:
- To visit a vertex v:
  - Mark v as visited
  - Recursively visit all unmarked vertices w pointing from v
Applications:
- program control-flow analysis
- mark-sweep garbage collector

Implementation

public class DirectedDFS {
  private boolean[] marked;

  public DirectedDFS(Digraph G, int s) {
    marked = new boolean[G.V()];
    dfs(G, s);
  }

  private void dfs(Digraph G, int v) {
    marked[v] = true;
    for (int w: G.adj(v)) {
      if (!marked[w]) {
        dfs(G, w);
      }
    }
  }

  public boolean reachable(int v) {
    return marked[v];
  }
}

BFS in digraphs: same as the one in BFS for undirected graph
- Algorithm:
  - BFS from source vertex s:
    - Put s onto a FIFO queue, and mark s as visited
    - Repeat until the queue is empty:
      - Remove the least recently added vertex v
      - For each unmarked vertex pointing from v, add to queue and mark as visited it
- Applications:
  - Web crawler

Topological sort

Precedence scheduling
- Goal: given a set of tasks to be completed with precedence constraints, in which order should we schedule the tasks
- Digraph model: vertex = task; edge = precedence constraints
Topological sort:
- DAG: directed acyclic graph, topological sort works only on DAG
- Topological sort: redraw the DAG so all edges point upwards
- Preposition: reverse DFS postorder of a DAG is a topological order
- Preposition: a digraph has a topological order iff no directed cycle
Solution:
- Run DFS
- Return vertices in reverse postorder

Java implementation

public class DepthFirstOrder {
  private boolean[] marked;
  private Stack<Integer> reversePost;

  public DepthFirstOrder(Digraph G) {
    reversePost = new Stack<Integer>();
    marked = new boolean[G.V()];
    for (int v = 0; v <G.V(); v++) {
      if (!marked[v]) {
        dfs(G, v);
      }
    }
  }

  private void dfs(Digraph G, int v) {
    marked[v] = true;
    for (w: G.adj(v)) {
      if (!marked[w]) {
        dfs(G, w);
      }
    }
    reversePost.push(v);
  }

  // When you pop items out from the stack, the result will be the topological order
  public Iterable<Integer> reversePost() {
    return reversePost;
  }
}

Strong Components

Definition: vertices v and w are strongly connected if there is a directed path from v to w and a directed path from w to v
Strong connectivity is an equivalence relation
In a DAG, there are V strongly connected components, each component contains exactly one vertex
Strong components algorithm brief history
- 1960s: Core OR problem
- 1972: linear-time DFS algorithm(Tarjan)
- 1980s: easy two-pass linear-time algorithm(Kosaraju-Sharir)
- 1990s: more easy linear-time algorithms

Kosaraju-Sharir algorithm

Reverse graph: Strong components in G are same as in \(G^{R}\)
Kernel DAG: contract each strong component into a single vertex
Idea:
- Compute topological order(reverse postorder) in \(G^{R}\)
- Run DFS in G, visiting unmarked vertices in reverse postorder of \(G^{R}\), categorize them in different groups
Preposition: Kosaraju-Sharir algorithm computes the strong components of a digraph in time proportional to \(E + V\)

Java implementation:

public class KosarajuSharirSCC {
  private boolean[] marked;
  private int[] id;
  private int count;

  public KosarajuSharirSCC(Digraph G) {
    marked = new boolean[G.V()];
    id = new int[G.V()];
    //  topological order on G.reverse
    DepthFirstOrder dfs = new DepthFirstOrder(G.reverse());
    for (int v: dfs.reversePost()) {
      if (!marked[v]) {
        dfs(G, v);
        count ++;
      }
    }
  }

  private void dfs(Digraph G, int v) {
    marked[v] = true;
    id[v] = count;
    for (int w: G.adj(v)) {
      if (!marked[w]) {
        dfs(G, w);
      }
    }
  }

  public boolean stronglyConnected(int v, int w) {
    return id[v] == id[w];
  }
}

Notice: the first step for finding topological order should be using DFS, the second step can be either DFS or BFS, any algorithm that marks the set of vertices reachable from a given vertex will do

Interview Questions:
- Hamiltonian path in a DAG: topological sort, if the sorted result is consecutive, then there is a hamiltonian path, if not, no hamiltonian path exists
- Reachable vertex from all other vertices in a DAG: the vertex with 0 outdegrees is the solution

Week 2

Minimum Spanning Trees

Introduction to MSTs
- Spanning tree: a spanning tree of an undirected graph G (connected, positive edge weights)is a subgraph T that is both a tree (connected and acyclic) and spanning (includes all of the vertices)
- Minimum spanning tree: a spanning tree with a min weight
Greedy algorithm
- When the graph is connected and edge weights are distinct, MST exists and is unique
- Cut property
  - Definition: a cut in a graph is a partition of its vertices into two nonempty sets
  - Definition: a crossing edge connects a vertex in one set with a vertex in the other set
  - Cut property: given any cut, the crossing edge of min weight is in the MST
- Greedy MST algorithm
  - Start with all edges colored gray
  - Find cut with no black crossing edges, color its min-weight edge black
  - Repeat until V - 1 edges are colored black
- Some implementations
  - Kruskal's algorithm
  - Prim's algorithm
  - Boruvka's algorithm
- When edge weights are not distinct, the greedy algorithm is still correct
- When the graph is not connected, we can calculate the minimum spanning forest, which is the MST for each component

Edge abstraction needed for weighted edges

Edge API

public class Edge implements Comparable<Edge> {
  private final int v, w;
  private final double weight;
  // create a weighted edge v-w
  Edge(int v, int w, double weight) {
    this.v = v;
    this.w = w;
    this.weight = weight;
  }
  // either endpoint
  int either() {
    return this.v;
  }
  // the other endpoint that's not v
  // get the two vertices: int v = e.either()' int w = e.other(v);
  int other(int vertex) {
    if (vertex == this.v) {
      return this.w;
    } else if (vertex == this.w) {
      return this.v;
    }
  }
  // compare this edge to that edge
  int compareTo(Edge that) {
    if (this.weight < that.weight) {
      return -1;
    } else if (this.weight > that.weight) {
      return 1;
    } else {
      return 0;
    }
  }
  // the weight
  double weight() {
    return this.weight;
  }
  // string representation
  String toString() {
    return String.format("%d-%d %.5f", v, w, weight);
  }
}

Edge-weighted graph API (allow self loops and parallel edges)

public class EdgeWeightedGraph {
  private final int V;
  private int E;
  private final Bag<Edge>[] adj;
  // create an empay graph with V vertices
  EdgeWeightedGraph(int V) {
    this.V = V;
    this.adj = (Bag<Edge>[]) new Bag[V];
    for (int v = 0; v < V; v++) {
      adj[v] = new Bag<Edge>();
    }
  }
  // create a graph from input stream
  EdgeWeightedGraph(In in) {
    this.V = in.readInt();
    this.adj = (Bag<Edge>[]) new Bag[V];
    for (int v = 0; v < V; v++) {
      adj[v] = new Bag<Edge>();
    }
  }
  // add weighted edge e to this graph
  void addEdge(Edge e) {
    int v = e.either();
    int w = e.other(v);
    this.adj[v].add(e);
    this.adj[w].add(e);
    this.E++;
  }
  // edges incident to v
  Iterable<Edge> adj(int v) {
    return this.adj[v];
  }
  // all edges in the graph
  Iterable<Edge> edges() {
      Bag<Edge> list = new Bag<Edge>();
      for (int v = 0; v < V; v++) {
          int selfLoops = 0;
          for (Edge e : adj(v)) {
              if (e.other(v) > v) {
                list.add(e);
              } else if (e.other(v) == v) {
                  // add only one copy of each self loop 
                  if (selfLoops % 2 == 0) list.add(e);
                  selfLoops++;
              }
          }
      }
      return list;
  }
  // number of vertices
  int V() {
    return this.V;
  }
  // number of edges
  int E() {
    return this.E;
  }
  // string representation
  String toString()
}

MST API

public class MST {
  // MST constructor
  MST(EdgeWeightedGraph G)
  // iterator of MST edges
  Iterable<Edge> edges()
  // weight of MST
  double weight()
}

Kruskal's algorithm

Idea: sort edges in ascending order of weight, add next edge to tree T unless doing so would create a cycle
Challenge: would adding edge v-w to the tree T create a cycle
- Union find: maintain a set for each connected component in T, if v and w are in the same set, the adding v-w would create a cycle, if not, add v-w to T and merge sets containing v and w

Java implementation

public class KruskalMST {
  private Queue<Edge> mst;

  public KruskalMST(EdgeWeightedGraph G) {
    mst = new Queue<Edge>();
    MinPQ<Edge> pq = new MinPQ<Edge>(G.E());
    for (Edge e : G.edges()) {
      pq.insert(e);
    }
    UF uf = new UF(G.V());
    while (!pq.isEmpty() && mst.size() < G.V() - 1) {
      Edge e = pq.delMin();
      int v = e.either();
      int w = e.other(v);
      if (!uf.connected(v, w)) {
        uf.union(v, w);
        mst.enqueue(e);
      }
    }
  }

  public Iterable<Edge> edges() {
    return mst;
  }
}

Performance: \(O(ElogE)\) time complexity

Prim's algorithm

Idea: start with vertex 0 and greedily grow tree T, add to T the min weight edge with exactly one endpoint in T, repeat until V - 1 edges
Challenge: find the min weight edge with exactly one endpoint in T
- Lazy solution:
  - Maintain a PQ of edges with one endpoint in T
  - The key in the PQ is the edge, the priority is its weight
  - Extract min to determine next edge e = v-w to add to T
  - If both v and w are in T, discard edge e
  - Otherwise, let w be the vertex not in T, add to PQ all edges incident to w, add e to T
- Eager solution
  - Maintain a PQ of vertices connected by an edge to T, where priority of vertex v is the weight of shortest edge connecting v to T
  - Extract the min vertex v and add its associated edge e = v-w to T
  - Update PQ by considering all edges e = v-x incident to v, if x is already in T, decrease the priority of x if e is a shorter path to x, add to PQ if x is not in T

Java implementation of lazy Prim's algorithm

public class LazyPrimMST {
  private boolean[] marked;
  private Queue<Edge> mst;
  private MinPQ<Edge> pq;

  public LazyPrimMST(WeightedGraph G) {
    pq = new MinPQ<Edge>();
    mst = new Queue<Edge>();
    marked = new boolean[G.V()];
    visit(G, 0);

    while (!pq.isEmpty()) {
      Edge e = pq.delMin();
      int v = e.either();
      int w = e.other(v);
      if (marked[v] && marked[w]) continue;
      mst.enqueue(e);
      if (!marked[v]) visit(G, v);
      if (!marked[w]) visit(G, w);
    }
  }

  private void visit(WeightedGraph G, int v) {
    marked[v] = true;
    for (Edge e : G.adj(v)) {
      if (!marked[e.other(v)]) {
        pq.insert(e);
      }
    }
  }

  public Iterable<Edge> mst() {
    return mst;
  }
}

Performance: \(O(ElogE)\) time complexity

Java implementation of eager Prim's algorithm

public class PrimMST {
  private Edge[] edgeTo;        
  private double[] distTo;      
  private boolean[] marked;     
  private IndexMinPQ<Double> pq; 

  public PrimMST(EdgeWeightedGraph G) {
      edgeTo = new Edge[G.V()];
      distTo = new double[G.V()];
      marked = new boolean[G.V()];
      pq = new IndexMinPQ<Double>(G.V());
      for (int v = 0; v < G.V(); v++) {
          distTo[v] = Double.POSITIVE_INFINITY;
      }
      for (int v = 0; v < G.V(); v++) {
          if (!marked[v])  {
            prim(G, v);
          }
      }   
  }

  private void prim(EdgeWeightedGraph G, int s) {
      distTo[s] = 0.0;
      pq.insert(s, distTo[s]);
      while (!pq.isEmpty()) {
          int v = pq.delMin();
          scan(G, v);
      }
  }

  private void scan(EdgeWeightedGraph G, int v) {
    marked[v] = true;
    for (Edge e : G.adj(v)) {
        int w = e.other(v);
        if (marked[w]) continue;        
        if (e.weight() < distTo[w]) {
            distTo[w] = e.weight();
            edgeTo[w] = e;
            if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
            else                pq.insert(w, distTo[w]);
        }
    }
  }

  public Iterable<Edge> edges() {
      Queue<Edge> mst = new Queue<Edge>();
      for (int v = 0; v < edgeTo.length; v++) {
          Edge e = edgeTo[v];
          if (e != null) {
              mst.enqueue(e);
          }
      }
      return mst;
  }
}

Performance: \(O(ElogV)\)

MST context
- Does a linear-time MST algorithm exist?
- Euclidean MST: given N points in the plane, find MST connecting them, where the distances between point pairs are their Euclidean distances
- Scientific application: clustering

Shortest Paths

Shortest Path API

Idea: given an edge-weighted digraph, find shortest path from s to t
Which vertices
- Source-sink: from one vertex to another
- Single source: from one vertex to all others
- All pairs: between all pairs of vertices
Restriction on edge weights
- Nonnegative weights
- Arbitrary weights
- Euclidean weights
Does the graph have cycles
- No directed cycles
- No negative cycles

Edge-weighted digraph API

DirectedEdge

public class DirectedEdge {
  private final int v, w;
  private final double weight;

  public DirectedEdge (int v, int w, double weight) {
    this.v = v;
    this.w = w;
    this.weight = weight;
  }

  public int from() {
    return this.v;
  }

  public int to() {
    return this.w;
  }

  public double weight() {
    return this.weight;
  }
}

Edge-weighted digraph API

public class EdgeWeightedDigraph {
  private final int V;
  private final Bag<DirectedEdge>[] adj;

  public EdgeWeightedDigraph(int V) {
    this.V = V;
    this.adj = (Bag<DirectedEdge>[]) new Bag[V];
    for (int v = 0; v < V; v++) {
      this.adj[v] = new Bag<DirectedEdge>();
    }
  }

  public void addEdge(DirectedEdge e) {
    int v = e.from();
    this.adj[v].add(e);
  }

  public Iterable<DirectedEdge> adj(int v) {
    return this.adj[v];
  }
}

Shortest Path Property

Goal: single source shortest path problem

A shortest path tree (SPT) exists

Use dist[v] to get the shortest path from source s to vertex v

Use edgeTo[v] and a stack to get the vertexes on the shortest path from s to v

public Iterable<DirectedEdge> pathTo(int v) {

  Stack<DirectedEdge> path = new Stack<DirectedEdge>();
  for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
    path.push(e);
  }
  return path;
}

Use edge relaxation to update shortest path

private void relax(DirectedEdge e) {
  int v = e.from();
  int w = e.to();
  if (distTo[w] > distTo[v] + e.weight()) {
    distTo[w] = distTo[v] + e.weight();
    edgeTo[w] = e;
  }
}

Shortest path optimality condition: Let G be an edge-weighted digraph, then distTo[] are the shortest path distances from s iff:
- distTo[s] = 0
- For each vertex v, distTo[v] is the length of some path from s to v
- For each edge e = w\(\rightarrow\)w, distTo[w] <= distTo[v] + e.weight()
Generic algorithm to compute SPT from s
- Idea
  - Initialize distTo[s] = 0 and distTo[v]=\(\infty\) for all other vertices
  - Repeat relaxing edges until the optimality conditions are satisfied
- Efficient implementation
  - Dijkstra's algorithm: non-negative weights
  - Topological sort algorithm: no directed cycles
  - Bellman-Ford algorithm: no negative cycles

Dijkstra's algorithm

Idea: consider vertices in increasing order of distance from s, add vertex to tree and relax all edges pointing from that vertex
Proposition: Dijkstra's algorithm computes a SPT in any edge-weighted digraph with nonnegative weights

Java implementation

public class DijkstraSP {
  private DirectedEdge[] edgeTo;
  private double[] distTo;
  private IndexMinPQ<Double> pq;

  public DijkstraSP(EdgeWeightedDigraph G, int s) {
    this.edgeTo = new DirectedEdge[G.V()];
    this.distTo = new double[G.V()];
    this.pq = new IndexMinPQ<Double>(G.V());
    for (int v = 0; v < G.V(); v++) {
      this.distTo[v] = Double.POSITIVE_INFINITY;
    }
    this.distTo[s] = 0.0;
    pq.insert(s, this.distTo[s]);
    while (!pq.isEmpty()) {
      int v = pq.delMin();
      for (DirectedEdge e : G.adj(v)) {
        relax(e);
      }
    }
  }

  private void relax(WeightedEdge e) {
    int v = e.from();
    int w = e.to();
    if (this.distTo[w] > this.distTo[v] + e.weight()) {
      this.distTo[w] = this.distTo[v] + e.weight();
      this.edgeTo[w] = e;
      if (this.pq.contains(w)) this.pq.decreaseKey(w, this.distTo[w]);
      else this.pq.insert(w, this.distTo[w]);
    }
  }
}

Time complexity: \(O((V+E)logV)\)

Edge-weighted DAGs

Idea: consider vertices in topological order, relax all edges pointint from that vertex
The key point is that topological sort works with even negative weights
Proposition: topological sort algorithm computes SPT in any edge-weighted DAG with time complexity of \(O(V + E)\)

Java implementation

public class AcyclicSP {
  private DirectedEdge[] edgeTo;
  private double[] distTo;

  public AcyclicSp(EdgeWeightedDigraph G, int s) {
    this.edgeTo = new DirectedEdge[G.V()];
    this.distTo = new double[G.V()];
    for (int v = 0; v < G.V(); v++) {
      this.distTo[v] = Double.POSITIVE_INFINITY;
    }
    this.distTo[s] = 0.0;
    Topological topological = new Topological(G);
    for (int v: topological.order()) {
      for (DirectedEdge e : G.adj(v)) {
        relax(e);
      }
    }
  }

  private void relax(WeightedEdge e) {
    int v = e.from();
    int w = e.to();
    if (this.distTo[w] > this.distTo[v] + e.weight()) {
      this.distTo[w] = this.distTo[v] + e.weight();
      this.edgeTo[w] = e;
      if (this.pq.contains(w)) this.pq.decreaseKey(w, this.distTo[w]);
      else this.pq.insert(w, this.distTo[w]);
    }
  }
}

Longest path in edge-weighted DAG
- Negate all weights
- Find shortest paths
- Negate weights in result

Negative weights

Dijkstra does not work with negative edge weights
Negative cycle: a negative cycle is a directed cycle whose sum of edge weights is negative
If there is a negative cycle, then there is no SPT

Bellman-Ford algorithm

Idea: initialize distTo[s] = 0 and distTo[v] = \(\infty\) for all other vertices, then repeat relaxing all edges for V times
Proposition: dynamic programming algorithm computes SPT in any edge-weighted digraph with no negative cycles with time complexity \(O(V * E)\)

Java implementation

public class BellmanFordSP {
  private double[] distTo;
  private DirectedEdge[] edgeTo;
  private boolean[] onQueue;
  private Queue<Integer> queue;
  private int cost;
  private Iterable<DirectedEdge> cycle;

  public BellmanFordSP(EdgeweightedDigraph G, int s) {
    this.distTo = new double[G.V()];
    this.edgeTo = new DirectedEdge[G.V()];
    this.onQueue = new boolean[G.V()];
    for (int v = 0; v < G.V(); v++) {
      this.distTo[v] = Double.POSITIVE_INFINITY;
    }
    this.distTo[s] = 0.0;
    this.queue = new Queue<Integer>();
    this.queue.enqueue(s);
    this.onQueue[s] = true;
    while (!queue.isEmpty() && !hasNegativeCycle()) {
      int v = queue.dequeue();
      this.onQueue[v] = false;
      relax(G, v);
    }
  }

  private void relax(EdgeWeightedDigraph G, int v) {
    for (DirectedEdge e : G.adj(v)) {
      int w = e.to();
      if (this.distTo[w] > this.distTo[v] + e.weight()) {
        this.distTo[w] = this.distTo[v] + e.weight();
        this.edgeTo[w] = e;
        if (!this.onQueue[w]) {
          this.queue.enqueue(w);
          this.onQueue[w] = true;
        }
      }
      if (++this.cost % G.V() == 0) {
        findNegativeCycle();
        if (hasNegativeCycle()) {
          return;
        }
      }
    }
  }

  public boolean hasNegativeCycle() {
    return this.cycle != null;
  }

  public Iterable<DirectedEdge> negativeCycle() {
    return this.cycle;
  }

  private void findNegativeCycle() {
    int V = this.edgeTo.length;
    EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
    for (int v = 0; v < V; v++) {
      if (this.edgeTo[v] != null) {
        spt.addEdge(this.edgeTo[v]);
      }
    }
    EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
    this.cycle = finder.cycle();
  }

  public Iterable<DirectedEdge> pathTo(int v) {
    if (hasNegativeCycle()) {
      throw new UnsupportedOperationException("Negative cost cycle exists");
    }
    if (!hasPathTo(v)){
      return null;
    }
    Stack<DirectedEdge> path = new Stack<DirectedEdge>();
    for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
        path.push(e);
    }
    return path;
  }
}

Performance comparison

Algorithm	Restriction	Time complexity	Extra space
Dijkstra (binary heap)	no negative weights, can have cycles	\(O((V + E)logV)\)	\(O(V)\)
Topological sort	no directed cycles, can have negative weights	\(O(V + E)\)	\(O(V)\)
Bellman-Ford	no negative cycles	\(O(V * E)\)	\(O(V)\)

My Blog

Princeton Algorithms Part Two Notes

Week 1

Week 2