[数据结构与算法]DFS深度优先遍历

所谓DFS就是指：优先考虑深度，换句话说就是一条路走到黑，直到无路可走的情况下，才会选择回头，然后重新选择一条路。

图的节点结构

1.点集（包含图里面所有的点）

2.边集（邻接矩阵，点与点之间是否可达）

3.点的数目

4.边的数目

初始化图

除了初始化图自己，还有分配堆空间，因为节点结构里面有一维数组和二维数组；

那就涉及到一位数组和二维数组的动态分配；点的数目由传入的个数决定，边的数目初始化为0

创建图

创建的过程其实也是遍历的过程，在循环之中将点赋值给图的点集，将邻接矩阵的值赋给边集；并且判断点与点之间是否可达，若可达，则边的数目++；因为我们目前研究的是无向图，所以会存在点1到点2可达，则点2到点1也可达，就会重复记录边的数目，则边的数目最后需要减半处理

DFS

先访问该元素，再在visited数组里面标识它已经访问过了，再进入循环判断当前这个元素的那一行的下一个元素，与当前的节点是否有边，是否被访问过了，若有边，且没有被访问，则进行对当前下标的DFS访问，即递归

#include<iostream>
#include<string.h>
using namespace std;
typedef struct Graph
{
	char* spot;//点集
	int** line;//邻接矩阵
	int spotNum;
	int lineNum;
}Graph;
Graph* initGraph(int dianNumber)
{
	Graph* T = new Graph;
	T->spot = new char[dianNumber];//创建长度为dianNumber的点集
	T->line = new int*[dianNumber];//创建一个二维数组的第一列，长度为dianNumber
	for (int i = 0; i < dianNumber; i++)
	{
		T->line[i] = new int[dianNumber];
	}
	T->spotNum = dianNumber;
	T->lineNum = 0;//初始边的数目为0
	return T;
}
void createGraph(Graph* T, const char* dian, int* bian)
{
	for (int i = 0; i < T->spotNum; i++)
	{
		T->spot[i] = dian[i];
		for (int j = 0; j < T->spotNum; j++)
		{
			T->line[i][j] = *(bian + i * T->spotNum + j);//一次移动一行
			if (T->line[i][j] != 0)
			{
				T->lineNum++;
			}
		}
	}
	T->lineNum /= 2;
}
void visit(Graph*T,int index)
{
	cout << T->spot[index] << " ";
}
void DFS(Graph* T, int* visited, int index)
{
	visit(T, index);
	visited[index] = 1;
	for (int i = 0; i < T->spotNum; i++)
	{
		if (T->line[index][i] == 1 && !visited[i])//如果矩阵有边，并且没有被访问过
		{
			DFS(T, visited, i);
		}
	}
}

int main()
{
	char array[] = {'A','B','C','D','E'};
	int num = sizeof(array) / sizeof(char);
	Graph* G = initGraph(num);
	int bian[] = { 0,1,1,1,0,1,0,1,1,1,1,1,0,0,0,1,1,0,0,1,0,1,0,1,0 };
	int dianNumber = G->spotNum;
	int* visited = new int[dianNumber];
	memset(visited, 0, dianNumber * sizeof(visited));
	createGraph(G, array, bian);
	DFS(G, visited, 0);//ABCDE为DFS的遍历结果
	cout << endl;
}