Skip to content

Instantly share code, notes, and snippets.

@josh-stevens
Created April 3, 2019 20:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save josh-stevens/17a2bfa93bc8a3188831be5d6641fb76 to your computer and use it in GitHub Desktop.
Save josh-stevens/17a2bfa93bc8a3188831be5d6641fb76 to your computer and use it in GitHub Desktop.
Simple graph
class Graph {
constructor(numberOfVertices) {
this.size = numberOfVertices;
this.list = new Map();
}
addVertex(v) {
this.list.set(v, []);
}
addEdge(v, w) {
this.list.get(v).push(w);
this.list.get(w).push(v);
}
printGraph() {
const keys = this.list.keys();
for (let k of keys) {
const values = this.list.get(k);
let str = "";
for (let v of values) {
str += v + " ";
}
console.log(k, " -> ", str);
}
}
bfs(v) {
const visited = {};
const q = [];
visited[v] = true;
q.push(v);
while(q.length) {
const current = q.shift();
console.log(current);
const adjacent = this.list.get(current);
for (let v in adjacent) {
const neighbor = adjacent[v];
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
dfs(v) {
const visited = {};
this.depthSearch(v, visited);
}
depthSearch(current, visited) {
visited[current] = true;
console.log(current);
const adjacent = this.list.get(current);
for (let v in adjacent) {
const neighbor = adjacent[v];
if (!visited[neighbor]) {
this.depthSearch(neighbor, visited);
}
}
}
}
const g = new Graph(6);
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
g.dfs('A');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment