CODEWITHSUNDEEP
graphdepth-first-search
Roman Roman
Roman Roman

Reputation: 917

Why Depth First Search checks vertices this way?

I'm learning graphs and have encountered such implementation of Depth First Search algorithm that finds cycles in a graph

Why should we check that w !== u. In which case can w === u ?

dfs(v, u) {
    this._marked[v] = true;

    const adj = this._graph.adj(v);

    for (const w of adj) {
        if (!this._marked[w]) {
            this.dfs(w, v);
        } else if (w !== u) {
            this.hasCycle = true;
        }
    }   
}

Upvotes: 0

Views: 18

Answers (1)

mirzanahal
mirzanahal

Reputation: 167

It seems that your algorithm is for undirected graphs and u is the parent of v. When you call this._graph.adj(v) it returns all adjacent including the parent u. The Condition w !== u check whether you have visited a node twice, it means you have two different paths to the node from your root. This means a cycle. But in the case that u is the parent node you are counting the edge E(u,v) twice which is not a definition for a cycle.

Upvotes: 1

Related Questions