Remarks: All the graphs here are without self loops and parallel edges, and anti

Question

Remarks: All the graphs here are without self loops and parallel edges, and anti-parallel edges. When we speak of a flow network, we mean there are capacities c(e) ? 0 on the edges, the graph G is directed with a source s and a destination t. In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit.

• Question2: Given an undirected graph, give an algorithm that finds all edges in the graph that belong to at least one cycle.

Explanation / Answer

Algorithm:-

step-1:

use dfs from each element and track from stack.

here we push each unvisited node into stack.

step-2:

for each adjesent node to node which is visited and found in stack then cycle is found.

step-3:

now we extract cycle pathfrom stack like (1-2-3-1) path is element foumd index to last.

step-4:

now, we check edge involve in cycle means (1-2,2-3,3-1) is not visited then visit it. We can use 2-D boolean matrix for visited edge matrix.

step-5:

we repeat all above step with each unvisied node so that we found all cycle even if graph is unconnected.

sted-6:

count the number of edge involved.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects