I am trying to implement a randomly generated maze using Prim's algorithm. I want my maze to look like this: however the mazes that I am generating from my program look like this: I'm current...

I've been spending a lot of time reading online presentations and textbooks about the cut property of a minimum spanning tree. I don't really get what it's suppose to illustrate or even why it's pr...

I was wondering when one should use Prim's algorithm and when Kruskal's to find the minimum spanning tree? They both have easy logics, same worst cases, and only difference is implementation which ...

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Given two connected weighted graphs and a set of pairs of vertices that can "cross the river" between the two graphs, the task is to find an MST (minimum spanning tree) of a graph made of...

I've been looking for an implementation (I'm using networkx library.) that will find all the minimum spanning trees (MST) of an undirected weighted graph. I can only find implementations for Krusk...

I am using an adjacency matrix, priority queue is the data structure. By my calculation, complexity is V^3 log V: While loop: V Checking adjacent Vertices: V Checking the queue if the entry is a...

I want to make a dynamic minimum spanning tree. I have an existing MS tree over n vertices and I add one more vertex and edges to all the existing vertices from this new vertex. How can I update th...

We can find a minimum bottleneck spanning tree in O(E log*V) in the worst case by using Kruskal's algorithm. This is because every minimum spanning tree is a minimum bottleneck spanning tree. But...

I have a list as c4_leaves = [56,78,90,112]. I'm trying to create a complete graph using these elements in c4_leaves as nodes. Here's what I've tried: V_ex = c4_leaves G_ex = nx.Graph() G_ex.add_n...

Given a graph of N vertices and the distance between the edges of the vertices stored in tuple T1 = (d11, d12, …, d1n) to Tn = (dn1, dn2, …, dnn). Find out a minimum spanning tree of this graph sta...

Does the opposite of Kruskal's algorithm for minimum spanning tree work for it? I mean, choosing the max weight (edge) every step? Any other idea to find maximum spanning tree?

Let's assume a complete graph of > 25000 nodes. Each node is essentially a point on a plane. It has 625M edges. Each edge has length which should be stored as a floating point number. I need an al...

This is a follow-up question of Why most graph algorithms do not adapt so easily to negative numbers?. I think Shortest Path (SP) has problem with negative weights, because it adds up all weights ...

Here is an exercise: Either prove the following or give a counterexample: (a) Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortes...

I would like to know the difference between Boruvkas algorithm and Kruskals algorithm. What they have in common: both find the minimum spanning tree (MST) in a undirected graph both add the s...

MAKE-SET(x） x.p = x x.rank = 0 UNION(x, y) LINK(FIND-SET(x),FIND-SET(y)) LINK(x, y) if x.rank > y.rank y.p = x else x.p = y if x.rand == y.rank y.rank = y.rank +1 The FIND-SET proce...

I am working on an algorithm to check if a given edge is included in one of all possible mst's. For this question, we are considering non-distinct values and our edge e connects vertices A & B...

I am struggling with this. We can get MST using Kruskal's algorithm or Prim's algorithm for the MST. And for "second-best" MST, I can: first get MST using either of the algorithm mentioned abo...

Let's say there's Graph G such that it all its edges have weights that correspond to distinct integers. So no two edge has the same weight. Let E be all the edges of G. Let emax be an edge in E wit...

A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. A MBST is not necessarily a MST (minimum sp...

What algorithm can I use to find a minimum spanning tree on a directed graph? I tried using a modification of Prim's algorithm, but wasn't able to make it work.

I intuitively feel that if one is using Prim's algorithm to find a graph's minimum spanning tree, it doesn't matter which root node is picked - the resultant MST will have the same weight regardles...

A graph can have many different Minimum Spanning Trees (MSTs), but can different MSTs have different sets of edge weights? For example, if an MST uses edge weights {2,3,4,5}, must every other MST h...

I have the following problem on my homework: Give an O(n+m) algorithm to find that whether an edge e would be a part of the MST of a graph (We are allowed to get help from others on this assig...