Undirected Graphs

Graph-processing challenges

1) Is a graph bipartite?

Solution: DFS

http://poj.org/problem?id=3041

2) Find a cycle. DFS

3) Euler tour. Is there a cycle that uses each edge exactly once? Answer: A connected graph is Eulerian iff all vertices have even degree.

4) Hamiltonian cycle. Find a cycle that visits every vertex exactly once. Intractable.

5) Graph isomorphism. Are two graphs identical except for vertex names? No one knows

6) Planarity. Lay out a graph in the plane without crossing edges? Linear-time DFS-based planarity algorithm by Tarjan.

Exercises

1 Nonrecursive depth-first search.

Implement depth-first search in an undirected graph without using recursion.

Use stack.

2 Diameter and center of a tree.Given a connected graph with no cycles

• Diameter: design a linear-time algorithm to find the longest simple path in the graph.
• Center: design a linear-time algorithm to find a vertex such that its maximum distance from any other vertex is minimized.

Diameter: divide and conquer.

Center: put root and all leaves into a queue, BFS.

3 Euler cycle. An Euler cycle in a graph is a cycle (not necessarily simple) that uses every edge in the graph exactly one.

• Show that a connected graph has an Euler cycle if and only if every vertex has even degree.
• Design a linear-time algorithm to determine whether a graph has an Euler cycle, and if so, find one.

Directed Graphs

https://algs4.cs.princeton.edu/42digraph/

DFS

• Reachability.
• Path finding.
• Topological sort.
• Directed cycle detection.

Basis for solving difficult digraph problems:

• 2-satisfiability.
• Directed Euler path.
• Strongly-connected components.

Reachability application:

• Mark: mark all reachable objects.
• Sweep: if object is unmarked, it is garbage (so add to free list).
• Memory cost: uses 1 extra mark bit per object (plus DFS stack).

BFS

BFS computs shortest paths from s to all other vertices in a digraph in time poroportional to E + V.

Multiple-source shortest paths.

• Given a digraph and a set of source vertices, find shortest path from any vertex in the set to each other vertex.
• Use BFS, but initialize by enqueuing all source vertices.

Cycle detection: BFS is reasonable only if the graph is undirected.

Topological sort

DAG. Directed acyclic graph.

Topological sort. Redraw DAG so all edges point upwards.

1. Run depth-first search.
2. Return vertices in reverse postorder.
   1. reverse postorder: put a node in the stack after all its neighbours have been processed.

A digraph has a topological order iff no directed cycle.

Given a digraph, fina a directed cycle.

• DFS. See text book for other solutions.

*** If use DFS, needs to perform cycle detection first, then do reverse postorder DFS

*** If use BFS, add node into the queue ONLY IF indegree is 0. BFS can be used to detect cycles

Strongly-connected Components

Def. Vertices v and w are strongly connected if there is both a directed path from v to w and a directed path from w to v.

Key property. Strong connectivity is an equivalence relation:

• v is strongly connected to v.
• If v is strongly connected to w, then w is strongly connected to v.
• If v is strongly connected to w and w to x, then v is strongly connected to x.

Kosaraju-Sharir algorithm

Intuition

• Strong components in G are same as in G_r

• Kernel DAG. Contract each strong component into a single vertex.

• Compute reverse postorder in G_r

• Run DFS in G, visiting unmarked vertices in reverse postorder of G_r

  1. If there is no edge pointing from one to the next in the order, they are in different strong components.

Related problems:

• In a directed graph, find minimum number of points that can traverse to all vertices in the graph

• http://poj.org/problem?id=2186

Summary

Exercises

1 Shortest directed cycle.

Given a digraph G, design an efficient algorithm to find a directed cycle with the minimum number of edges (or report that the graph is acyclic). The running time of your algorithm should be at most proportional to V(E+V)and use space proportional to E+V, where V is the number of vertices and E is the number of edges.

2 Hamiltonian path in a DAG.

Given a directed acyclic graph, design a linear-time algorithm to determine whether it has a Hamiltonian path (a simple path that visits every vertex), and if so, find one.

Solution: Compute a topological sort and check if there is an edge between each consecutive pair of vertices in the topological order.

3 Reachable vertex.

1) DAG: Design a linear-time algorithm to determine whether a DAG has a vertex that is reachable from every other vertex, and if so, find one.

Solution: Compute the outdegree of each vertex.If the DAG exactly one vertex v with outdegree 0, then it is reachable from every other vertex. i.e. the last node in the topological order

2) Digraph: Design a linear-time algorithm to determine whether a digraph has a vertex that is reachable from every other vertex, and if so, find one.

Solution: Compute the strong components and kernel DAG,