Results 1 to 2 of 2
  1. #1
    hey
    hey is offline Member
    Join Date
    Dec 2007
    Posts
    21
    Rep Power
    0

    Default Graph DPS and BFS implementation

    Hello everyone,

    I'm preparing for an exemption exam. There are a couple of questions I need to solve.((

    Given the following Java class definition for a graph
    Java Code:
    public class MyGraph<E> {
    public class Node {
    E myValue;
    boolean tag;
    ArrayList<Node> myNeighbors;
    }
    ArrayList<Node> myNodes;
    void visitNode(Node n) {/* Action to be performed when traversing node */}
    void deptFirstSearch(Node n) { /* Perform depth-first search of graph starting at n */ }
    }
    i. Write code for the method depthFirstSearch( n ) that performs a depth first traversal
    starting at node n.
    ii. Write code for the method breadthFirstSearch(n) that performs a breadth first traversal
    starting at node n.


    I looked through available lectures and there is no code mentioned there, just description of those algorithms.

    DFS Traversal Algorithm
    for all nodes X
    X.tag = False
    put 1stnode in Stack
    while (Stack not empty )
    pop X off Stack
    if (X.tag = False)
    set X.tag = True
    for each successor Y of X
    if (Y.tag = False)
    push Y onto Stack


    BFS Traversal Algorithm
    for all nodes X
    X.tag = False
    put 1stnode in Queue
    while ( Queue not empty )
    take node X out of Queue
    if (X.tag = False)
    set X.tag = True
    for each successor Y of X
    if (Y.tag = False)
    put Y in Queue


    I was wondering, if someone can helpme with writing a code.

  2. #2
    hey
    hey is offline Member
    Join Date
    Dec 2007
    Posts
    21
    Rep Power
    0

Similar Threads

  1. Need Help for Dot Plot Graph
    By BHCluster in forum Java 2D
    Replies: 5
    Last Post: 04-15-2008, 02:54 PM
  2. Big Faceless Graph Library 2.3.3
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 11-09-2007, 10:33 PM
  3. Big Faceless Graph Library 2.3.2
    By levent in forum Java Software
    Replies: 0
    Last Post: 08-07-2007, 04:28 PM
  4. How to insert graph in java
    By valery in forum Advanced Java
    Replies: 1
    Last Post: 08-06-2007, 08:38 PM
  5. Help with graph code example
    By silvia in forum Java 2D
    Replies: 1
    Last Post: 07-29-2007, 10:16 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •