【数据结构与算法】图的遍历（深度优先遍历DFS算法）

1.1深度优先遍历

 深度优先遍历（depth first search），也有称为深度优先搜索简称DFS。它的主要思想就是例如找钥匙一样。例如：我们的一把车钥匙被搞丢了但是可以确定的是它一定就在家里的某个位置，所以我们需要从房间开始寻找，可是我们是该在房间某一处寻找还是将一整个房间搜索完之后再找其他房间的地方呢？在深度优先遍历意思就是将一个房间的所有地方搜索完之后再进行其他房间的搜索，直至找到车钥匙为止。

假设你现在需要完成一个任务，要知道你在如下迷宫中，从顶点A开始要走遍所有图中的顶点并作上标记，注意不是简单地看着这样的平面图走，而是如同现实般在迷宫之中去完成任务。

很显然对这种图的遍历我们需要一种策略，否则在这个四通八达的道路里很容易迷失方向，要想完成任务那就只能靠运气。如果看完这篇文章对深度优先遍历有一定的了解之后，这个任务就不难完成。

首先我们从A点开始，做上表示走过的记号之后，面前就有两条路，通向B和F，我们给自己定一个原则，在没有碰到重复的顶点的情况下，始终是向右手边走，于是我们就走到了B顶点。整个路径的过程可以参考下图，此时会遇到三个岔路口，通向C、I、G，右手通行我们走到了C顶点。就这样一直走到F顶点之后当我们发现下一个便回到了A顶点之后，此时在F顶点，走右手倒数第二个通道走到了G顶点，又遇到了三个路，但是发现B、D已经走过了所以走到了H顶点，到H处时我们遇到了两个都走过的路口，但是我们清楚的知道该图我们还没有遍历完成，所以我们一路从H退到G、F、E、D顶点，到了D顶点发现I没有走过所以走到I，就完成了这个任务。

 

其实从上面的叙述来说，深度优先遍历就是一个递归的过程，如果在仔细一点你会发现它就像是一棵树的前序遍历。它从图中的某个顶点V出发，访问该顶点，然后从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到。

邻接矩阵的深度遍历的代码如下所示：

int visited[10]; 
//邻接矩阵的深度优先递归算法
void DFS(struct photo* G, int i)        //访问标志的数组
{
	int j;
	visited[i] = 1;
	cout << G->vex[i]<<" ";        //打印结点的内容
	for (j = 0; j < G->numnodes; j++)
	{
		if (G->arc[i][j] == 1 && visited[j] == 0)    //对未被访问的结点进行递归
			DFS(G, j);
	}
}
//邻接矩阵的深度遍历操作
void DFStraverse(struct photo* G)
{
	int i;
	for (i = 0; i < G->numnodes; i++)
		visited[i] = 0;        //初始化标志数组都为被访问
	for (i = 0; i < G->numnodes; i++)
		if (visited[i] == 0)
			DFS(G, i);        //对未被党文的顶点调用DFS
}

整体的可运行代码如下，其中包含如何存储数据：

struct photo
{
	char vex[10];
	int arc[10][10]={0};
	int numnodes, numdges;
};
 
void creategraph(struct photo*G)
{
	cout << "请输入顶点数和边数:" << endl;
	cin >> G->numnodes >> G->numdges;
	for (int i = 0; i < G->numnodes; i++)
		cin >> G->vex[i];
	for (int i = 0; i < G->numnodes; i++)
		for (int j = 0; j < G->numnodes; j++)
			G->arc[i][j] = 0;
	for (int k = 0; k < G->numdges; k++)
	{
		int i, j;
		cout << "请输入有边点数：（i，j）" << endl;
		cin >> i>>j;
		G->arc[i][j] = 1;
		G->arc[j][i] = G->arc[i][j];
	}
}
 
void print(struct photo* G)
{
	for (int i = 0; i < G->numnodes; i++)
	{
		for (int j = 0; j < G->numnodes; j++)
		{
			cout <<setw(2)<< G->arc[i][j] << " ";
		}
		cout << endl;
	}
}
 
int visited[10]; 
void DFS(struct photo* G, int i)
{
	int j;
	visited[i] = 1;
	cout << G->vex[i]<<" ";
	for (j = 0; j < G->numnodes; j++)
	{
		if (G->arc[i][j] == 1 && visited[j] == 0)
			DFS(G, j);
	}
}
 
void DFStraverse(struct photo* G)
{
	int i;
	for (i = 0; i < G->numnodes; i++)
		visited[i] = 0;
	for (i = 0; i < G->numnodes; i++)
		if (visited[i] == 0)
			DFS(G, i);
}
int main()
{
	struct photo* y;
	y = (struct photo*)malloc(sizeof(struct photo));
	creategraph(y);
	print(y);
	DFStraverse(y);
	return 0;
}

大致的运行结果如下，可以根据上面所述的推论可以对我在下图中所输入的数据进行一个推演，主要是观察并且熟练这个思路：

邻接表的代码其中DFStraverse函数的代码几乎是完全一模一样的，只是在递归函数中因为将存储的结构从数组换成了链表所以变的不同。

如下是邻接表的深度遍历的代码：

 

int visited[10];
void DFS(nodes* G, int i)
{
	struct dege* e;
	visited[i] = 1;
	cout << G->adj[i].data<<" ";
	e = G->adj[i].first;
	while (e)
	{
		if (visited[e->adv] == 0)
			DFS(G, e->adv);
		e = e->next;
	}
}
void DFStraverse(nodes* G)
{
	for (int i = 0; i < G->numnodes; i++)
		visited[i] = 0;
	for (int i = 0; i < G->numnodes; i++)
		if (visited[i] == 0)
			DFS(G, i);
}

完整的邻接表的创建以及深度优先遍历的代码如下所示：

struct dege
{
	int adv;
	struct dege* next;
};
 
typedef struct vex
{
	char data;
	struct dege* first;
}adjlist[100];
 
struct nodes
{
	adjlist adj;
	int numnodes, numedges;
};
 
void create(struct nodes* G)
{
	struct dege* e;
	cout << "请输入顶点数目和边的数目：" << endl;
	cin >> G->numnodes >> G->numedges;
	for (int i = 0; i < G->numnodes; i++)
	{
		cin >> G->adj[i].data;
		G->adj[i].first = NULL;
	}
	for (int k = 0; k < G->numedges; k++)
	{
		cout << "请输入有边的结点i,j:" << endl;
		int i, j;
		cin >> i >> j;
		e = (struct dege*)malloc(sizeof(struct dege));
		e->adv = j;
		e->next = G->adj[i].first;
		G->adj[i].first = e;
		e = (struct dege*)malloc(sizeof(struct dege));
		e->adv = i;
		e->next = G->adj[j].first;
		G->adj[j].first = e;
	}
}
 
int visited[10];
void DFS(nodes* G, int i)
{
	struct dege* e;
	visited[i] = 1;
	cout << G->adj[i].data<<" ";
	e = G->adj[i].first;
	while (e)
	{
		if (visited[e->adv] == 0)
			DFS(G, e->adv);
		e = e->next;
	}
}
void DFStraverse(nodes* G)
{
	for (int i = 0; i < G->numnodes; i++)
		visited[i] = 0;
	for (int i = 0; i < G->numnodes; i++)
		if (visited[i] == 0)
			DFS(G, i);
}
int main()
{
	struct nodes* S;
	S = (struct nodes*)malloc(sizeof(struct nodes));
	create(S);
	DFStraverse(S);
	return 0;
}

最终的运行结果如下所示：

这几天有一些迷茫，主要因为期中考试复习有些打乱了我自己的复习计划。

很喜欢一句话：少年不望登高，但求平安健康。