The course is the second part of a two-part course that is based on a variety of material that we have prepared over many years:
- Our textbook Algorithms, 4th edition is the basic reference for the material we will be covering. Although the lectures are designed to be self-contained, we will assign optional readings for students who wish more extensive coverage of the material. You can purchase the textbook in either hardcover or electronic format from amazon.com.
- Our booksite, which is open to everyone and contains a wealth of supplementary information, including synopses of the textbook and Java code that you will be using throughout the course.
References:
We begin our exploration of advanced algorithms by looking at data structures for graphs, which are essential models for a broad variety of real-world problems. A number of classic algorithms are easy to implement, but worthy of careful study both because convincing oneself that they operate as intended can be a challenge and because their performance is strongly dependent on proper use of the basic data structures that we covered in Algorithms Part I.
We define an undirected graph API and consider the adjacency-matrix and adjacency-lists representations. We introduce two classic algorithms for searching a graph—depth-first search and breadth-first search. We also consider the problem of computing connected components and conclude with related problems and applications.
- Reasons to study graphs -- countless applications in scientific, business and other (games!) applications
- Problems -- shortest path, is_there_cycle, Euler_path, Hamilton_path (TSP) , connectivity, biconnectivity, MST, planarity, graph isomorphism
- Graph representation and API -- adjacency matrix, adjacensy list; real-world graphs tend to be sparce
- Depth-First Search
- Put unvisited vertices on stack
- Marks all vertices connected to s in time proportinal to the sum of their degrees
- After DFS
- Can find all vertices connected to s in constant time
- Can find path to vertice s in time propertional to its length
- Breath-First Search
- Put unvisited vertices on queue
- Computes shortest path to s in time proportional to E + V
- Kevin Bacon graph
- Connected Component -- a maximal set of connected vertices
- Is-Connected-To is equivalence relations -- reflexive, symmetric and transitive
- Use DFS
- Graph-processing challenges
- Is a graph bipartite?
- Find a cycle
- Euler tour -- a cycle that uses each edge exactly once
- Hamilton cycle -- visits each vertex exactly once, Travelling Salesman Problem, NP-complete
- Are two graphs identical except to vertex names (who knows)
- Lay out a graph in a plane w/o crossing edges
In this lecture we study directed graphs. We begin with depth-first search and breadth-first search in digraphs and describe applications ranging from garbage collection to web crawling. Next, we introduce a depth-first search based algorithm for computing the topological order of an acyclic digraph. Finally, we implement the Kosaraju-Sharir algorithm for computing the strong components of a digraph.
- Digraph problems
- Find path from s to t, what is the shortest path
- Topological sort -- can you draw a digraph so that all edges point upwards
- Strong connectivity -- is the 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
- Graph representation and API -- vertex-indexes array of adjacency-lists
- Depth-First Search is exaclty the same
- Every program is a digraph, dead-code elimination, infinite-loop detection
- Mark-sweep garbage collection algorithm
- Breath-First Search is exaclty the same
- Computes shortest path to all other vertices in time proportional to E + V
- Multiple-source shortest paths
- Web crowler
- Topologocal Sort
- Given a set of tasks to be completed with precedence constraints, in what order should the tasks be executed
- If observed as DAG -- redraw DAG so all edges point upwards
- Solution -- Traverse the graph in DFS, return vertices in reverse postorder; there must be no cycle
- Stringly-connected Components -- a maximal subset of strongly connected vertices
- Vertices v and w are strongly connected if there is a directed path from v to w and from w to v
- Strong connectivity is an equivalence relation
- Strong components in G are same as in G-reverse
- Kosaraju-Sharir 2-phase algorithm
- Compute reverse postorder in G-reverse
- Run DFS in G, visiting unmarked vertices in reverse postorder of G-reverse
- Computes strong components in time proportional to E + V