On Mon, Nov 22, 2010 at 9:37 AM, Sakthi Priyan
<[email protected]> wrote:
> I am sorry. I didn't explain my problem clearly at first shot.
> It goes like this
> Assume there are five nodes in a graph. I am giving the Adjacency Matrix
> here.
> 1 2 3 4 5
> 1 0 1 1 1 1
> 2 1 0 1 0 0
> 3 1 1 0 0 0
> 4 1 0 0 0 1
> 5 1 0 0 1 0
> Now I need to visit all the nodes with minimum weights crossed. This is the
> problem :(
Do you mean you need to find the minimum spanning tree? If so, I
suggest you read the Kruskal's algorithm [1] or similars.
> Here we have two closely connected components (CCC), 123 and 145. And node 1
> acts like a bridge between those CCC. If I enter any of those CCC, I need to
> touch node 1 again to reach the other. So, if I mark node 1 as visited at
> first, the program will start from 1 and lets say it touches 2 and then it
> ll touch 3. From 3, it has to go to 1 and by that time node 1 is marked as
> visited. So program 'll halt there and 'll give wrong result.
I think you have misunderstood the Vineel's advice; I'll try and
explain how to walk a graph making use of some pseudo code:
function walk(n):
if n is visited
return
mark `n' as visited
<for each node, m, linked to n>
walk(m)
I hope it helps.
Regards,
Matteo
[1] http://en.wikipedia.org/wiki/Kruskal's_algorithm
--
Matteo Landi
http://www.matteolandi.net/
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
