C++之笔试题基础45 网易：笔试，盘古游戏：道路村庄

 

 

深度优先

深度优先遍历，从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

我们从这里可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。

具体算法表述如下：

1. 访问初始结点v，并标记结点v为已访问。

2. 查找结点v的第一个邻接结点w。

3. 若w存在，则继续执行4，否则算法结束。

4. 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。

5. 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。

例如下图，其深度优先遍历顺序为 1->2->4->8->5->3->6->7

// strides.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>

using namespace std;
const int maxn = 1e3 + 7;//1007，常量。

//生成一个E[maxn]的数组，每一个数组元素，为vector<int>，
	vector<int> E[maxn];
	//vector<int>表示一个数组
	//vector<int> E[maxn];//表示生成一个的二维数组E[maxn][动态一维数组]
	//表示最多有1006行，n列
	//E[0].push_back(01);
	//E[0].push_back(02);
	//E[1].push_back(11);
	//cout << E[0].size() << endl;  //2
	//cout << E[1].size() << endl;  //1

	//cout << E[0][0] << endl;//1
	//cout << E[0][1] << endl;//2
	//cout << E[1][0] << endl;//11

//n村庄的数量，m道路的数量。
int n, m;

//vis数组，大小maxn;
int vis[maxn];//表示村庄是否被访问，即有路

int cnt = 0;//道路数量

//遍历第x村庄
void dfs(int x){
	vis[x] = 1;//x村庄已经被访问，标志，该村庄有路
	for (int i = 0; i<E[x].size(); i++){
		if (!vis[E[x][i]])//x村庄到i村庄=false，
			dfs(E[x][i]);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{

	cout << maxn << endl;

	cin >> n >> m;
	//m行，道路联通的村庄
	for (int i = 0; i<m; i++){
		int a, b;//村庄，编号
		cin >> a >> b;
		E[a].push_back(b);//a村庄连着b
		E[b].push_back(a);//b村庄连着a
	}

	//n个村庄，依次遍历。
	for (int i = 1; i <= n; i++){
		if (!vis[i]){//vis[i]=False,表示没有访问，则需要修道路。
			cnt++;
			dfs(i);//从i往下找
		}
	}
	cout << cnt - 1 << endl;

	system("pause");
	return 0;
}