## Facebook Interview Question

Interns- 0of 0 votes
given a target node in a directed graph, find the shortest cycle including this node, return the whole path.

**Country:**United States

Let t the target node of directed graph G = (V, E). If t is in a cycle, then there is some vertex v such that there is an edge t -> v, and there is a directed path from v to t. So, for each such v, start a BFS to try to find the shortest path from v to t (if exists), return the minimum length path among them.

But it's possible to solve it with a single BFS, start the BFS as usual from t, that is, add t to the queue, but don't mark it as visited! mark each vertex as visited as they are discovered, and the first time you find t, you'll have the shortest cycle that contains t, keep a parent pointer structure so you can rebuild the path.

Straight forward BFS to find shortest path from s to s. Just ensure, the start node is not put into the visited nodes at first. Since there is no relaxation (unweighted graph) needed, the order of first discovery from BFS is as well the shortest path to that node. Store it's parent and don't care about rediscovery (as usually). If I get back to S, I have the shortest cycle.

Runtime is O(|V|+|E|), especially if there is no cycle, this might happen (e.g. if you

give me the root of a tree as start). Space is O(|V|).

The core of the algo is this code, assuming s is the given node:

```
unordered_map<Node*, Node*> parents;
deque<Node*> q{ 1, s };
while (!q.empty()) {
Node* u = q.back();
q.pop_back();
for (auto v : u->adjacents_) {
if (parents.count(v) > 0) continue;
parents[v] = u;
if (v == s) {
q.clear();
break;
} else {
q.push_front(v);
}
}
}
```

the whole solution is

```
#include <string>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <iostream>
using namespace std;
struct Node
{
string label_;
unordered_set<Node*> adjacents_;
Node(const string& label) : label_(label) {}
void link(Node* v) { adjacents_.insert(v); }
};
vector<Node*> shortest_cycle_path(Node* s)
{
unordered_map<Node*, Node*> parents;
deque<Node*> q{ 1, s };
while (!q.empty()) {
Node* u = q.back();
q.pop_back();
for (auto v : u->adjacents_) {
if (parents.count(v) > 0) continue;
parents[v] = u;
if (v == s) {
q.clear();
break;
} else {
q.push_front(v);
}
}
}
// recover path
vector<Node*> path;
auto current = s;
do {
path.push_back(current);
current = parents[current];
} while (current != nullptr && current != s);
if (current != nullptr) path.push_back(s);
if (path.size() == 1) path.clear(); // no cycle
reverse(path.begin(), path.end());
return path;
}
ostream& operator << (ostream& os, const vector<Node*>& v) {
os << "{";
bool first = true;
for (auto n : v) {
if (first) {
cout << n->label_;
first = false;
} else {
cout << "," << n->label_;
}
}
os << "}";
return os;
}
int main()
{
/*
/------(f)<- /--\
v ---/ \ v |
(a) / ----->(e)---/
| / / ^
vv | /
(b)-->(c)-->(d)-->(g)->(h)
\ ^
-------/
*/
Node a("a");
Node b("b");
Node c("c");
Node d("d");
Node e("e");
Node f("f");
Node g("g");
Node h("h");
a.link(&b);
b.link(&c);
c.link(&e);
c.link(&d);
d.link(&e);
e.link(&f);
e.link(&e);
f.link(&b);
f.link(&a);
d.link(&g);
d.link(&h);
g.link(&h);
cout << shortest_cycle_path(&b) << endl; // {b,c,e,f,b}
cout << shortest_cycle_path(&a) << endl; // {a,b,c,e,f,a}
cout << shortest_cycle_path(&e) << endl; // {e,e}
cout << shortest_cycle_path(&g) << endl; // {}
}
```

I would solve it as Follows.

Given the Node and Path class

```
class Node {
public int value;
public Node next;
public Node(int x) { value = x; next = null; }
}
class Path {
public ArrayList<Node> path;
public Path(ArrayList<Node> path){this.path = path;}
}
```

Since HashSet has O(1) for insertion and search we will use this for determining whether a node has been visited by our algorithm. When we find the first node in our cycle(first time we find a previously visited node) we can create our path.

```
public Path getShortestCycle(Node a) {
Node current = a;
HashSet<Node> visited = new HashSet<>();
while(current.next != null) {
if(!visited.contians(current)) {
visited.add(current);
} else { // We have found the start node for the cycle!
return computePath(current);
}
current = current.next;
}
return null; // Could not find path
}
// Computes the cycle starting at node a
private Path computePath(Node a) {
Node start = a;
Node current = a;
ArrayList<Node> path = new ArrayList<Node>();
while(current != a && current.next != null) {
if(current.next = a) {
path.add(current);
path.add(a);
return new Path(path);
} else {
path.add(current);
}
current = current.next;
}
return null; // Could not find path.
}
```

Perform DFS with a stack that represents the simple path you're currently on.

If you visit a node that's already in the simple path, you ignore it.

When you reach a cycle, record it if its size is smaller than the current

smallest recorded cycle.

Another approach is to find the strongly connected components of the graph (or at least the sub-graph that is connected to the target node).

- vlchen91 November 13, 2017