recursive calls to function. how should i do it?

[streamkid]

hello..
i have the following problem to solve, which is part of mst problem.
i have some nodes (ie cities if you like), and each city is connected
with some other. we don't know which city is connected with what other
city, except for the 1st level (direct connections from city to city).
i want to build the complete map of what is connected to what.

let's say that i have:
city A, connected to: D, F
city B, connected to: A, C,
city C, connected to: D,

starting from city D, i find out that it's connected to C.
C is also connected to B and directly. We set also true that D is
connected to B.
Since B is connected To A, D must know that it's also connected to
whichother cities A is connected with.
And So on..

As you can see, there is a recursive "thing" in this process.
I 'm wondering how to implement it.. I thought of building a function
that would recursively calls its self, and does what i described with
words above.
And for each step deeper it will go, it won't check if the current
node is also connected with past-checked nodes..

I hope you get what i mean.. Can't describe it better :|

If you think that it could be done better/easier with another way,
tell me! :)

[Michael]

On Feb 23, 12:58 pm, "streamkid" <[e-mail]:

i have some nodes (ie cities if you like), and each city is connected
with some other. we don't know which city is connected with what other
city, except for the 1st level (direct connections from city to city).
i want to build the complete map of what is connected to what.

let's say that i have:
city A, connected to: D, F
city B, connected to: A, C,
city C, connected to: D,

starting from city D, i find out that it's connected to C.
C is also connected to B and directly. We set also true that D is
connected to B.
Since B is connected To A, D must know that it's also connected to
whichother cities A is connected with.
And So on..

If you think that it could be done better/easier with another way,
tell me! :)

Common ways to solve this are Dijkstra's algorithm, and the Floyd-
Warshall algorithm. Both are covered in Wikipedia.

Michael

[Piyo]

streamkid wrote:

If you think that it could be done better/easier with another way,
tell me! :)

BTW, this is not really a C++ question but hey, its an interesting
problem. So here is how I would approach this:
- write a recursive (or not) depth first traversal given a node
and returns all reachable nodes from that node. The signature
might look like:
{set of all reachable nodes from a and including a} dft( node a );

- then I would approach the problem by first initializing all nodes
marked as unreachable. Then pick any unreachable node and call dft
on it.

- this returns a set of nodes that are accesssible to and from each
other. Mark your nodes properly. eg. given {a, b, c} then
a can go to b and c
b can go to a and c
c can go to a and b

- rinse and repeat for the remaining unreachable nodes

Good Luck with your project :)

[streamkid]

thanx both of you for your answers :)

i started solving the mst, by using the reverse-delete algorithm..
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"

the function i want to write is for step 3 :)
i though of a recursive function and i 've written some lines..
maybe i post code tonight (local time 1am atm) or 2morrow morning :)

thanx again for your answers :)
streamkid

[Piyo]

streamkid wrote:

thanx both of you for your answers :)

i started solving the mst, by using the reverse-delete algorithm..
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"

the function i want to write is for step 3 :)
i though of a recursive function and i 've written some lines..
maybe i post code tonight (local time 1am atm) or 2morrow morning :)

thanx again for your answers :)
streamkid

BTW, Wikipedia is your friend. It even has pseudocode! Imagine that!

http://en.wikipedia.org/wiki/Reverse-Delete_algorithm

[streamkid]

On Feb 24, 1:23 am, Piyo <[e-mail]:

streamkid wrote:

thanx both of you for your answers :)

i started solving the mst, by using the reverse-delete algorithm..
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"

the function i want to write is for step 3 :)
i though of a recursive function and i 've written some lines..
maybe i post code tonight (local time 1am atm) or 2morrow morning :)

thanx again for your answers :)
streamkid

BTW, Wikipedia is your friend. It even has pseudocode! Imagine that!

http://en.wikipedia.org/wiki/Reverse-Delete_algorithm

yeah, i know, that's my source. i didn't know about that algorithm
before i read wiki ;)

[streamkid]

On Feb 24, 1:23 am, Piyo <[e-mail]:

streamkid wrote:

thanx both of you for your answers :)

i started solving the mst, by using the reverse-delete algorithm..
" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"

the function i want to write is for step 3 :)
i though of a recursive function and i 've written some lines..
maybe i post code tonight (local time 1am atm) or 2morrow morning :)

thanx again for your answers :)
streamkid

BTW, Wikipedia is your friend. It even has pseudocode! Imagine that!

http://en.wikipedia.org/wiki/Reverse-Delete_algorithm

" * Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.
"

which i pasted before is from wiki, but my problem is to implement 3rd
step (* Check if deleting current edge will further disconnect graph.)
in c++...