220 questions
-1
votes
1
answer
100
views
Kruskal's Algorithm Minimum Spanning Tree (Disjoint Set data structure)
I would like to generate a minimum spanning tree for the following graph:
I am using the disjoint set data structure and I am having trouble with the union (Union Rank) operation.
The edges get ...
-2
votes
1
answer
88
views
When should I not use Prims' and Kruskal algorithm?
I am very confused about when should I not use this algorithm.
I thought kruskal was used to find the shortest path however i came to know that it is not used to find the shortest path instead Minimum ...
1
vote
0
answers
88
views
Optimize implementation of Kruskal's algorithm
I am doing this assignment, https://open.kattis.com/problems/borg?editresubmit=14545391, and my code solves the problem. I've researched other peoples solutions and it seems like I do what other ...
- 11
1
vote
2
answers
95
views
Kruskal's algorithm including a specific edge
I'm trying to solve the following question in which I have to find a list of critical edges and pseudocritical edges. From my understanding of the problem, critical edges are edges that must be ...
- 225
0
votes
3
answers
118
views
Problem removing from Java-HashSet while implementing Kruskal's algorithm
in the following code I am trying to implement Kruskal's algorithm to compute the minimal spanning tree of a graph.
The problem is that removing sets from the connected components does not work ...
- 131
0
votes
0
answers
48
views
Finding minimum spanning tree with Kruskal's, but there are overlap vertex
I tried to find minimum spanning tree with given graph (as adjacency list), priority queue and union-find method (with kruskal).
But there are two differences with my desired output :
First, The ...
- 133
1
vote
0
answers
55
views
In Kruskal's Algorithm, why does the union procedure check whether r_x == r_y since the opposite was required to call union()?
In Algorithms [DPV] Section 5.1.3, the authors outlined Kruskal's Algorithm. In the algorithm itself, while iterating through all edges on the graph, they compare whether find(u) != find(v). If so, ...
- 189
2
votes
2
answers
52
views
Operating on a pair of elements in an array and dropping one
There is a class of questions, that requires us to randomly select two elements from a given array, perform an operation on those elements, add the result to an "answer" and then drop any ...
- 51
0
votes
0
answers
174
views
DFS vs. Kruskal runtime (maze generation)
I have written two algorithms for creating unique mazes, one of them using depth-first-search (DFS) and the other using Kruskal's. The DFS algorithm performs as expected, however Kruskal's algorithm ...
- 11
-1
votes
1
answer
148
views
how to program Prim's and Kruskal's algorithm using adjacency lists in C
I have understood and implemented Prim's and Kruskal's algorithm using adjacency matrix but I am not understanding how to write a program using adjacency lists
I tried creating 2 matrices one for min ...
0
votes
0
answers
201
views
In openMP is there a way to for tasks to share variables?
In my experience, when I update a varible in 1 task the variable is not updated in other tasks even if the first task that updated the variable is done executing. For example given the code,
int ...
0
votes
1
answer
63
views
What is the logic behind this index in Kruskal's minimum spanning tree algorithm?
I don't understand why we are increasing e += 1 when the parents are not same. And why the while loop stops based on e's value? Why we need that index?
def kruskal(self):
i, e = 0, 0
ds = dst....
- 123
2
votes
1
answer
80
views
qsort not sorting the content correctly, kruskal's algorithm
I am trying to sort an array of structs using qsort, but it's not properly sorting the content.
The structure node consists of the starting vertex, the ending vertex, and the cost of reaching from ...
- 31
0
votes
0
answers
145
views
Does Kruskal's algorithm find the minimum bottleneck spanning tree? if so how do we prove correctness?
How would you prove Kruskal's algorithm always produces a minimum bottleneck spanning tree?
- 39
0
votes
1
answer
146
views
Kruskal algorithm, cycles and unvisited vertices
Algorithm does not pass through vertex 1(Z) and 4(B). Cycles are for vertices 12-13-14(S-T-K) and 13-15-16(T-L-R), how to fix it?
Below is the command, my code, graph, my output and the input file.
...
- 11