hnsfdxyc

用户名：00000152

访问量：24623

签　名：

等　　级
排　　名	362
经　　验	5240
参赛次数	0
文章发表	24
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

树了解一下（c++）
浏览：362

图的深度优先遍历
浏览：314

你可能喜欢

图的深度优先遍历

　　作者: hnsfdxyc　　　　发表时间：2019-08-09 13:42:53 浏览：314　|　评论：0　

### 深度优先搜索遍历过程

------------

图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。

#### 思想：
假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索**是一个递归的过程**

#### 特点：
选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。
**具体点，**给定一图G=<V,E>，用visited[i]表示顶点i的访问情况，则初始情况下所有的visited[i]都为false。假设从顶点V0开始遍历，则下一个遍历的顶点是V0的第一个邻接点Vi，接着遍历Vi的第一个邻接点Vj，……直到所有的顶点都被访问过。

所谓的第一个是指在某种存储结构中(邻接矩阵、邻接表)，所有邻接点中存储位置最近的，通常指的是下标最小的。在遍历的过程中有两种情况经常出现
    某个顶点的邻接点都已被访问过的情况，此时需回溯已访问过的顶点。
    图不连通，所有的已访问过的顶点都已回溯完了，仍找不出未被访问的顶点。此时需从下标0开始检测visited[i]，找到未被访问的顶点i，从i开始新一轮的深度搜索。

#### 看一个例子

从V0开始遍历
遍历分析：V0有两个邻接点V1和V2，选择下标最小的V1遍历。接着从V1开始深度遍历，V1只有邻接点V3，也就是没有选的：遍历V3。接着从V3开始遍历，V3只有邻接点V0，而V0已经被遍历过。此时出现了上面提到的情况一，开始回溯V1，V1无未被遍历的邻接点，接着回溯V0，V0有一个未被遍历的邻接点V2，新的一轮深度遍历从V2开始。V2无邻接点，且无法回溯。此时出现了情况二，检测VISITED[I]，只有V4了。深度遍历完成。看到回溯，应该可以想到需要使用栈。
遍历序列是
V0->V1->V3->V2->V4。
从其它顶点出发的深度优先遍历序列是：
V1->V3->V0->V2->V4。
V2->V0->V1->V3->V4。
V3->V0->V1->V2->V4。
V4->V2->V0->V1->V3。
以上结果，我们稍后用于测试程序。

结合在图的实现：邻接矩阵中的代码，我们看下在邻接矩阵形式下的图的深度遍历算法：
深度优先代码
```cpp
/*
深度优先搜索
从vertex开始遍历，visit是遍历顶点的函数指针
*/
void Graph::dfs(int vertex, void (*visit)(int))
{
	stack<int> s;
	//visited[i]用于标记顶点i是否被访问过
	bool *visited = new bool[numV];
	//count用于统计已遍历过的顶点数
	int i, count;
	for (i = 0; i < numV; i++)
		visited[i] = false;
	count = 0;
	while (count < numV)
	{
		visit(vertex);
		visited[vertex] = true;
		s.push(vertex);
		count++;
		if (count == numV)
			break;
		while (visited[vertex])
		{
			for (i = 0; i < numV
				&& (visited[i] 
				|| matrix[vertex][i] == 0 || matrix[vertex][i] == MAXWEIGHT); i++);
			if (i == numV)  //当前顶点vertex的所有邻接点都已访问完了
			{
				if (!s.empty())
				{
					s.pop();   //此时vertex正是栈顶，应先出栈
					if (!s.empty())
					{
						vertex = s.top();
						s.pop();
					}
					else  //若栈已空，则需从头开始寻找新的、未访问过的顶点
					{
						for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
					}
				}
				else  //若栈已空，则需从头开始寻找新的、未访问过的顶点
				{
					for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
				}
			}
			else  //找到新的顶点应更新当前访问的顶点vertex
				vertex = i;
		}
	}
	delete[]visited;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

hnsfdxyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

Pascal三角（Java代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-舍罕王的失算（C语言代码）

图的深度优先遍历

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

WU-整数平均值（C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

出圈】指针malloc版

C二级辅导-统计字符（C语言代码）

勾股数（C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

hnsfdxyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

Pascal三角 （Java代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-舍罕王的失算 （C语言代码）

图的深度优先遍历

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

WU-整数平均值 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

出圈】指针malloc版

C二级辅导-统计字符 （C语言代码）

勾股数 （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

Pascal三角（Java代码）

Tom数（C语言代码）

C语言训练-舍罕王的失算（C语言代码）

　　评论区

WU-整数平均值（C++代码）

母牛的故事（C语言代码）

C二级辅导-统计字符（C语言代码）

勾股数（C语言代码）