Questions tagged [minimum-spanning-tree]
A minimum spanning tree (MST) or minimum weight spanning tree is a spanning tree of a connected, undirected graph with the least possible weight.
586
questions
0
votes
0
answers
22
views
How to analyze all traces in a graph analyzed with minimum spanning trees?
The Minimum Spanning Tree algorithm (MST) allows to find the shortest possible connexion for all nodes. In Python, Scipy provides a package to analyze MST. I want to find a way to get the main traces ...
0
votes
0
answers
16
views
Attribute Error for Prim's Algorithm implementation in Python
I've been struggling with the code used to implement Prim's Algorithm in Python. I really hope that someone help me as I needed this specific code for my Case Study. Thank you!
Here's the code:
# A ...
0
votes
0
answers
28
views
Finding the total weight in MST in Prim's Algorithm
currently I'm making a comparison between the Prim's Algorithm and Kruskal's Algorithm. Both codes are from GeeksforGeeks, however only the Kruskal's algorithm has the total calculated weight in ...
0
votes
1
answer
40
views
C# Prim's algorithm isn't generating maze correctly
I was trying to implement a C# version of the Java code given in this answer to generate a random maze, but my code doesn't quite generate the mazes correctly - it creates "isolated" wall ...
1
vote
1
answer
33
views
Why can't edges be fewer than vertices in Graph theory?
Upon analyzing Kruskal's Algorithm, Kruskal's Algorithm is apparently considered to be E log E because "for an MST to exist, E can't be smaller than V so assume it dominates"
However, the ...
0
votes
0
answers
16
views
How come this python object is updating its state when I didn't tell it to while making Prim's MST
To make it as simple as possible, I am trying to make Prim's algorithm in python from scratch. I am starting with this data structure:
{(0, 0): 0.0, (0, 1): 1.7729893, (0, 2): 2.0814261, (0, 3): 1....
0
votes
1
answer
120
views
Prim's algorithm using heap or unsorted array?
There's a question in my CS class asking that if the graph is a sparse graph, which is n^2 >> m, whether unsorted list with O(n^2) is more efficient than the binary heap O((m+n)logn). I'm a ...
0
votes
1
answer
91
views
Minimum cost to make connect all nodes in one partition of a weighted undirected bipartite graph
Given a weighted undirected bipartite graph between partition A and B, I'm trying to find the minimum cost to connect all nodes in partition A.
It seems like I need to first find a Minimum Spanning ...
0
votes
1
answer
34
views
True or False: For an undirected graph, for every vertex, its edge with minimum weight is in a minimum spanning tree
I think this is true. With consideration to Prim's algorithm, the minimum edge of a vertex is either already in a tree, or will be selected eventually.
I also tried a lot of graph and they all seem ...
2
votes
1
answer
212
views
Time complexity of Prim's MST algorithm problem
I have a graph problem where we have:
There are exactly n vertices and n-1 edges.
All vertices are connected with each other – i.e. the network consists of
just one connected component. The network ...
1
vote
1
answer
77
views
How can I find an MST from all trees containing a given edge?
In a weighted undirected graph, I need to modify Kruskal's algorithm to find the MST conditional to the fact that it includes a given edge 'e' in O(m log n) time. How can I do that?
0
votes
0
answers
26
views
A sub-optimal solution that does not guarantee that all MSTs are found in a reasonable time
The calculation of all MSTs of a graph is infeasible in practice. This is because the number of all MSTs has an upper bound of n power (n-2), where n is the number of nodes in the graph.
Therefore ...
0
votes
1
answer
52
views
Getting nodes without edges (When the N is larger than 60)
First I generated an NxN matrix of zeros and ones using NumPy. After that, I generated a copy matrix from the previous matrix, I replaced the ones in the first matrix with the weight of the edges. ( ...
0
votes
1
answer
92
views
How to convert a minimum spanning tree to a path/route in Java?
I have a minimum spanning tree in Java.
This is in a Graph class which has a list of Nodes, those Node classes have a list of Edge classes which have a boolean if they are in the MST or not.
Example:
...
0
votes
2
answers
53
views
How is a cut lonely if there are often multiple edges crossing a cut in a connected undirected graph?
I'm learning the requirements for finding a minimum spanning tree for a connected, undirected graph with distinct edge costs. One of the requirements is that there must be no cycles created in the ...
0
votes
0
answers
66
views
calculate the degree of all nodes for the MST and illustrate the values on the screen
I generated a random matrix of zeros and ones that is symmetric and
the diagonal == 0 after that I generated another matrix from the
the first matrix I made that contains the weights of the edges I ...
3
votes
1
answer
96
views
Give minimum permutation weight for edges such that a given set of edge is the Minimum Spanning Tree
Question:
Given a graph of N nodes and M edges, the edges are indexed from 1 -> M. It is guaranteed that there's a path between any 2 nodes.
You need to assign weights for M edges. The weights are ...
0
votes
0
answers
36
views
How to Find the Minimum and Maximum Weight Where Both Are as Close as Possible and Allow Travel Between Any Two Nodes
I have an undirected weighted graph and have to find the minimum and maximum weight, and both are as close as possible and allow travel between any two nodes.
I have tried everything. I found that ...
-1
votes
1
answer
20
views
Coding MST (4) in CPLEX
I'm trying to code MST4 in CPLEX, but because I'm new to code writing I have difficulty in doing it. I would really appreciate if anyone could help me.
Thanks
1
vote
1
answer
109
views
Find weight of MST in a complete graph of two weight with given edges
I need to get the MST of a complete graph where all edges are defaulted to weight 3, and I'm also given edges that have weight 1.
Here is an example
5 4 (N, M)
1 5
1 4
4 2
4 3
Resulting MST = 3 -> ...
0
votes
0
answers
125
views
making kruskal's algorithm in c (segmentation fault)
In this code I want to make Kruskal's algorithm, which calculates a minimum
spanning tree of a given graph. And I want to use min-heap and disjoint set at the code.
To make time complexity of O(e log ...
0
votes
0
answers
34
views
getting segmentation error on Kruskal algorithm for mst in gfg practice
vector<int> pr;
vector<int> sz;
vector<vector<int>> ans;
void mset(int u)
{
pr[u] = u ;
sz[u] = 1;
}
int fset(int u)
{
if(pr[u] == u)
return u;
...
0
votes
0
answers
42
views
Clustering validation and MST
I need your help to solve two problems related to spanning trees and clustering validation. One of the good technique to validate clustering is to use DBCV from https://github.com/christopherjenness/...
0
votes
0
answers
22
views
In a graph, is possible exist a MST with smaller-highest cost edge compare to another MST?
Given an undirected weighted graph, and assuming it has multiple MST, is it possible there is exist an MST with the lowest highest-cost edge compared with other MST?
For example, the highest cost edge ...
0
votes
1
answer
153
views
minimum spanning tree remove all extra edges
Extra edge- edge made with 2 points, where each point is connected with another edge.
I want to disconnect MST by deleting these edges.
What is the best approach to minimize the weight of new ...
0
votes
0
answers
135
views
MST from given list of coordinates
I want to know, what method should I use to construct a minimum spanning tree, given 1 million inputs (2d coordinates), so declaring 10^6 * 10^6 2d array for Prims is not an option, also, some values ...
0
votes
1
answer
117
views
Minimal trees around special nodes
I have a connected weighted undirected graph. The graph contains two types of nodes. Hub nodes and non-hub nodes.
What I would need is to grow a tree from each hub node to every non-hub node so that ...
0
votes
0
answers
29
views
Minimum spanning Tree for a large data set
Im fairly new to data mining, and I'm trying to plot a minimum spanning tree(MST) in python after reading the excel file. Im having a lot of errors, and would anyone have a solution for this type of ...
0
votes
0
answers
915
views
Time Complexity of (Minimum Spanning Tree) Prim's Algorithm
When we implement this algorithm using adjacency matrix and without using priority queue, the time complexity comes out to be O(V^2), where V is the total no. of vertices and E is the total no. of ...
1
vote
1
answer
116
views
Leetcode 1584. How can I improve my Kruskal&Union Find algorithm to make it faster?
The question was on Leetcode 1584. Min Cost to Connect All Points. My answer to this question is:
class Solution {
public int minCostConnectPoints(int[][] points) {
List<int[]> list =...
1
vote
0
answers
199
views
Duplicate Edge in Prim's Minimum Spanning tree
I've created a generic data structures and algorithm library written in C.
I've tried to implement Minimum Spanning tree using the Prim's Algorithm
When I run the code for a bi directional graph, I ...
4
votes
1
answer
138
views
Minimum spanning tree for pairs of adjacent edges
For some graph, there is a cost associated with each pair of adjacent edges. I hope to find a subgraph such that every point is connected and the cost is minimised (a minimum spanning tree).
For the ...
0
votes
1
answer
523
views
Implementing Union-Find Algorithm for Kruskal's Algorithm to find Minimum Spanning Tree in Java
I am trying to solve the following Leetcode problem (https://leetcode.com/problems/connecting-cities-with-minimum-cost), and my approach is to figure out the total weight of the minimum spanning tree (...
1
vote
1
answer
117
views
R iGraph - how to color edges used in minimum spanning tree
I would like to plot the solution of the minimum spanning tree(MST) by coloring the edges used in the solution.
library("igraph")
A = matrix(c(0, 23, 11, 5, 26, 22,23, 0, 9, 13, 30, 18,11, 9,...
2
votes
1
answer
234
views
Difference between prims and boruvka's Algorithm
I am studying about MST algorithms. I am curious to find the key differences between prims and boruvka's algorithm but the resources online don't have much to say about them other than their ...
1
vote
1
answer
63
views
A question about performing the next step in Boruvka's Algorithm
I have a question about implementing Boruvka's algorithm for Minimum-Spanning-Trees.
Assume we have the following graph:
It is fairly simple and clear to me how to find the smallest connection/edge ...
0
votes
0
answers
20
views
Update the weight of Minimum Spanning Tree (MST) after adding edges (not 1 edge only)
Given a weighted, undirected graph G = (V,0) and E edges connect 2 vertices of G. Add the i-th egde to the graph G, called G_i, respectively (G_(i+1) is G_i added (i+1)-th edge). Check that G_i has ...
0
votes
0
answers
40
views
MST_Kruskal algorithm C++
I find the algorithm below, but I didn't understand how that works and what edges class must contain. Please if anyone can understand it tell me a description:
void MST_Kruskal(edges edge[], map<...
1
vote
1
answer
38
views
How to create a SimpleWeightedGraph<Node, DefaultEdge> from SpanningTree<DefaultEdge>
I used KruskalMinimumSpanningTree so I can use the getSpanningTree() method.
The method returns a SpanningTree only containing edges (no more nodes). For my export Function I need a graph though...
Is ...
0
votes
1
answer
61
views
Loop for minimum spanning tree does not work
we as 3 friends try to solve minimum spanning tree with coflicts problem using r. In solving this question, we read files in .txt format that contain for ex.
"1 2 5
2 4 6" etc. which ...
1
vote
1
answer
266
views
Find minimum-weight set of edges to remove that will make a graph acyclic
Given a positively-weighted, undirected cyclic graph, how can I find the smallest set of edges to remove that will make the graph acyclic? The algorithm must run in O((E+V)logV) time.
I attempted to ...
2
votes
1
answer
285
views
Modified Minimum Spanning Tree
I have to implement an algorithm where we have an existing road network (nodes connected by path ie., undirected graph). We have to connect all the cities together, and normally I would use something ...
1
vote
2
answers
237
views
Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)
We have an algorithm problem in hand, can you please write your ideas about this, thank you!
There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
0
votes
0
answers
139
views
Finding Minimum Spanning Tree in O(V+E) when edges have limited values
If I have an undirected graph with the edges being only values of 1 or 2, could I find the minimum spanning tree in O(V+E) complexity?
-1
votes
2
answers
115
views
Create N-Clusters out of Min spanning tree?
Let say I created a Minimum Spanning Tree out of Graph with M nodes. Is there an algorithm to create N number of clusters.
I'm looking to cut some of the links such as that I end up with N clusters ...
1
vote
1
answer
199
views
Finding Minimum Spanning Tree (MST) in graph?
Given an Undirected graph G with with weight on its edges and 2 different minimal spanning trees: T, T'
Then I want to prove the following:
For every edge e in T that's not in T', there is an edge e' ...
0
votes
0
answers
65
views
Minimum spanning trees of sub-graphs?
Any hint please if I should prove or search for counterexample, at least to know which direction to go...
Consider the following 2 graphs:
G1 (V, E1)
G2 (V, E2)
and a weight function for the vertices ...
0
votes
0
answers
101
views
Prim Algorithm application
everyone, I have a weighted connected undirected graph, I need to find it's minimum spanning tree weight. On input I have numbers n(vertices amount), m(edges amount). And then m edges in format: A(out ...
0
votes
2
answers
148
views
Calculating total weight of MST using Prim's and a heap
Attempting to implement a method that builds a MST using prim's and a min heap (using priority queue) and returns the total weight of the MST.
My code seems to produce different results to what is ...
1
vote
1
answer
116
views
How to use Boost MST Algorithm on a complete Graph [closed]
I am very new to the BGL. I have the following problem: I've got a very large complete Graph and weights for every edge and need to evaluate a Minimum Spanning Tree.
I would like to use the Boost ...