TOTAL POINTS 3
Implement depth-first search in an undirected graph without using recursion
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.
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.
TOTAL POINTS 3
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.
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.
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.
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.