Depth First Search & Breadth First Search implementation
Data Structure

Your terminology is a bit off.  Trees have roots and children.  Arbitrary graphs, on the other hand… I think "origin" and "neighbors" would be more appropriate.


Visited flag: Storing the visited/unvisited flag in the Node hurts flexibility.  Once you perform a dfs() or bfs(), that graph is "ruined".  You won't be able to reset all nodes to the unvisited state.  (Well, you could do it manually, since Node.state is a public field, after all.  But that's nasty too.)  Instead, I suggest that dfs() and bfs() keep a HashSet of visited nodes.  Once the traversal is done, just discard the set.
State.Visiting: That value is never used.
Node.getNode(): The name suggests that it would return a single node, but it doesn't.  Also, by returning the entire array, and the original of the array rather than a copy, you would be letting the caller alter the graph's connections in unapproved ways.  Better to offer ways to iterate through all neighbours and to fetch a specific neighbour.
Child vertex array: The Node constructor says: vertices = new Node[8];  However, addNode() checks if (count &lt; 10).  You should test against vertices.length instead.

If the capacity is exceeded, you should't print to System.out as a side-effect.  Throw an exception instead, so that the caller can decide how to handle it.

Better yet, use an expandable data structure so that you don't have to deal with capacity limits.  A simple substitution would be to use an ArrayList&lt;Node&gt;, but read on…
Graph.vertices vs. Node.child: Those arrays seem to serve the same purpose, redundantly.
Graph.createNewGraph(): It's cumbersome.  Wouldn't it be nice to be able to write

Graph g = new Graph();
g.addEdge("A", "B");
g.addEdge("B", "C");
…
return g;



My suggestion:

public class Graph {
    // Alternatively, use a Multimap:
    // http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html
    private Map&lt;String, List&lt;String&gt;&gt; edges = new HashMap&lt;String, List&lt;String&gt;&gt;();

    public void addEdge(String src, String dest) {
        List&lt;String&gt; srcNeighbors = this.edges.get(src);
        if (srcNeighbors == null) {
            this.edges.put(src,
                srcNeighbors = new ArrayList&lt;String&gt;()
            );
        }
        srcNeighbors.add(dest);
    }

    public Iterable&lt;String&gt; getNeighbors(String vertex) {
        List&lt;String&gt; neighbors = this.edges.get(vertex);
        if (neighbors == null) {
            return Collections.emptyList();
        } else {
            return Collections.unmodifiableList(neighbors);
        }
    }
}


Traversal

Your dfs() and bfs() methods can only ever print the node names.  You can't reuse the code for anything else, since the System.out.print() calls are mingled with the graph traversal code.  It would be better to implement an Iterator so that the caller can decide what to do with each node.

Also, DFS and BFS are two different strategies for accomplishing a similar task.  Therefore, they should be implemented in two classes with a shared interface.  I suggest an Iterator&lt;String&gt;.

The breadth-first iterator is a pretty straightforward translation of your original code, with the main difference being that the iterator is now responsible for keeping track of which vertices have been visited.

public class BreadthFirstIterator implements Iterator&lt;String&gt; {
    private Set&lt;String&gt; visited = new HashSet&lt;String&gt;();
    private Queue&lt;String&gt; queue = new LinkedList&lt;String&gt;();
    private Graph graph;

    public BreadthFirstIterator(Graph g, String startingVertex) {
        this.graph = g;
        this.queue.add(startingVertex);
        this.visited.add(startingVertex);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean hasNext() {
        return !this.queue.isEmpty();
    }

    @Override
    public String next() {
        //removes from front of queue
        String next = queue.remove(); 
        for (String neighbor : this.graph.getNeighbors(next)) {
            if (!this.visited.contains(neighbor)) {
                this.queue.add(neighbor);
                this.visited.add(neighbor);
            }
        }
        return next;
    }
}


Unfortunately, you'll find that you can no longer use recursion for depth-first traversal.  Instead, you'll have to rewrite it as an iterative solution using an explicit stack, which makes the code more complicated.  (Alternatively, if you abandon the idea of making an Iterator and use the visitor pattern instead, then you could keep the same recursive code structure).

public class PreOrderDFSIterator implements Iterator&lt;String&gt; {
    private Set&lt;String&gt; visited = new HashSet&lt;String&gt;();
    private Deque&lt;Iterator&lt;String&gt;&gt; stack = new LinkedList&lt;Iterator&lt;String&gt;&gt;();
    private Graph graph;
    private String next;

    public PreOrderDFSIterator(Graph g, String startingVertex) {
        this.stack.push(g.getNeighbors(startingVertex).iterator());
        this.graph = g;
        this.next = startingVertex;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean hasNext() {
        return this.next != null;
    }

    @Override
    public String next() {
        if (this.next == null) {
            throw new NoSuchElementException();
        }
        try {
            this.visited.add(this.next);
            return this.next;
        } finally {
            this.advance();
        }
    }

    private void advance() {
        Iterator&lt;String&gt; neighbors = this.stack.peek();
        do {
            while (!neighbors.hasNext()) {  // No more nodes -&gt; back out a level
                this.stack.pop();
                if (this.stack.isEmpty()) { // All done!
                    this.next = null;
                    return;
                }
                neighbors = this.stack.peek();
            }

            this.next = neighbors.next();
        } while (this.visited.contains(this.next));
        this.stack.push(this.graph.getNeighbors(this.next).iterator());
    }
}


Tests

This problem deserves better testing.  With the original code, which always printed its output to System.out, there was no good way to write unit tests.  Now, you can do anything you want with the results, so it is possible to write proper unit tests.

import static org.junit.Assert.*;

import org.junit.BeforeClass;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

import java.util.*;

// javac -cp .:junit.jar GraphTest.java
// java -cp .:junit.jar:hamcrest-core.jar org.junit.runner.JUnitCore GraphTest

@RunWith(JUnit4.class)
public class GraphTest {

    public static Graph graph1;

    @BeforeClass
    public static void makeGraphs() {
        Graph g = graph1 = new Graph();
        g.addEdge("A", "B");
        g.addEdge("B", "C");
        g.addEdge("B", "D");
        g.addEdge("B", "A");
        g.addEdge("B", "E");
        g.addEdge("B", "F");
        g.addEdge("C", "A");
        g.addEdge("D", "C");
        g.addEdge("E", "B");
        g.addEdge("F", "B");
    }

    private void expectIteration(String answer, Iterator&lt;String&gt; it) {
        StringBuilder sb = new StringBuilder();
        while (it.hasNext()) {
            sb.append(' ').append(it.next());
        }
        assertEquals(answer, sb.substring(1));
    }

    @Test
    public void preOrderIterationOfIsolatedVertex() {
        expectIteration("Z", new PreOrderDFSIterator(graph1, "Z"));
    }

    @Test
    public void preOrderIterationFromA() {
        expectIteration("A B C D E F", new PreOrderDFSIterator(graph1, "A"));
    }

    @Test
    public void preOrderIterationFromB() {
        expectIteration("B C A D E F", new PreOrderDFSIterator(graph1, "B"));
    }

    @Test
    public void BreadthFirstIterationOfIsolatedVertex() {
        expectIteration("Z", new BreadthFirstIterator(graph1, "Z"));
    }

    @Test
    public void BreadthFirstIterationFromA() {
        expectIteration("A B C D E F", new BreadthFirstIterator(graph1, "A"));
    }

    @Test
    public void BreadthFirstIterationFromB() {
        expectIteration("B C D A E F", new BreadthFirstIterator(graph1, "B"));
    }
}