Remarks: All the graphs here are without self loops and parallel edges, and anti
ID: 3715177 • Letter: R
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.
Question 1: Give an algorithm that finds the minimum size cycle in a graph (DFS helps a lot).
Explanation / Answer
Solution
For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.
The pseudocode for DFS is shown below. In the init() function, notice that we run the DFS function on every node. This is because the graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the DFS algorithm on every node.
Complexity analysis
Assume that graph is connected. Depth-first search visits every vertex in the graph and checks every edge its edge. Therefore, DFS complexity is O(V + E). As it was mentioned before, if an adjacency matrix is used for a graph representation, then all edges, adjacent to a vertex can't be found efficiently, that results in O(V2)complexity.
Feel free to reach out regarding any queries . And please do rate the answer . Thank you .