Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations Chriss Miller on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
graph algorithms
- Thread starter vintl
- Start date
- Thread starter
- #3
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>>0) i=dad<i>;<br>while(dad[j]>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>>0) i=dad<i>;<br>while(dad[j]>0) j=dad[j];<br>if(doit&&(i!=j))dad[j]=i;<br>for(int k=1;k<N;k++)<br>cout<<dad[k];<br>cout<<endl;<br>return(i!=j);<br>}<br>main()<br>{<br>int E, V;<br>EQ eq(20);<br>for(int i=0;i<E;i++)<br>eq.find(*,*,1);<br>...<br>}<br>
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...
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...
- Thread starter
- #5
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.
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.
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!
- Status