Traversing an undirected, unweighted graph with a twist: minimum visits to each node

Question

I'm trying to write code that will traverse an undirected, unweighted graph. Essentially, the method will be passed a node (which knows all its neighbors). The method then has to build a model of the graph as efficiently* by going from node to node and collecting information which nodes link to each other. At the end, the method will have a complete list of all the nodes and all the vertices that connect them.

*The crux of the problem lies in the word efficiently and what I mean by it. Let me direct your attention to this small graph:

Let's say I start at node G. I can either visit C, B, F, D, H, J or E. I want to minimize the amount of times I visit a node and in order to visit a node, I must pass through all nodes on the way to that node.

Example: let's say I decide to visit node C. The next node to visit could be either A, B, F, D, H, J or E. However, to visit any node except for A, I would have to pass through G again which is considered inefficient. And in order to visit A, I would have to visit G and C again and then pass through C and then G to get back to the rest of the graph. So I decide to visit A. This means I have to pass through C again to reach G. Thus, from a logical point of view, it makes sense to visit the C branch last.

However, the program, when it starts at Node G, is unaware that branch C leads to a dead-end. As I write this, I think it might be impossible, but I ask it anyways: is there anyway to traverse this graph as efficiently as possible (as I have previously defined it) using only the information given (i.e. that the program only knows about the nodes its visited and the edges emanating from those nodes? Or should I just go with a variation Dijkstra's algorithm in order to insure I visit every node?

This will all be written in Java if that matters.

Answer 1

Wouldn't just a simple recursion with a collect-argument do?

public void traverse(Node n, Set<Node> visisted) {

  visited.add(n);

  for (Node neighbour : n.getNeighbours()) {

    if (!visited.contains(neighbour)) {
      traverse(neighbour, visited);
    }

  }

}

Answer 2

Do you want simply to traverse the whole graph (regardless of the path taken), and do some operation on each node, or do you want to compute the shortest path from one node to any other node? (I might not understand your goal.)

In the first case, stick to a traversal algorithm such as Breadth First Search. For the other, you may want to consider Dijkstra by using same-weighted edges (i.e. = 1).

You can see the BFS as a special case of Dijkstra when you are interested only in one starting node and all edges have the same weight. With different costs you could use Uniform Cost Search.