Breadth-first and depth-first search algorithms in a 5x5 grid of numbers

Question

We're supposed to read in a text file with a 5x5 grid of numbers and write a breadth-first search and a depth-first search methods.

I'm not asking for anyone to do my homework for me, but I would like some help understanding the theory of these algorithms. Pseudocode wouldn't hurt either.

Solution 1

Breadth first search essentially means: visit all of the parent nodes, then visit all of the children nodes.

While depth first search means: visit all the of the children nodes first until your reach a leaf node (a node with no children), then visit the next parent node and all of there children node and keep on until you visited all of the nodes.

Here you have picture (taken from Wikipedia) that shows the order (represented by a tree) in which the nodes are visited in a breadth-first search:

Here you have the corresponding picture for a depth-first search:

The pseudocode for

Breadth First Search:

def BFS(G,v):

    create a queue Q
    enqueue v onto Q
    mark v

    while Q is not empty:
      t = Q.dequeue()

      if t is what we are looking for:
          return t

      for all edges e in G.incidentEdges(t) do:
         o = G.opposite(t, e)

     if o is not marked:
          mark o
          enqueue o onto Q

Essentially you are creating a queue and adding all of the nodes in it... Remember a queue is first-in-first-out data structure.

Depth First Search:

def DFS(G, v):
    label v as explored

    for all edges e in G.incidentEdges(v) do:

      if edge e is unexplored then:

          w = G.opposite(v, e)

          if vertex w is unexplored then:

              label e as a discovery edge
              recursively call DFS(G, w)
      else 
         label e as a back edge

Now, for this one, you are pretty much setting an explored flag, if you have explored all of them then you have done depth first search in order.

Solution 2

Depth and breadth first searches may be easier to understand in the context of a tree.

    A
   / \
  B   C
 /
D

A depth-first search (DFS) will visit child nodes before visiting sibling nodes. A dept first search of the above tree would visit items in the following order:

A B D C

C is B's sibling so it is searched after searching through B's descendants.

A breadth-first search (BFS) searches sibling nodes before visiting child nodes. A breadth first search of the above tree would visit items in the follow order:

 A B C D   

B and C are siblings so they are searched before B's child, D.

Comments

[dlev]

First: Get some confidence! I'm sure you're not actually useless. Second: This is a question better suited for Google. StackOverflow questions are expected to be about specific programming problems that you have attempted to solve yourself.

[cjm]

Do a little research and then if you have more specific questions come back.

[Juvanis]

you are not useless! i edited the question.

[Kevin]

the journey of a million miles begins with a single step.

[nbro]

This is nice, but I would like to see also an example in a raw graph. Could you please provide it?

[nbro]

This answer is bad. The pseudocode is confusing and you have explained it far away from well. Also, the initial explanations of the algorithms are not good, in my opinion.

[The Doctor]

Forgot I even wrote this question. Coming back to it, I am curious to see what an example for a raw graph would be. If anyone sees this, would the implementation even really be different from that of DFS for a tree?