Karger's Algorithm (Min Cut)

[thakurdiwakar]

Is your feature request related to a problem? Please describe. Karger's Algorithm (Min Cut) :

Karger's algorithm is a randomized algorithm used to find the minimum cut in a graph. The minimum cut of a graph is defined as the smallest number of edges that, if removed, would divide the graph into two disconnected components. Karger's algorithm is based on the concept of contraction, where two randomly chosen vertices are merged into a single vertex, reducing the size of the graph. The algorithm repeats this contraction step until only two vertices (representing the two sides of the cut) remain.

Describe the solution you'd like

I wanted to add the solution in C++ and Python. You can find about it more here

Approach- Initialize the graph G. Repeat until there are two vertices left: Choose a random edge e in G. Contract e, merging the two endpoints of e into a single vertex. The cut formed by the two remaining vertices is a minimum cut. The algorithm works by iteratively contracting randomly chosen edges until only two vertices remain. The cut formed by the two remaining vertices is then a minimum cut.

[thakurdiwakar]

Please Assign me this issue

[Kumar-laxmi]

Assigned! @thakurdiwakar : C++ & Python

[Soumya6Tiwari]

@Kumar-laxmi sir kindly assign me this issue under ssoc 23.I can code it using c++ and Java, please assign it to me as this would be my first PR.

[github-actions[bot]]

This issue has been automatically closed because it has been inactive for many days. Please reopen if you still intend on working on this problem