Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3

Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3.

Give o(v^3) algorithm for it.

Solution:

step 1: Run DFS on the given as  it is.

step 2: In the DFS-visit of vertice ( say u ) run a modified BFS ( say BFS2).

The algorithm for BFS2 is as following:

BFS2(u) {

foreach v1 belongs to adj[u]

foreach v2 belongs to [adj[v1] - u] { // because we know u must be adjacent of v1. that's why we will not let u create massacre here.

if ( v2 and u are adjacent to each other )

Report ( u,v1,v2) as a cycle or length 3 .

}

}

This problem appears in algorithm design manual by skiena as following

5-17. Consider the problem of determining whether a given undirected graph G = (V,E) contains a triangleor cycle of length 3.

1. Give an O( | V | ³) to find a triangle if one exists.

The complexity id v3 because for each vertices BFS2 will run for with v^2 complexity.

Advertisement