## Google Interview Question

Software Developers**Country:**India

```
//BFS time complexity: O(V + E), space: O(V)
class Solution {
public static void main(String[] args) {
List<List<Integer>> adj = new ArrayList<List<Integer>>(9);
for (int i = 0; i < 9; i++) {
adj.add(new ArrayList<Integer>());
}
adj.get(4).add(5);
adj.get(5).add(6);
adj.get(5).add(7);
adj.get(7).add(6);
adj.get(7).add(8);
System.out.println(longestCycle(adj,4));
}
public static int longestCycle(List<List<Integer>> adj, int node) {
Deque<Integer> q = new LinkedList<Integer>();
boolean[] visited = new boolean[adj.size()];
int[] levels = new int[adj.size()];
levels[node] = 1;
q.addLast(node);
visited[node] = true;
while (!q.isEmpty()) {
int top = q.pollFirst();
for (Integer x: adj.get(top)) {
if (visited[x]) {
if (x == node) {
return levels[top];
}
} else {
levels[x] = levels[top] + 1;
q.addLast(x);
}
}
}
return -1;
}
}
```

```
public class DetectSmallestCycleInGraph {
private int shortestCycleSize = Integer.MAX_VALUE;
private Graph.Vertex[] shortestCycle;
Graph.Vertex[] findSmallestCycleDirectedGraph(Graph g) {
for(Graph.Vertex v :g.getVertices()) {//O(V)
Stack<Graph.Vertex> vertexStack = new Stack<>();
v.setVisited(false);//marking it unvisited so it can be traversed
boolean hasCycle = hasCycleDirectedGraph(v, vertexStack);
if(hasCycle) {
if(vertexStack.size() < shortestCycleSize){
shortestCycleSize = vertexStack.size();
shortestCycle = new Graph.Vertex[shortestCycleSize];
vertexStack.toArray(shortestCycle);
}
}
}
return shortestCycle;
}
boolean hasCycleDirectedGraph(Graph.Vertex source, Stack<Graph.Vertex> adjVertex) {
if(source.isVisited()) return false;
source.setVisited(true);
adjVertex.push(source);
for(Graph.Edge adj : source.getEdges()) {//O(A) , where A is adjacent edges to source
if(adj.getTo().isVisited() && adjVertex.contains(adj.getTo())) {//contains causes O(M) where M is the number of vertices on a path from the source node
return true;
} else if(!adj.getTo().isVisited() && hasCycleDirectedGraph(adj.getTo(), adjVertex)) {
return true;
}
}
adjVertex.pop();
return false;
}
public static void main(String[] args) {
int[][] edges = {
{0, 1},
{0, 2},
{2, 1},
{3, 0},
{1, 3},//shortest cycle
{1, 4},
{4, 5},
{5, 6},
{6, 7},
{7, 1}//cycle
};
Graph g = new Graph(edges);
DetectSmallestCycleInGraph da = new DetectSmallestCycleInGraph();
Graph.Vertex[] cycle = da.findSmallestCycleDirectedGraph(g);
System.out.println("\n Shortest cycle : ");
for (Graph.Vertex v : cycle) {
System.out.print(v.getId() + " -> ");
}
}
```

Small modification to BFS to measure distance between two graph nodes. The issue is they should be the same node so you are confident you find the shortest cycle.

- baites January 23, 2019