深さ優先探索のアルゴリズムをC++で

C++でグラフをごにょごにょするようなものは昔書いてたんだけど、Rubyで書いたやつのほうがすっきり書けたので書き直してみた。

#include <string>
#include <set>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

class Graph
{
public:
  Graph(){
  };
  virtual ~Graph(){
  };
  void addVertex(string v) {
	vertices.insert( v );
  }
  
  void setWeight(string v, string w, int weight) {
	addVertex(v);
	addVertex(w);
	weights[v][w] = weight;
  }

  bool isAdjacent(string v, string w) {
	map<string, map<string, int> >::iterator it = weights.find(v);
	while (it != weights.end()) {
	  if ( (*it).second.find(w) != (*it).second.end() ) {
		return true;
	  } else {
		return false;
	  }
	  ++it;
	}
	return false;
  }
  
  set<string> getVertices() {
	return vertices;
  }

  void eachVertices(void (*func)(string v)) {
	for (set<string>::iterator it = vertices.begin(); it != vertices.end(); ++it) {
		func((*it));
	}
  }

  void eachSuccessingVertex(string v, void (*func)(string v, string w, int weight)) {
	// vから出ている枝とその枝のウエイトを関数に投げる
	for (set<string>::iterator it = vertices.begin(); it != vertices.end(); ++it) {
	  if ( isAdjacent(v,*it) ) {
		func(v, (*it), weights[v][*it]);
	  }
	}
  }

  vector<string> breadthFirstSearch(string s, vector<string> *hasApproached = new vector<string>, int indent = 0) {
	for (int i = 0; i < indent; ++i) {
	  cout << " ";
	}
	cout << s << endl;

	(*hasApproached).push_back(s);
	for (map<string, int>::iterator it = weights[s].begin(); it != weights[s].end(); ++it){
	  if ( find((*hasApproached).begin(), (*hasApproached).end(), (*it).first) == (*hasApproached).end() ) {
		// 出て行った先のnodeがhasApproachedの中になかったら、再帰する
		breadthFirstSearch((*it).first, hasApproached, indent+1);
	  }
	}
	return *hasApproached;
  }

private:
  set<string> vertices;
  map<string, map<string, int> > weights;
};

void printVertices(string v) {
  cout << " " << v << " ";
}

void printWeights(string v, string w, int weight) {
  cout << v << " -> " << w << " : "  << weight << endl;
}


int main(int argc, char *argv[]) {
  Graph g;
  g.setWeight("0", "1", 1);
  g.setWeight("1", "3", 2);
  g.setWeight("1", "4", 4);
  g.setWeight("1", "0", 4);
  g.setWeight("2", "3", 4);
  g.setWeight("4", "2", 4);
  g.setWeight("5", "2", 4);
  g.setWeight("3", "5", 4);

  cout << "All of vertices are [";
  g.eachVertices(printVertices);
  cout << "]." << endl;
  
  cout << "Information of vertices and weights are as following : " << endl;

  set<string> vertices = g.getVertices();
  for (set<string>::iterator it = vertices.begin(); it != vertices.end(); ++it){
	g.eachSuccessingVertex(*it, printWeights);
  }

  cout << "Result of depth first search is as following : " << endl;

  for (set<string>::iterator it = vertices.begin(); it != vertices.end(); ++it){
	g.breadthFirstSearch(*it);
  }
  return 0;
}

実行結果。

/tmp% ./a.out
All of vertices are [ 0  1  2  3  4  5 ].
Information of vertices and weights are as following : 
0 -> 1 : 1
1 -> 0 : 4
1 -> 3 : 2
1 -> 4 : 4
2 -> 3 : 4
3 -> 5 : 4
4 -> 2 : 4
5 -> 2 : 4
Result of depth first search is as following : 
0
 1
  3
   5
    2
  4
1
 0
 3
  5
   2
 4
2
 3
  5
3
 5
  2
4
 2
  3
   5
5
 2
  3