Amazon Interview Question
Country: United States
Do a DFS of directed graph. Maintain these attributed while doing DFS,
- previsit numbers for nodes
- postvisit numbers for nodes
- parent/ancestor information for nodes
Directed graph has cycles where DFS reveals back-edges. Back edges means when you have an edge (u,v) such that (pre,post) pair of u is contained in that of v.
Whenever you get a back edge, use parent information to back-trace the cycle.
You can generate the minimum spanning tree (MST) of the graph, which is rather simple with BFS. Any graph edges not in the MST is possible to introduce a cycle.
For each edge not in MST, let source_vertex be the source of the edge, and end_vertex be the end of the edge. If end_vertex is ancestor of source_vertex, then there is a loop between source_vertex and end_vertex. The loop can be identified by calling getParent() from source_vertex, until meet the end_vertex.
my earlier comment about MST is not right.
The following code is tested to work well.
public void printGraphCycles(Graph graph) {
HashSet<Vertex> visited = new HashSet<>();
HashSet<Vertex> candidates = new HashSet<>();
for(Vertex vertex : graph.vertexs()){
if(! visited.contains(vertex) && !candidates.contains(vertex))
DFS(graph, vertex, visited, candidates);
}
}
public void DFS(Graph graph, Vertex vertex, HashSet<Vertex> visited, HashSet<Vertex> candidates) {
/*
1 ---] 2
] /] \
| / | ]
| / | 3
| / | /
| [ | [
5 ----] 4
*/
candidates.add(vertex);
for(Vertex adj : graph.adj(vertex)) {
if(candidates.contains(adj)) {
// visited nodes may need to revisit to build the cycle
// so don't put visited.contains(adj) on the if condition.
// an example is node 4
// found cycle
printCycle(vertex, adj);
} else {
adj.setParent(vertex); // build the trace back
DFS(graph, adj, visited, candidates);
}
}
candidates.remove(vertex);
visited.add(vertex);
}
This can be done by doing a DFS of the directed graph where you maintain these attributes while doing the DFS:
- DevGuy February 19, 20141) Previsit numbers for nodes, the clock value when you are about to visit a node
2) Postvisit numbers for nodes, the clock value when you are leaving the node after it has been explored
3) Parent/Ancestor information. For every node, record its ancestor/parent as you do the DFS.
Directed graphs have the property that cycles are always found when DFS reveals a back-edge. A back-edge means that if you are looking at an edge (u,v) during traversal, you will see that (pre, post) pair for u is contained within (pre, post) pair of v.
Whenever you spot a back-edge during DFS, just use parent information to back-trace the cycle.