Prim and Kruskal's algorithms complexity

Question

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 algorithm in O( m*a(m,n)).

I have no idea how to do this and really need some guidance about how the weights can help me in here.

Seaway

Could you clarify what n, m and a are please? – Hartsfield

@Hartsfield m - Edges , N - Vertices – Seaway

Answer 1

You can sort edges weights faster.

In Kruskal algorithm you don't need O(M lg M) sort, you just can use count sort (or any other O(M) algorithm). So the final complexity is then O(M) for sorting and O(Ma(m)) for union-find phase. In total it is O(Ma(m)).

For the case of Prim algorithm. You don't need to use heap, you need 7 lists/queues/arrays/anything (with constant time insert and retrieval), one for each weight. And then when you are looking for cheapest outgoing edge you check is one of these lists is nonempty (from the cheapest one) and use that edge. Since 7 is a constant, whole algorithms runs in O(M) time.

Cracow

You don't need a linked list exactly. Just anything with constant time insert and retrieval. – Cracow

how with prim with two type of weights {1,2} we reach to O(E)? I couldn't get the point – Medardas

@MioUnio can you implement priority-queue for two values, which has constant type insert and retrieval? – Cracow

like +1 nice answer but would you please provide more detail? I couldent get the point – Medardas

If you have two weights.You just have two arrays. In one, you insert weights 1 in other you insert weights 2 (and the associated information about the edge). So, insert is constant time. Same goes for retrieval. You first look into array with weight 1, if it's nonempty you pick any edge from there. If it is empty you pick edge from array with weights 2. – Cracow

Answer 2

As I understand, it is not popular to answer homework assignments, but this could hopefully be usefull for other people than just you ;)

Prim:

Prim is an algorithm for finding a minimum spanning tree (MST), just as Kruskal is. An easy way to visualize the algorithm, is to draw the graph out on a piece of paper. Then you create a moveable line (cut) over all the nodes you have selected. In the example below, the set A will be the nodes inside the cut. Then you chose the smallest edge running through the cut, i.e. from a node inside of the line to a node on the outside. Always chose the edge with the lowest weight. After adding the new node, you move the cut, so it contains the newly added node. Then you repeat untill all nodes are within the cut.

A short summary of the algorithm is:

1. Create a set, A, which will contain the chosen verticies. It will initially contain a random starting node, chosen by you.
2. Create another set, B. This will initially be empty and used to mark all chosen edges.
3. Choose an edge E (u, v), that is, an edge from node u to node v. The edge E must be the edge with the smallest weight, which has node u within the set A and v is not inside A. (If there are several edges with equal weight, any can be chosen at random)
4. Add the edge (u, v) to the set B and v to the set A.
5. Repeat step 3 and 4 until A = V, where V is the set of all verticies.
6. The set A and B now describe you spanning tree! The MST will contain the nodes within A and B will describe how they connect.

Kruskal:

Kruskal is similar to Prim, except you have no cut. So you always chose the smallest edge.

1. Create a set A, which initially is empty. It will be used to store chosen edges.
2. Chose the edge E with minimum weight from the set E, which is not already in A. (u,v) = (v,u), so you can only traverse the edge one direction.
3. Add E to A.
4. Repeat 2 and 3 untill A and E are equal, that is, untill you have chosen all edges.

I am unsure about the exact performance on these algorithms, but I assume Kruskal is O(E log E) and the performance of Prim is based on which data structure you use to store the edges. If you use a binary heap, searching for the smallest edge is faster than if you use an adjacency matrix for storing the minimum edge.

Hope this helps!

Hampden