minimum-spanning-tree Questions
5
Solved
Dijkstra's is typically used to find the shortest distance between two nodes in a graph. Can it be used to find a minimum spanning tree? If so, how?
Edit: This isn't homework, but I am trying to u...
Destination asked 15/12, 2009 at 18:8
3
Solved
I was trying to develop a clustering algorithm tasked with finding k classes on a set of 2D points, (with k given as input) using use the Kruskal algorithm lightly modified to find k spanning trees...
Alkalize asked 5/12, 2013 at 3:47
1
Solved
I have a symmetrical graph and created a tree with all shortest path from a random vertex to any other vertex. Can I use the tree to construct a Minimum Spanning Tree(MST)? My algorithm is similar ...
Borderline asked 5/7, 2013 at 17:28
4
Solved
As my question speaks I want to know why do we use Priority queue in Prim's Algorithm?
How does it saves us from using the naive way (yes I've heard of it but don't know why).
I'd be very happy if...
Paddie asked 12/8, 2011 at 10:6
2
I'm currently optimizing electrical grid planning and the MST doesn't solve the problem well, because if the connection to the main grid is in a radial point all the power has to flow through one e...
Earthwork asked 26/6, 2013 at 19:36
1
Solved
I'm looking for an algorithm (or any other way) to determine if a given weighted graph has unique MST (Minimum spanning tree) in O(ElogV)?
I don't know anything about the weights (e.g. weight(e1) ...
Genuflection asked 25/6, 2013 at 21:29
2
I'm studying graph theory and I have a question about the connection between minimum spanning trees and shortest path trees.
Let G be an undirected, connected graph where all edges are weighted wi...
Weakminded asked 13/6, 2013 at 17:53
2
Solved
I am studying Prim's Algorithm. There is a part within the code the next vertex across the cut will be coming to the set of the vertices belonging to the MST. While doing that, we also have to 'upd...
Hydrargyrum asked 12/6, 2013 at 21:15
2
How i can calculate im R(3.0.0 - Linux x32) minimum spanning tree with Kruskal's algorithm?
I create an weighted full graph with igraph (0.6.5) library as folws:
set.seed(1234567890)
g <- grap...
Hoyle asked 17/5, 2013 at 9:33
3
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal sp...
Gerena asked 15/5, 2013 at 18:41
2
Solved
I have this question from Robert Sedgewick's book on algorithms.
Critical edges. An MST edge whose deletion from the graph would cause the
MST weight to increase is called a critical edge. Sho...
Feliciafeliciano asked 30/3, 2013 at 15:25
2
Solved
Let G = (V, E) be a weighted, connected and undirected graph and let T be a minimum spanning tree. Let e be any edge not in E (and has a weight W(e)).
Prove or disprove:
T U {e} is an edge set that...
Ewold asked 25/2, 2013 at 17:32
4
Solved
I'm trying to solve a problem related to graphs in Python. Since its a comeptitive programming problem, I'm not using any other 3rd party packages.
The problem presents a graph in the form of a 5...
Harless asked 13/1, 2013 at 4:13
1
Solved
A minimum spanning tree gives the cheapest way an undirected graph. But what is a minimum spanning forest? Is it defined for connected graphs or unconnected graphs?
Ousley asked 13/1, 2013 at 10:35
2
Solved
I don't want to find all the minimum spanning trees but I want to know how many of them are there, here is the method I considered:
Find one minimum spanning tree using prim's or kruskal's algori...
Dardanelles asked 13/12, 2012 at 5:53
2
I have an undirected connected graph G. I wish to find an algorithm that return true if there are at least 2 MSTs.
What if I want to see if there are exactly 2 MSTs?
Bluebird asked 6/12, 2012 at 20:3
1
Solved
One can use Prim's algorithm or Kruskal's algorithm to find the minimum spanning tree/graph of a collection of vertices/nodes and edges/links. What I want though, is an algorithm that finds the min...
Willing asked 30/10, 2012 at 19:58
3
Solved
Can someone explain to me why is Prim's Algorithm using adjacent matrix result in a time complexity of O(V2)?
Globose asked 30/10, 2012 at 4:15
2
Given an undirected connected graph with weights. w:E->{1,2,3,4,5,6,7} - meaning there is only 7 weights possible.
I need to find a spanning tree using Prim's algorithm in O(n+m) and Kruskal's algo...
Seaway asked 28/5, 2012 at 8:1
1
Solved
Here is an excise:
Consider the problem of finding a minimum weight connected subset T of edges from a weighted connected graph G. The weight of T is the sum of all the edge weights in T.Give an...
Kettie asked 2/5, 2012 at 22:20
2
Solved
"Thus, the total time for Prim's algorithm is O(V lg V + E lg V) = O(E lg V), which is asymptotically the same as for our implementation of Kruskal's algorithm."
From http://serverbob.3x.ro/IA/DDU...
Petcock asked 14/6, 2011 at 22:54
2
Solved
So I need some help coming up with a way to find a Minimum spanning tree.
Suppose I have my graph in the form of an adjacency list:
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 ...
Contexture asked 26/2, 2012 at 2:17
2
A graph (positive weight edges) with a MST
If some edge, e is modified to a new value, what is the best way to update the MST without completely remaking it. I think this can be done in linear time...
Shaduf asked 29/3, 2012 at 20:58
2
Solved
Suppose that you have a directed graph with nonnegative, integer edge lengths that are in the range 0 to U - 1, inclusive. What is the fastest algorithm for computing a minimum spanning tree of thi...
Selfridge asked 15/1, 2012 at 23:25
2
With reference to Kruskal's algorithm in Ada, I'm not sure where to start.
I'm trying to think through everything before I actually write the program, but am pretty lost as to what data structures...
Passionless asked 17/10, 2011 at 2:20
© 2022 - 2024 — McMap. All rights reserved.