Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #23702

Re: depth first search

Show all headers | View raw

On Sunday, April 28, 2013 6:40:46 AM UTC-4, Chris Uppal wrote:
> Barb Knox wrote:
> 
> 
> 
> > This sounds like homework, but I'll give you a hint:  consider the 2D
> 
> > array to be a graph, with the vertices being the array elements and the
> 
> > edges being up/right/down/left adjacency.
> 
> 
> 
> Indeed, and a more remarkably obtuse example of using DFS would be hard to 
> 
> concoct.
> 
> 
> 
> Hmm...
> 
> 
> 
> Searching for the last character in a String ?
> 
> 
> 
> Returning the value of a static final integer field ??
> 
> 
> 
>     -- chris

Thanks for your help! But I need to clarify a few things if it is not too much trouble. So what I gather from your post is that if I am starting off at (x,y) that I need to do a recursive call on (x-1,y) , (x+1,y) , (x, y+1) and (x,y-1).  So for example:
/ / / / / / /
/ 00*11  /
/ *0000  /
/ 00111  /
/ 11100  /
/ 0010*  /
/ / / / / / /

Imagine 0's are white and 1's are black and * is an empty space.  Also image that the matrix also is a 7x7 and not a 5 by 5 where the above diagram is surrounded by '/' to make sure you don't get an index out of bounds error.  So really my starting place will be (2,2) and I will search (1,2), (3,2) (2,1) and (2,3).  So my idea was to change the 0's and 1's to some other character (but not the same character) if they are alive (this will tell me I have visited those spots) and dead spots I have visited will also be changed to a character to know I have visited them.  But the problem is if i start at (2,2) above and mark that first spot dead I still need to come back and change it to alive after I have visited the spot below it or the spot 2 to the right of it.  (Because liveness is contagious with similar colors).  Can you maybe provide some more specific assistance.  This is HW and I do not want the answer but I have been cracking away at this on scratch paper with pictures and diagrams but still am a little stuck.


I have a template for DFS but I do not know how to apply it to this situation:

DFS(Vertex){
   if visited(vertex) =  true{
            return;
   }
   visited(vertex) = true;
   Application SPecific Processing goes here
   for each neighbor W of vertex,
     DFS(W);

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

depth first search willmann817@gmail.com - 2013-04-27 21:46 -0700
  Re: depth first search Barb Knox <see@sig.below> - 2013-04-28 21:06 +1200
    Re: depth first search "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-04-28 11:40 +0100
      Re: depth first search willmann817@gmail.com - 2013-04-28 07:22 -0700
        Re: depth first search "Alex" <foo@email.invalid> - 2013-04-28 20:25 +0000
          Re: depth first search Lew <lewbloch@gmail.com> - 2013-04-28 19:01 -0700
        Re: depth first search Lew <lewbloch@gmail.com> - 2013-04-28 18:42 -0700
          Re: depth first search Barb Knox <see@sig.below> - 2013-04-29 13:59 +1200
            Re: depth first search lipska the kat <"nospam at neversurrender dot co dot uk"> - 2013-04-29 11:21 +0100
              Re: depth first search Barb Knox <see@sig.below> - 2013-05-02 16:02 +1200
  Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 12:22 -0700
  Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 12:49 -0700
    Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 16:21 -0700
  Re: depth first search Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2013-04-28 21:43 -0500
    Re: depth first search willmann817@gmail.com - 2013-04-29 08:46 -0700

csiph-web