# 深さ優先探索のアルゴリズムを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) {
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の中になかったら、再帰する
}
}
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){
}
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