グラフの頂点でマークが付いている頂点数を数える

[たかし]

大学の講義の過去問で分からないものがあります。
問題

コード:

//グラフの頂点を次のVertexクラスで表現する。
public class Vertex {
  public boolean mark; //マーク
  public int degree; //隣接頂点の個数
  public Vertex neighbor[]; //最初のdegree個の要素が隣接頂点を参照
}

//Vertexクラスの次のメソッドを完成させよ。

int numberOfMarkedNeighbors()
//隣接頂点のうち、markの値がtrueであるものの個数を数えて値とする。

次のようなものを考えました。

コード:

int numberOfMarkedNeighbors(Vertex v){
  int result = 0;

  if(v.marked){
    result++;
  }
  for(int i = 0; i < c.degree; i++) {
    result = result + numberOfMarkedNeighbors(v.neighbor[i]);
  }

  return result;
}

しかしこれでは再帰呼び出しを行ったときに同じ頂点同士を再帰し続けて無限ループになってしまうと思います。
例）頂点0のneighbor[0]は頂点1でそれに対して再帰呼び出しをする。
　　頂点1のneighbor[0]は頂点0でそれに対して再帰呼び出しをする。
　　これの繰り返しが起こる。

前の授業ではすべての頂点にマークを付けるというプログラムを作りました。
そのときは訪問した頂点はtrueにできるので訪問済みであればreturnをしました。
ですが今回の場合はマークがあらかじめ付いているのでマークが付いていればreturnというわけにはいきません。

どうしたらよいのか分からないのでご教授お願いします。

[beatle]

良くある問題ですね。

要素がたくさんあるコレクションを色々な順番で訪問する過程で、訪問済み頂点を記録しておきたい。
でも、対象クラスは変更してはいけない。
こんな時は、「訪問済み要素を記録しておくコレクション」を作ります。訪問済み要素一覧、ということです。

コレクションには要素の重複がない「Set」が適します。

コード:

Set<Vertex> visited_vertices = new HashSet<Vertex>();

そして、訪問を再帰的に行うには各再帰にこのvisited_verticesを渡さねばなりませんので、引数を改造します。

コード:

int numberOfMarkedNeighbors(Vertex v, Set<Vertex> visited_vertices)

そして、visited_vertices.contains(v)のように、要素が訪問済みかどうかを調べます。