1 数据文件如下

0 5
2 4
2 3
1 2
0 1
3 4
3 5
0 2

2 C++实现DFS算法

Graph.h

/*
 * Graph.h
 *
 *  Created on: 2014年5月17日
 *      Author: zhongchao
 */

#ifndef _GRAPH_
#define _GRAPH_
#include <fstream>
#include <iostream>
#include <ext/hash_map>
#include <hash_set>
#include <map>
#include<limits>
#include <stdio.h>
#include <string.h>
#include <vector>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
using namespace __gnu_cxx;

class Graph
{
private:
		hash_map<int, vector<int> > adj;
		hash_set<int> nodes;
		int _v; //节点的个数
		int _e; //边的条数
public:
		Graph(string path);
		void addEdge(int a, int b);
		vector<int> getEdges(int n);
		hash_set<int> getNodes();
		int v(); //节点的个数
		int e(); //边的个数
};
//----------------------------------------------------------------------
#endif /* _GRAPH_*/

Graph.cpp

/*
 * Graph.cpp
 *
 *  Created on: 2014年5月17日
 *      Author: zhongchao
 */
#include "Graph.h"

Graph::Graph(string path): _v(0), _e(0)
{

		ifstream reader(path.c_str(), ios::in);
		if(reader.is_open())
		{
				while(reader.eof() != EOF)
				{
						int a, b;
						reader>>a>>b;
						_e++;
						if(reader.fail())
								break;
						addEdge(a, b);
						nodes.insert(a);
						nodes.insert(b);
				}
		}
}

void Graph::addEdge(int a, int b)
{
		hash_map<int, vector<int> >::iterator it = adj.find(a);
		if(it == adj.end())
		{
				vector<int> tmp;
				tmp.push_back(b);
				adj.insert(pair<int, vector<int> >(a, tmp));
		}
		else
		{
				it->second.push_back(b);
		}

		it = adj.find(b);
		if(it == adj.end())
		{
				vector<int> tmp;
				tmp.push_back(a);
				adj.insert(pair<int, vector<int> >(b, tmp));
		}
		else
		{
				it->second.push_back(a);
		}
}
int Graph::v()
{
		return nodes.size();
}

vector<int> Graph::getEdges(int n)
{
		return adj.find(n)->second;
}
hash_set<int> Graph::getNodes()
{
		return nodes;
}

BFS.h

/*
 * BFS.h
 *
 *  Created on: 2014年6月2日
 *      Author: zhongchao
 */

#ifndef _BFS_
#define _BFS_
#include "Graph.h"

void bfsTtest();

class BFS
{
private:
		bool* mark;
		int* edgeTo;
		int startNode;
		Graph* _graph;
		vector<int> pq;
public:
		BFS(Graph* graph, int n);
		~BFS();
		void bfs(Graph* graph, int n);
		bool hasPathTo(int n);
		vector<int> pathTo(int n);
		void printPaths();

};
#endif /* _BFS_ */

BFS.cpp

/*
 * BFS.cpp
 *
 *  Created on: 2014年6月2日
 *      Author: zhongchao
 */

/*
 * DFS.cpp
 *
 *  Created on: 2014年6月1日
 *      Author: zhongchao
 */
#include "BFS.h"


BFS::BFS(Graph* graph, int n): _graph(graph),startNode(n)
{
		mark = new bool[graph->v()];
		edgeTo = new int[graph->v()];
		bfs(graph, n);
}

void BFS::bfs(Graph* graph, int n)
{
		mark[n] = true;
		pq.push_back(n);
		while(pq.size() > 0)
		{
				int preN = *(pq.begin());
				pq.erase(pq.begin());
				vector<int> ns = graph->getEdges(preN);
				for(vector<int>::iterator it = ns.begin(); it != ns.end(); it++)
				{
						if(mark[*it] == true) continue;
						edgeTo[*it] = preN;
						pq.push_back(*it);
						mark[*it] = true;
				}
		}
}
bool BFS::hasPathTo(int n)
{
		return mark[n];
}
vector<int> BFS::pathTo(int n)
{
		vector<int> tmp;
		if(hasPathTo(n) == true)
		{
				tmp.push_back(n);
				int  s = edgeTo[n];
				tmp.push_back(s);
				while(s != startNode)
				{
						s= edgeTo[s];
						tmp.push_back(s);
				}
				//tmp.push_back(startNode);
				return tmp;
		}
		else
				return tmp;
}
void BFS::printPaths()
{
		for(int i = 0; i < _graph->v(); i++)
		{
				cout<<i<<"    "<<edgeTo[i]<<endl;
		}

		hash_set<int> nodes = _graph->getNodes();
		for(hash_set<int>::iterator it = nodes.begin(); it != nodes.end(); it++)
		{
				int n = *it;
				if(n == startNode) continue;
				if(hasPathTo(n) == true)
				{
						char str[250];
						vector<int> edges = pathTo(n);
						string p = "";
						for(vector<int>::reverse_iterator it1 = edges.rbegin(); it1 != edges.rend(); it1++)
						{
							sprintf(str, "%d", *it1);
							p += string(str)+"->";
							//cout<<*it1<<"->";
						}
						cout<<p<<"end"<<endl;
				}
		}
}
BFS::~BFS()
{
		delete[] mark;
		delete[] edgeTo;
}
void bfsTest()
{
		string path("/home/zhongchao/worksapce/cpp/ComputeAlgorithms/data/tinyCG.txt");
		Graph* graph = new Graph(path);
		int n = 0;
		BFS* bfs = new BFS(graph, n);
		bfs->printPaths();
}

#include "DFS.h"
void bfsTest();
int main(int argc, char** argv)
{
		bfsTest();
		return 1;
}

遍历的路径如下
0->1->end
0->2->end
0->5->3->end
0->5->3->4->end
0->5->end