Path. Sequence of vertices connected by edges.
Cycle. Path whose first and last vertices are the same.
Two vertices are connected if there is a path between them.
Some graph-processing problems
Challenge. Which of these problems are easy? difficult? intractable?
Depth-first search. Put unvisited vertices on a stack.
Breadth-first search. Put unvisited vertices on a queue.
Shortest path. Find path from s to t that uses fewest number of edges.
Algorithm.
Some definitions:
Diameter of a tree. Given a graph that is a tree (connected and acyclic), find the longest path, i.e., a pair of vertices v and w that are as far apart as possible. Your algorithm should run in linear time.
Center of a tree. Given a graph that is a tree (connected and acyclic), find a vertex such that its maximum distance from any other vertex is minimized.
Parallel edge detection. Devise a linear-time algorithm to count the parallel edges in a graph.
toString()
1 | In in = new In(args[0]); |
Adjacency-lists digraph representation
same as graph APIs. only difference is:
1 | public void addEdge(int v, int w) { |
Goal. Given a set of tasks to be completed with precedence constraints, in which order should we schedule the tasks?
DAG. Directed acyclic graph.
Topological sort. Redraw DAG so all edges point upwards.
A digraph has a topological order iff no directed cycle.
Reverse graph. Strong components in G are same as in G^R.
Kernel DAG. Contract each strong component into a single vertex.
Phases:
Java Implement(Strong components in a digraph (with two DFSs))