Primeiro em profundidade e primeiro em largura são duas maneiras comuns de percorrer um gráfico.
Graph traversal é o processo de visitar cada vértice do gráfico exatamente uma vez. Existem duas maneiras populares de percorrer um gráfico: travessia em profundidade (ou pesquisa em profundidade) e travessia em largura (ou amplitude -primeira pesquisa). Ambas as travessias resultam em uma árvore geradora, que pode ser modelada usando uma classe, conforme mostrado na figura abaixo. Observe que Tree é uma classe interna definida na classe AbstractGraph. AbstractGraph.Tree é diferente da interface Tree definida em Procurando por um Elemento. AbstractGraph.Tree é uma classe especializada projetada para descrever o relacionamento pai-filho dos nós, enquanto a interface Tree define operações comuns, como pesquisar, inserir e excluir em uma árvore. Como não há necessidade de realizar essas operações para uma árvore geradora, AbstractGraph.Tree não é definido como um subtipo de Tree.

A classe Tree é definida como uma classe interna na classe AbstractGraph nas linhas 226–293 em AbstractGraph.java. O construtor cria uma árvore com raiz, arestas e uma ordem de pesquisa.

A classe Tree define sete métodos. O método getRoot() retorna a raiz da árvore. Você pode obter a ordem dos vértices pesquisados ​​invocando o método getSearchOrder(). Você pode invocar getParent(v) para encontrar o pai do vértice v na pesquisa. Invocar getNumberOfVerticesFound() retorna o número de vértices pesquisados. O método getPath(index) retorna uma lista de vértices do índice de vértice especificado até a raiz. Invocar printPath(v) exibe um caminho da raiz para v. Você pode exibir todas as arestas da árvore usando o método printTree().