# AC Javascript solution with Vertex, inEdges, and BFS Topological Sort

1. Create Vertex class with id and 2 sets: inEdges & outEdges.

2. Build graph to store all vertices, and
|-> setup inEdges neighbors, and
|-> setup outEdges neighbors.

3. Run a BFS topological sort with inEdges.size === 0 order, return "" if the result.length !== graph size.

``````class Vertex {
constructor(c) {
this.id = c;
this.inEdges = new Set();
this.outEdges = new Set();
}
}

}
}

function alienOrder (words) {
if (words === null || words.length === 0) return "";

let graph = {};
let result = "";

for(let i = 0; i < words.length; i++){
let word = words[i];
// build graph
for(let j = 0; j < words[i].length; j++){
if (graph[word[j]] === undefined) graph[word[j]] = new Vertex(word[j]);
}
// setup in and out edges
if (i > 0) setNeighbors(words[i-1], words[i], graph);
}
// console.log(graph);
}

function setNeighbors(s, t, graph) {
for(let i = 0; i < Math.min(s.length, t.length); i++){
v1 = graph[s[i]];
v2 = graph[t[i]];
// setup in & out edges
if(v1.id !== v2.id){
break;
}
}
}

function topologicalSort(graph, result) {
let queue = [];
for (let key in graph) {
if (graph[key].inEdges.size === 0) queue.push(graph[key]);
}
while(queue.length !== 0) {
let curr = queue.shift();
result += curr.id;
for(let outEdge of curr.outEdges) {
graph[outEdge].inEdges.delete(curr.id);
if (graph[outEdge].inEdges.size === 0) queue.push(graph[outEdge]);
}
}
if(result.length !== Object.keys(graph).length) return "";
return result;
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.