图的遍历（DFS）

void Graph::DFS(int v)
{
	//当前节点被访问过的标志
	visit[v] = 1;
	//访问当前节点
	cout << vertex[v] << endl;
	//对顶点在边表中该行的所有边关系进行遍历，如果==1表示是邻接点，并且还要判断当前顶点是否被访问过
	for (int i = 0; i < vertexNum; i++)
	{
		if (arc[v][i] == 1 && visit[i]==0)
		{
			DFS(i); //如果满足条件，就从该顶点开始再次进行DFS操作
		}
	}
}

void Graph::DFSTraverse()
{
	//遍历所有顶点
	for (int i = 0; i < vertexNum; i++)
	{
		//这里我们决定把顶点数组中第一个元素当做遍历起点
		if (visit[i] == 0)//如果当前顶点处于未被访问的状态，就对该顶点进行DFS操作
		{
			//DFS函数是对当前传入的顶点以及它的未被遍历过的邻接点进行递归遍历输出操作
			//当当前顶点和邻接点都被遍历完成后，弧退出DFS函数，进入当前for循环
			//这里的for循环相当于对每一个顶点都进行判断，看其是否被遍历过，防止漏网之鱼
			DFS(i);
		}
	}
}

#include<iostream>
using namespace std;
const int MAX = 10; //图的最大顶点个数为10
typedef char DataType;
class Graph 
{
private:
	//边的个数
	int arcNum;
	//顶点个数
	int vertexNum;
	//定义一个存放顶点的一位数组
	DataType vertex[MAX];
	//定义一个存放顶点间的边关系的二维数组
	int arc[MAX][MAX];
	//访问数组
	int visit[MAX];
public:
	//v[]数组存放用户输入的一维数组的顶点数据，n表示顶点个数，e是边的个数
	Graph(DataType v[], int n, int e);
	//DFS----深度优先递归算法
	void DFS(int v);//v从某个顶点开始进行访问操作---对应顶点数组中的下标位置
    //DFS---深度优先遍历
	void DFSTraverse();
};
//有参构造函数的实现
Graph::Graph(DataType v[], int n, int e)
{
	//初始化顶点个数
	vertexNum = n;
	//初始化边的个数
	arcNum = e;
	//初始化顶点数组
	for (int i = 0; i <n; i++)
	{
		vertex[i] = v[i];
	}
	//初始化边数组
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			arc[i][j] = 0;
	//初始化访问数组
	for (int i = 0; i < MAX; i++)
		visit[i] = 0;//一开始所有节点都处于未被访问的状态

	//由用户来决定，哪两个顶点之间存在边
	int vi=0, vj=0;
	for (int i = 0; i < arcNum; i++)
	{
		cin >> vi >> vj;//输入边依附的两个顶点编号
		//这是无向图的边初始化标志
		arc[vi][vj] = 1;//有边的标志
		arc[vj][vi] = 1;
	}
}
void Graph::DFS(int v)
{
	//当前节点被访问过的标志
	visit[v] = 1;
	//访问当前节点
	cout << vertex[v] << endl;
	//对顶点在边表中该行的所有边关系进行遍历，如果==1表示是邻接点，并且还要判断当前顶点是否被访问过
	for (int i = 0; i < vertexNum; i++)
	{
		if (arc[v][i] == 1 && visit[i]==0)
		{
			DFS(i); //如果满足条件，就从该顶点开始再次进行DFS操作
		}
	}
}
void Graph::DFSTraverse()
{
	//遍历所有顶点
	for (int i = 0; i < vertexNum; i++)
	{
		//这里我们决定把顶点数组中第一个元素当做遍历起点
		if (visit[i] == 0)//如果当前顶点处于未被访问的状态，就对该顶点进行DFS操作
		{
			//DFS函数是对当前传入的顶点以及它的未被遍历过的邻接点进行递归遍历输出操作
			//当当前顶点和邻接点都被遍历完成后，弧退出DFS函数，进入当前for循环
			//这里的for循环相当于对每一个顶点都进行判断，看其是否被遍历过，防止漏网之鱼
			DFS(i);
		}
	}
}
//测试-------------------
void test()
{
	DataType v[5] = { 'a','b','c','d','\0' };
	Graph p(v, 4, 4);
	p.DFSTraverse();
}
int main()
{
	
	test();
	system("pause");
	return 0;
}

//v----从某个顶点开始进行访问
void Graph::DFS(int v)
{
	//设置当前节点被访问过
	visit[v] == 1;
	//输出当前节点的信息
	cout << adjList[v].vertex << endl;
	//遍历当前顶点的边链表
	ArcNode* workNode = adjList[v].firstEdge;
	//当前节点不为空，表示还存在邻接点没有遍历完，并且遍历过程中判断当前邻接点是否被访问过
	while (workNode&&visit[workNode->dajvex]==0)
	{
		workNode = workNode->next;
	}
}

void Graph::DFSTravers()
{
	//遍历所有顶点，确保所有顶点都以及它的邻接点都被访问过，以防漏网之鱼
	for (int i = 0; i < vertexNum; i++)
	{
		if (visit[i] == 0)//当前顶点没有被访问过
		{
			DFS(i);
		}
	}

#include<iostream>
using namespace std;
//邻接链表
typedef char DataType; //顶点的数据类型
//边表结构体
struct ArcNode 
{
	int dajvex;//记录邻接点在数组中的下标
	ArcNode* next;
};
//顶点表结构体
struct VertexNode 
{
	DataType vertex;//顶点结构体的数据
	ArcNode* firstEdge;//相当于头指针，指向边表
};
const int MAX = 10; //图的最大顶点数
class Graph 
{
private:
	VertexNode adjList[MAX];//顶点表结构体数组
	int vertexNum;//顶点数
	int arcNum;//边数
	int visit[MAX];//访问数组
public:
	Graph(DataType v[], int n, int e);
	void DFS(int v);
	void DFSTravers();
};
//构造函数实现:用户传入的顶点结构体数组，里面存放着顶点数据  顶点数  边数
Graph::Graph(DataType v[], int n, int e) 
{
	vertexNum = n;//初始化顶点数
	arcNum = e;//初始化边数
	for (int i = 0; i < vertexNum; i++)
	{
		adjList[i].vertex = v[i]; //将用户传入的顶点数据给顶点结构体数组进行赋值
		adjList[i].firstEdge = NULL;
	}
	//初始化访问数组
	for (int i = 0; i < vertexNum; i++)
		visit[i] = 0;//一开始所有顶点都未被访问过
	//建立边的关系
	for (int i = 0; i < arcNum; i++)
	{
		//输入边的信息存储在边表中
		int vi, vj;                              
		cin >> vi >> vj;//输入边依附两个顶点的编号
		ArcNode* s = new ArcNode;//将边表结构体开辟在堆区
		s->dajvex = vj;//这里是有向图，所以vi--->vj,dajvex存储的值是出度节点在数组中的下标
		//头插法
		s->next = adjList[vi].firstEdge;
		adjList[vi].firstEdge = s;
	}
}
//v----从某个顶点开始进行访问
void Graph::DFS(int v)
{
	//设置当前节点被访问过
	visit[v] == 1;
	//输出当前节点的信息
	cout << adjList[v].vertex << endl;
	//遍历当前顶点的边链表
	ArcNode* workNode = adjList[v].firstEdge;
	//当前节点不为空，表示还存在邻接点没有遍历完，并且遍历过程中判断当前邻接点是否被访问过
	while (workNode&&visit[workNode->dajvex]==0)
	{
		workNode = workNode->next;
	}
}
void Graph::DFSTravers()
{
	//遍历所有顶点，确保所有顶点都以及它的邻接点都被访问过，以防漏网之鱼
	for (int i = 0; i < vertexNum; i++)
	{
		if (visit[i] == 0)//当前顶点没有被访问过
		{
			DFS(i);
		}
	}
}
int main()
{
	DataType v[5] = { 'a','b','c','d','\0' };
	Graph p(v,4,4);
	p.DFSTravers();
	system("pause");
	return 0;
}