Mark As Completed Discussion

Good morning! Here's our prompt for today.

Can you detect a cycle in an undirected graph? Recall that an undirected graph is one where the edges are bidirectional. A cycle is one where there is a closed path, that is, the first and last graph vertices can be the same.

Description

We've covered how to detect a cycle using depth-first search, but can you find one without it? Assume the following graph definition:

JAVASCRIPT
1class Graph {
2	constructor() {
3		this.adjacencyList = new Map();
4	}
5
6	addVertex(nodeVal) {
7		this.adjacencyList.set(nodeVal, []);
8	}
9
10	addEdge(src, dest) {
11		this.adjacencyList.get(src).push(dest);
12		this.adjacencyList.get(dest).push(src);
13	}
14
15	removeVertex(val) {
16		if (this.adjacencyList.get(val)) {
17			this.adjacencyList.delete(val);
18		}
19
20		this.adjacencyList.forEach((vertex) => {
21			const neighborIdx = vertex.indexOf(val);
22			if (neighborIdx >= 0) {
23				vertex.splice(neighborIdx, 1);
24			}
25		});
26	}
27
28	removeEdge(src, dest) {
29		const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);
30		this.adjacencyList.get(src).splice(srcDestIdx, 1);
31
32		const destSrcIdx = this.adjacencyList.get(dest).indexOf(src);
33		this.adjacencyList.get(dest).splice(destSrcIdx, 1);
34	}
35}

Constraints

  • The number of vertices in the graph <= 100000
  • The number of edges in the graph <= 100000
  • Let |V|, |E| represent the number of vertices and edges of the graph
  • Expected time complexity : O(|V|+|E|)
  • Expected space complexity : O(|V|)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's how we would solve this problem...

How do I use this guide?