数据结构——图的深度优先遍历（DFS）

　　本文内图的存储方式是邻接矩阵。

　　ＤFS的遍历方法可以类比树的先序遍历。

　　在实现树的先序遍历时，遍历顺序是  根 子树 下一个子树 ...

　　而DFS的实现方法是优先深度，与一个树按照先序遍历的顺序相同。

　　所以在实现DFS之前，需要先学习   寻找第一个邻接点（FirstNeighbor）与 寻找下一个邻接点（NextNeighbor） 如何实现

　　这个在之前的实现广度优先遍历里有过分享，这里就不再赘述。我们就直奔主题。

BFS的实现

　　图的深度优先遍历类比树的先序遍历。采取的遍历顺序为  结点 子节点 下一个子节点 ...

　　我们可以采用递归的方法访问树的子树，那么也可以相同的方法进行图的深度优先遍历（DFS）

　　不同的是我们需要设立一个 bool 变量 IsData 来进行判断，判断该变量是否被遍历过

　　利用 for 循环和 if 判断来进行条件的筛选

　　最后得到代码：

//DFS
void DFS(Adj_Matrix& q, char a)
{
	int m = find(q, a);
	if (m == -1)
		return;
	
	visit(q, m);
	q.IsData[m] = false;
	
	for (int i = FirstNeighbor(q, a); i > 0; i = NextNeighbor(q, a, i))
	{
		
		if (q.IsData[i])
		{
			DFS(q, q.data[i]);
		}

	}
}

　　同样的，也需要考虑图为非连通图的情况，所以利用 for 循环对每一个连通分量进行遍历。

　　最终得代码：

//非连通图DFS
void DFSTraverse(Adj_Matrix& q)
{
	for (int i = 0; i < q.NumData; i++)
		q.IsData[i] = true;

	for (int i = 0; i < q.NumData; i++)
		if (q.IsData[i])
			DFS(q, q.data[i]);
}

完整代码：

#include <iostream>
using namespace std;
#define MAX 10

//邻接矩阵
typedef struct Adj_Matrix
{
	//结点
	char data[MAX];

	//边
	int edge[MAX][MAX];

	//结点数
	int NumData, NumEdge;

	//判断结点有无被遍历
	bool IsData[MAX];

}Adj_Matrix;

//初始化
void InitAdj(Adj_Matrix& q)
{
	for (int i = 0; i < MAX; i++)
		q.IsData[i] = true;
	q.NumData = 0;
	q.NumEdge = 0;
}

//寻找位置
int find(Adj_Matrix q, char a)
{
	for (int i = 0; i < q.NumData; i++)
		if (q.data[i] == a)
			return i;
	return -1;
}

//寻找第一个临界点
int FirstNeighbor(Adj_Matrix q, char a)
{
	int m = find(q, a);
	if (m == -1)
		return -1;

	for (int i = 1; i <= q.NumData; i++)
		if (q.edge[m][i] == 1)
			return i;
	return -1;
}

//寻找下一个临界点
int NextNeighbor(Adj_Matrix q, char a, char b)
{
	int m = find(q, a);
	if (m == -1)
		return -1;

	int n = find(q, b);
	if (n == -1)
		return -1;

	for (int i = n + 1; i <= q.NumData; i++)
		if (q.edge[m][i] == 1)
			return i;

	return -1;
}

//遍历函数
void visit(Adj_Matrix q, int i)
{
	cout << q.data[i] << " ";
}

//DFS
void DFS(Adj_Matrix& q, char a)
{
	int m = find(q, a);
	if (m == -1)
		return;
	
	visit(q, m);
	q.IsData[m] = false;
	
	for (int i = FirstNeighbor(q, a); i > 0; i = NextNeighbor(q, a, i))
	{
		
		if (q.IsData[i])
		{
			DFS(q, q.data[i]);
		}

	}
}

//非连通图DFS
void DFSTraverse(Adj_Matrix& q)
{
	for (int i = 0; i < q.NumData; i++)
		q.IsData[i] = true;

	for (int i = 0; i < q.NumData; i++)
		if (q.IsData[i])
			DFS(q, q.data[i]);
}


int main()
{
	Adj_Matrix q;
	int j = 97;
	for (int i = 0; i < 4; i++, j++)
	{
		q.data[i] = (char)j;
	}
	q.edge[0][2] = q.edge[2][0] = q.edge[1][3] = q.edge[3][1] = q.edge[2][3] = q.edge[3][2] = 1;
	q.NumData = 4;
	q.NumEdge = 3;

	DFS(q, q.data[0]);
	cout << endl;
	DFSTraverse(q);

	return 0;
}