Minumum spanning tree

[earthquake]

Hi guys.I have a homework about Minumum Spannning tree in the order that Prims's algorithm includes them starting from node G.Can you help me??

I am sorry .I don't know how to add a image file.Therefore,I added a link.


http://u1311.hizliresim.com/1h/c/ug0t3.png


I have to complete the sequence of nodes.

[Duthomhas]

That's a pretty picture, but what is your input? Or is the picture all you are given?

I assume the latter.

Store your graph as a matrix (a 2D array), where nodes show connections thus:

if node1 connects to node2, then graph[node1][node2] is nonzero. (This assumes that no edge can have a weight of zero.)

Since it is a nondirected graph, you will have duplicate information in the graph -- that is graph[node1][node2] == graph[node2][node1].

It is possible to ignore this duplicate information, but for the moment I recommend that you don't worry about it. Just make sure to set both graph[node1][node2] and graph[node2][node1] to the same value when you create your minimum spanning tree.

You will also want a way to convert 'A' to an index into the graph, since in C++ you can only index arrays with integers, starting at zero.

unsigned index_of( char letter )
{
  return letter - 'A';
}

Having that, we can now create the input tree graph:

unsigned graph[ 8 ][ 8 ] =  // 'A' to 'H' is eight nodes
{ // A,  B,  C,  D,  E,  F,  G,  H
  {  0,  1,  0,  0,  0,  2,  3,  0 }, // A | connects to B (weight=1), F (weight=2), and G (weight-3)
  {  1,  0,  0,  0,  0,  0,  0,  0 }, // B | only connects to A (weight=1)
  {  0,  0,  0,  0,  0,  0,  5,  0 }, // C | only connects to G (weight=5)
  ... // and so on 
};

Now, to create your minimum spanning tree, you start with an empty graph:

unsigned mst[ 8 ][ 8 ] = { { 0 } };  // all elements are zero


To perform Prim's algorithm, you start with any random node. Your assignment specifies that you should start with node G.

[code]unsigned current_node = index_of( 'G' ); 

All the nodes that are connected to node G are listed in the row G of the graph array. Loop through to find the smallest one, and add it to the tree. Remember that there are two spots on the graph that must be assigned. (G connects to H, so H connects to G, both with the same weight.)

mst[current_node][new_node] = 
mst[new_node][current_node] = graph[current_node][new_node];

The next step is to find the next node to add. You'll have to think about it -- there is actually a pretty simple answer. Remember (==hint), every node must be connected to the MST by the smallest edge not already connected to the tree.

Hope this helps.

[earthquake]

thank you for your answer but what I want to learn is sequence. Starting point is G.

FOR EXAMPLE: G A B F H C D E OR G A B F H C D E G like this

[earthquake]

please help??

[Duthomhas]

Build the tree to find out the order elements are added. You can't skip the building step.

[Computergeek01]

I don't mean to hijack this thread, but I missed out on stuff like this in school. In this game when you back track across an edge do you add the value of that edge a second time? Like when you go from 'G' -> 'A' -> 'B' you then need to back track to 'A' to reach another node. Does the value of that edge, 'B' back to 'A', get added to the total weight a second time? Wikipedia didn't quite clear that up for me.

[ne555]

The weight of a graph is simply the sum of the weights of its edges.

> Like when you go from 'G' -> 'A' -> 'B' you then need to back track to 'A' to reach another node.
There is no backtracking in the construction. You've got a subset of the nodes, those are all candidates that may provide the next edge to be added.

I think that you misunderstood the purpose of the algorithm.
You'll end with a sub-graph that connects all the nodes (there is a path between any pair). The weight of the sub-graph is minimal, you don't care for the weight of the paths*.

If you want a tree, you simply choose a `root' and define the direction of the edges appropriately.


*See Floyd-Warshall for the shortest path between all the pairs.

[Computergeek01]

The weight of the sub-graph is minimal, you don't care for the weight of the paths*.

That's where I think I'm having trouble. I thought the weight (the number) of the path is what is being added together. I'll try to read up on it some more.

[ne555]

You add the weight of the edges, no of the paths

[Computergeek01]

I think I get it now. You're statement:

There is no backtracking in the construction. You've got a subset of the nodes, those are all candidates that may provide the next edge to be added.

finally set in. Any nodes connected to a node that is already part of the graph is a valid move, you treat them as one entity not individually connected nodes, right?

[Duthomhas]

http://en.wikipedia.org/wiki/Prim%27s_algorithm

Edges connect nodes. You don't care about all edges, only about all nodes.

So, for each node already in the MST, you have a list of edges. From that list, you will choose one that connects to a node not already in the MST. From among those, chose the edge with the minimum weight.

An undirected graph means that you can travel both ways along an edge connecting two nodes. What that means is that your graph array (as I described above) will have at most two entries in the array.

For example:

  A B C
A 0 1 0
B 1 0 2   Table (the "graph array")
C 0 2 3

        1
   (A)-----(B)
           /
          /2        Graph
         /
     __(C)
    /   |
    \___/
     3

Notice that Table[A][B] shows 1, meaning A connects to B (weight = 1). Since it is an undirected graph, B also connects to A (with the same weight), so Table[B][A] is also 1.

C connects to itself, so it is along the diagonal (Table[A][A], Table[B][B], and Table[C][C]). That diagonal is the axis of symmetry in the table.

For a directed graph, there probably isn't any symmetry (but there could be, but if there were, the directed graph would be the same as an undirected graph).

Hope this answers your questions enough to get you started.

[Computergeek01]

That Wiki article is actually where my confusion came from, it's a little sparse on the description. ne555 did a good job explaining it and I appreciate you bringing it together to confirm my thoughts. I think I'm good now. Thank you.

[Duthomhas]

Ah. I often refresh to make sure I am posting something useful, but lately Chrome seems to think it is smarter than me and so my post comes after some (in this case, three) posts I didn't know where there...