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 our guided, illustrated walk-through.

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.