服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++深度优先搜索的实现方法

C++深度优先搜索的实现方法

2021-01-28 14:50C++教程网 C/C++

这篇文章主要介绍了C++深度优先搜索的实现方法,是数据结构中非常重要的一种算法,需要的朋友可以参考下

本文实例讲述了图的遍历中深度优先搜索C++实现方法,是一种非常重要的算法,具体实现方法如下:

首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历。图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search)。

一、深度优先搜索(DFS)的算法思想

深度优先搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想就是:首先访问图中某一起始顶点v,然后由v出发,访问与v邻接且未被访问的任一顶点w1,再访问与w1邻接且未被访问的任一顶点w2,……重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直到图中所有顶点均被访问过为止。

C++深度优先搜索的实现方法

如上图所示,从顶点2开始深度优先遍历图,结果为:2,0,1,3。

二、DFS算法实现

和广度优先搜索一样,为了防止顶点被多次访问,需要使用一个访问标记数组visited[]来标记顶点是否已经被访问过。

这里使用邻接表表示图。对于一个有向图,假设从给定顶点可以访问到图的所有其他顶点,则DFS递归算法的C++代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*************************************************************************
  > File Name: DFS.cpp
  > Author: SongLee
 ************************************************************************/
#include<iostream>
#include<list>
using namespace std;
 
/* 图 */
class Graph
{
  int V;                // 顶点数
  list<int> *adj;           // 邻接表
  void DFSUtil(int v, bool visited[]); // 从顶点v深度优先遍历
public:
  Graph(int V);            // 构造函数
  void addEdge(int v, int w);     // 向图中添加边
  void DFS(int v);           // 从v开始深度优先遍历图
};
 
/* 构造函数 */
Graph::Graph(int V)
{
  this->V = V;
  adj = new list<int>[V];
}
 
/* 添加边,构造邻接表 */
void Graph::addEdge(int v, int w)
{
  adj[v].push_back(w);         // 将w添加到v的链表
}
 
/* 从v开始深度优先遍历 */
void Graph::DFSUtil(int v, bool visited[])
{
  // 访问顶点v并输出
  visited[v] = true;
  cout << v << " ";
 
  list<int>::iterator i;
 
  for(i=adj[v].begin(); i!=adj[v].end(); ++i)
    if(!visited[*i])       // 若邻接点尚未访问
      DFSUtil(*i, visited);   // 递归
}
 
/* 对图进行深度优先遍历,调用递归函数DFSUtil() */
void Graph::DFS(int v)
{
  bool *visited = new bool[V];
  for(int i=0; i<V; ++i)
    visited[i] = false;
 
  // 假设从给定顶点v可以到达图的所有顶点
  DFSUtil(v, visited);
}
 
/* 测试 */
int main()
{
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);
 
  cout << "Depth First Traversal (starting from vertex 2) \n";
  g.DFS(2);
  cout << endl;
   
  return 0;
}

上面的代码是假设从给定顶点可以访问到图的所有其他顶点。如果没有这个假设,为了对图作一个完整的深度优先遍历,我们需要对每个顶点调用DFSUtil()。当然那之前需要先检查顶点是否已经访问过。所以我们只需要修改DFS()函数部分:

?
1
2
3
4
5
6
7
8
9
10
11
void Graph::DFS()
{
  bool *visited = new bool[V];
  for(int i=0; i<V; ++i)
    visited[i] = false;
   
  // 对每个顶点调用DFSUtil(),从0开始
  for(int i=0; i<V; ++i)
    if(!visited[i])
      DFSUtil(i, visited);
}

对于无向图的深度优先搜索,只是邻接表不一样,其他的都是一样的。我们只需要修改addEdge(v, w)函数:

?
1
2
3
4
5
void Graph::addEdge(int v, int w)
{
  adj[v].push_back(w);     // 将w加到v的list
  adj[w].push_back(v);
}

注意:图的邻接矩阵表示是唯一的,但对于邻接表来说,如果边的输入次序不同,生成的邻接表也不同。因此,对于同一个图,基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的,基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

三、DFS算法性能分析

1 . 空间复杂度

DFS算法是一个递归算法,需要借助一个递归工作栈,故它的空间复杂度为O(|V|)。

2 . 时间复杂度

当以邻接表存储时,时间复杂度为O(|V|+|E|)。

当以邻接矩阵存储时,时间复杂度为O(|V|^2)。

延伸 · 阅读

精彩推荐
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20