Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Detect An Undirected Graph Cycle (Main Thread)

Here is the interview question prompt, presented for reference.

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.

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

class Graph {
    constructor() {
        this.adjacencyList = new Map();
    }

    addVertex(nodeVal) {
        this.adjacencyList.set(nodeVal, []);
    }

    addEdge(src, dest) {
        this.adjacencyList.get(src).push(dest);
        this.adjacencyList.get(dest).push(src);
    }

    removeVertex(val) {
        if (this.adjacencyList.get(val)) {
            this.adjacencyList.delete(val);
        }

        this.adjacencyList.forEach((vertex) => {
            const neighborIdx = vertex.indexOf(val);
            if (neighborIdx >= 0) {
                vertex.splice(neighborIdx, 1);
            }
        });
    }

    removeEdge(src, dest) {
        const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);
        this.adjacencyList.get(src).splice(srcDestIdx, 1);

        const destSrcIdx = this.adjacencyList.get(dest).indexOf(src);
        this.adjacencyList.get(dest).splice(destSrcIdx, 1);
    }
}

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|)

You can see the full challenge with visuals at this link.

Challenges • Asked over 6 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Detect An Undirected Graph Cycle.