CS29003 Algorithms Laboratory
Assignment 98: Application of Graph traversals
General instruction to be followed strictly
1. Do not use any global variable unless you are explicitly instructed so.
2. Do not use Standard Template Library (STL) of C++.
3. Use proper indentation in your code and comment.
4. Name your file as <roll_no>_<assignment_no>. For example, if your roll number is 14CS10001
and you are submitting assignment 3, then name your file as 14CS10001_3.c or 14CS10001_3.cpp
as applicable.
5. Write your name, roll number, and assignment number at the beginning of your program.
6. Make your program as efficient as possible. Follow best practices of programming.
Let G = (V, E) be a weighted, undirected, acyclic, connected graph with weight function w : V −→
Z. Let n be the number of vertices in G. Observe that such a graph has exactly n − 1 edges. We are also
given a cost c : E −→ Z per edge. Since G is connected and acyclic, if we remove any edge e ∈ E from G,
we obtain two connected components, say H1e , H2e . We define the vulnerability (γe ) of any edge e ∈ E
as follows.
X X
γe = c(e) − w(x) − w(y)
x a vertex of H1e y a vertex of H2e
7 3
5
-5 2 6 8
3
5 Edge Vulnerability
4 28 {1, 2} −52
−4 {1, 4} −43
{1, 5} −50
12 1 {3, 4} −14
{3, 6} −26
5 -3
Figure 1: A graph and the vulnerability of its edges.
Vertices are labeled with {1, 2, . . . , n}. Figure 1 exhibits an example of a graph and the vulnerabilities
of its edges. In this assignment, you write a C/C++ function to find an edge having the highest
1
vulnerability. If there are more than one edge having the highest vulnerability, output any one of
them. Represent the graph with an adjacency list.
Part I: Brute-force O(n2 )-Time Algorithm
In this part, you implement the following algorithm. For each edge e ∈ E, you remove the edge from
the graph, obtain the two connected components H1e and H2e , compute the sum of the weights of the
vertices in each H1e and H2e , and compute γ(e). Finally output an edge e with the smallest γ(e).
Part II: Linear Time Algorithm
Design an O(n)-time algorithm for this problem. Hint: use DFS (you are welcome to use any other ap-
proach)!
main()
1. Read n from the user.
2. Read the weights of these n vertices.
3. Read the edges along with its weight.
4. Dynamically allocate space to store the graph in the adjacency list format using malloc/calloc/new
5. Compute an edge with the smallest vulnerability using both the methods and output.
You assume that the given graph is weighted, undirected, acyclic, connected (no need to check this
in your code). An edge is denoted by an unordered pair of vertices whose order does not matter.
For example, when giving input, user can denote an edge as 2 3 or 3 2. You code should behave
identically in both the cases. Submit a single .c or .cpp file. Your code should get compiled properly by
gcc or g++ compiler.
Sample Output
Write n: 6
Write weights of vertices: 12 -5 7 28 -3 8
Write the edges and their weights
1 2 5
1 4 -4
1 5 3
3 4 3
3 6 5
Edge with the smallest vulnerability computed using first method: 3 4
Edge with the smallest vulnerability computed using second method: 3 4
