graph.h

金元平 数据结构 答案

#ifndef GRAPH_H
#define GRAPH_H

#include <list>
#include <iostream>
using namespace std;

class Graph
{
public:
	void test();
	void depthFirstSearch();

private:
	list<int>* headNodes;
	int n;
	bool* visited;
	void DFS(int v);
};


void Graph::test()
{
// This function created a graph of 8 vertexes for test
	n = 8;
	headNodes = new list<int>[8];
	headNodes[0].insert(headNodes[0].end(), 1);
	headNodes[0].insert(headNodes[0].end(), 2);

	headNodes[1].insert(headNodes[1].end(), 0);
	headNodes[1].insert(headNodes[1].end(), 3);
	headNodes[1].insert(headNodes[1].end(), 4);

	headNodes[2].insert(headNodes[2].end(), 0);
	headNodes[2].insert(headNodes[2].end(), 5);
	headNodes[2].insert(headNodes[2].end(), 6);

	headNodes[3].insert(headNodes[3].end(), 1);
	headNodes[3].insert(headNodes[3].end(), 7);

	headNodes[4].insert(headNodes[4].end(), 1);
	headNodes[4].insert(headNodes[4].end(), 7);

	headNodes[5].insert(headNodes[5].end(), 2);
	headNodes[5].insert(headNodes[5].end(), 7);

	headNodes[6].insert(headNodes[6].end(), 2);
	headNodes[6].insert(headNodes[6].end(), 7);

	headNodes[7].insert(headNodes[7].end(), 3);
	headNodes[7].insert(headNodes[7].end(), 4);
	headNodes[7].insert(headNodes[7].end(), 5);
	headNodes[7].insert(headNodes[7].end(), 6);

}

void Graph::depthFirstSearch()
{
	visited = new bool[n];
	for (int i=0; i<n; i++)
		visited[i] = false;
	DFS(0);
	delete []visited;
}

void Graph::DFS(int v)
{
	cout<<v<<endl;
	visited[v] = true;
	for ( list<int>::iterator i=headNodes[v].begin(); i!=headNodes[v].end(); ++i )
	{
		if (!visited[*i])
			DFS(*i);
		else
			cout<<'('<<*i<<')';
	}
}


//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

#endif