graph algorithms

[vintl]

hulo,<br>does anyone know how the graph algorithm-&gt;union-Find algorithms works?<br>if possible pls include a working algorithms of the union-Find algorithms so i can understand how it works.<br>thanks<br>

 

[Nosferatu]

Could you be more specific pls? That sounds a little like the Greedy method for finding a hamiltonian cycle in a graph... What should that algorithm do?

 

[vintl]

union-find is where we wish to know whether or not a vertex x is connected to a vertex y in a graph. thats all i know.<br>i have some algorithms..but i need to make it work so i can understnad better. heres the algo<br>class EQ {<br>private:<br>int *dad;<br>public:<br>EQ(int size);<br>int find(int x, int y, int doit);<br>};<br><br>int EQ::find(int x, int y, int doit)<br>{<br>int i=x, j=y;<br>while(dad<i>&gt;0) i=dad<i>;<br>while(dad[j]&gt;0) j=dad[j];<br>if(doit&&(i!=j))dad[j]=i;<br>return(i!=j);<br>}<br>i try to make some modification so i can print something..but it doesn't work. like,<br>int EQ::find(int x, int y, int doit)<br>{<br>int i=x, j=y;<br>while(dad<i>&gt;0) i=dad<i>;<br>while(dad[j]&gt;0) j=dad[j];<br>if(doit&&(i!=j))dad[j]=i;<br>for(int k=1;k&lt;N;k++)<br>cout&lt;&lt;dad[k];<br>cout&lt;&lt;endl;<br>return(i!=j);<br>}<br>main()<br>{<br>int E, V;<br>EQ eq(20);<br>for(int i=0;i&lt;E;i++)<br>eq.find(*,*,1);<br>...<br>}<br>

 

[Nosferatu]

Well, i can't quite understand the purpose of dad array...

Anyway, a very simple algorithm that does just that is the Roy-Warshall algorithm: (and as i can see, it resembles the algorithm you put here)
It works on a bi-dimensional matrix, that represents the connections in a graph, like:
mat[j] = 1 if there is a link between i and j

mat[j] = 0 if there isnt a link between i and j

The algorithm works like:
int i,j,k;
for (i=0;i<n;i++)
for(j=0;j<n;j++)
for (k=0;k<n;k++)
if (mat[k] && mat[k][j])
mat[j] = 1;

where n is the number of graph nodes.
The algorithm simply states that :
If theres a link between i and k and between k and j then there is a link between i and j.


Hope this helps...

 

[vintl]

the dad arrray contains, for each vertex, the index of its parent ( 0 if it is the root of some tree) as specified in the class..
the constructor allocates the space for the dad array and sets all its values initially to 0. this find function implement both union and find operations. if the third argument is 0 we do find only,if its nonzero we do union.

 

[Nosferatu]

Well, as i mentioned in my tip, the union-find should be fairly similar to Roy-W. alg. i put above.

However, there' a slight mistake in the code (a big one indeed), i'm sorry if i mislead you. The last 2 lines of the code should be like:
if (mat[k] && mat[k][j])
mat[j] = 1;


Also,
mat[j] = 1 if there is a link between i and j

mat[j] = 0 if there isnt a link between i and j


Good luck!