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

2024-04-01 11:10:08

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

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

一、深度优先搜索（DFS）的算法思想

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

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

二、DFS算法实现

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

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

/*************************************************************************
  > 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()函数部分：

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)函数：

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++代码解答示例

八皇后问题即指在一个8*8的棋盘上放置8个皇后,不允许任何两个皇后在棋盘的同一行.同一列和同一对角线上.关键字:递归.上溯.通用技巧: 经观察发现,对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7) 其主对角线(即左上至右下)上的每个点的i-j+7的值(范围在(0,14))均相等: 其从对角线(即右上至左下)上的每个点的i+j的值(范围在(0,14))均相等: 且每个主对角线之间的i-j+7的值均不同,每个从对角线之间的i-j+7的值亦不同: 如a[3][4]: 主:3-4+7
C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析

本文实例讲述了C++实现图的邻接矩阵存储和广度.深度优先遍历的方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 1 0 2 1 0 3 1 2 3 1 2 4 1 1 4 1 输入结束(此行不必输入) 注:0 1 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示 0 2 1表示该图的第0个顶点和第2个定点有边相连,如上图中的a
八皇后问题实现代码分享

main.cpp 复制代码代码如下: #include<iostream>#include<cstring> using namespace std; const int N = 7; int count = 0; void QueenPrint(int LayOut[N][N]) //打印结果{ cout<<"第"<<++count<<"种布局:"<<endl; for(int i = 0
8皇后问题的解法实例代码

复制代码代码如下: #include <stdio.h> #define MAX 200#define Empty 0#define Full 1#define N 8 unsigned char qipan[N][N][N]={MAX};//初始化8张棋盘表示每下一步的void input(int i);int count = 0; int main(){ input(0); getchar(); return 0;}void input(int i){ int x
C++实现八皇后问题的方法

本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没
C语言通过深度优先搜索来解电梯问题和N皇后问题的示例

N皇后问题问题描述: 在n×n格的棋盘上放置彼此不受攻击的n个皇后.按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子.n后问题等价于再n×n的棋盘上放置n个皇后,任何2个皇后不妨在同一行或同一列或同一斜线上. 需求输入: 给定棋盘的大小n (n ≤ 13) 需求输出: 输出有多少种放置方法. #include <stdio.h> #include <math.h> #define MAX 101 int total = 0; char m[MAX][MAX
c++递归实现n皇后问题代码(八皇后问题)

还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 扩展到N皇后问题是一样的.一看,似乎要用到二维数组.其实不需要.一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列--应用广泛的小技巧.而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可. 这种思路的实现方式网上大把,包括前面提到的那
深入N皇后问题的两个最高效算法的详解

N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行.同一列.同一斜线上的皇后都会自动攻击).一. 求解N皇后问题是算法中回溯法应用的一个经典案例回溯算法也叫试探法,它是一种系统地搜索问题的解的方法.回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试.在现实中,有很多问题往往需要我们把其所有可能穷举出来,然后从中找出满足某种要求的可能或最优的情况,从而得到整个问题的解.回溯算法就是解决这种问题的"通用算法",有&qu
C语言实现图的遍历之深度优先搜索实例

DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法.分享给大家供大家参考.具体方法如下: #include <iostream> #include <algorithm> #include <iterator> using namespace std; #define MAX_VERTEX_NUM 10 struct Node { int adjvex; struct Node *next; int info; }; typ
C++深度优先搜索的实现方法

本文实例讲述了图的遍历中深度优先搜索的C++实现方法,是一种非常重要的算法,具体实现方法如下: 首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次.注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历.图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search). 一.深度优先搜索(DFS)的算法思想深度优先搜索算法所遵循的搜索策略是尽可能"深&
Java编程实现基于图的深度优先搜索和广度优先搜索完整代码

为了解15puzzle问题,了解了一下深度优先搜索和广度优先搜索.先来讨论一下深度优先搜索(DFS),深度优先的目的就是优先搜索距离起始顶点最远的那些路径,而广度优先搜索则是先搜索距离起始顶点最近的那些路径.我想着深度优先搜索和回溯有什么区别呢?百度一下,说回溯是深搜的一种,区别在于回溯不保留搜索树.那么广度优先搜索(BFS)呢?它有哪些应用呢?答:最短路径,分酒问题,八数码问题等.言归正传,这里笔者用java简单实现了一下广搜和深搜.其中深搜是用图+栈实现的,广搜使用图+队列实现的,代码如下:
python实现全排列代码(回溯、深度优先搜索)

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. 公式:全排列数f(n)=n!(定义0!=1) 1 递归实现全排列(回溯思想) 1.1 思想举个例子,比如你要对a,b,c三个字符进行全排列,那么它的全排列有abc,acb,bac,bca,cba,cab这六种可能就是当指针指向第一个元素a时,它可以是其本身a(即和自己进行交换),还可以和b,c进行交换,故有3种可能,当第一个元素a确定以后,指针移向第二
最短时间学会基于C++实现DFS深度优先搜索

目录前言 1.迷宫找出口,区分dfs,bfs: 一.DFS经典放牌可能组合二.leetcode 员工的重要性三.leetcode 图像渲染四.leetcode 被围绕的区域五.岛屿数量六. 小练习:岛屿的最大面积总结前言同学们肯定或多或少的听到过别人提起过DFS,BFS,却一直都不太了解是什么,其实两个各为搜索算法,常见使用深度优先搜索(DFS) 以及广度优先搜索(BFS) ,今天我们就来讲讲什么是深度优先搜索,深度优先就是撞到了南墙才知道回头,才会往上一层返回. 1.迷宫
python实现提取百度搜索结果的方法

本文实例讲述了python实现提取百度搜索结果的方法.分享给大家供大家参考.具体实现方法如下: # coding=utf8 import urllib2 import string import urllib import re import random #设置多个user_agents,防止百度限制IP user_agents = ['Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130406 Firefox/23.0', \ 'M
PHP实现二叉树的深度优先与广度优先遍历方法

本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法.分享给大家供大家参考.具体如下: #二叉树的广度优先遍历 #使用一个队列实现 class Node { public $data = null; public $left = null; public $right = null; } #@param $btree 二叉树根节点 function breadth_first_traverse($btree) { $traverse_data = array(); $queue = arr
PHP查找与搜索数组元素方法总结

本文实例讲述了PHP查找与搜索数组元素方法.分享给大家供大家参考.具体分析如下: 查找.筛选与搜索数组元素是数组操作的一些常见功能.下面来介绍一下几个相关的函数. in_array()函数 in_array()函数在一个数组汇总搜索一个特定值,如果找到这个值返回true,否则返回false.其形式如下: boolean in_array(mixed needle,array haystack[,boolean strict]); 来看下面的例子,查找变量apple是否已经在数组中,如果在,则输出
Yii 2.0实现联表查询加搜索分页的方法示例

前言最近在学习yii2.0,在使用yii2.0过程中遇到一些问题,现将查询搜索分页的方法整理如下,分享出来供大家参考学习,话不多说,来一起看看详细的介绍: 主表:{{%article}} 关联表:{{%article_class}} 方法如下 1.使用gii创建CRUD和search不详述 2.在Article中添加的关联内容,代码#注释部分 class Article extends \yii\db\ActiveRecord { #关联查询1:这里加上被关联字段 public $class_
Python实现提取谷歌音乐搜索结果的方法

本文实例讲述了Python实现提取谷歌音乐搜索结果的方法.分享给大家供大家参考.具体如下: Python的简单脚本,用于提取谷歌音乐搜索页面中的歌曲信息,包括歌曲名,作者,专辑名,现在链接等,最多只提取10页结果. #! /usr/bin/env python #coding=utf-8 ''' Created on 2011-8-19 @author: yaoboyuan ''' from urllib import request,parse import re,sys def extrac
C++递归线性阵列搜索数字的方法

本文实例讲述了C++递归线性阵列搜索数字的方法.分享给大家供大家参考.具体如下: 这里采用递归方法搜索阵列的数字,发现返回index,未发现范围a -1. 复制代码代码如下: int searchArray(int arr[], const int size, const int num, int index = 0) { if(index >= size - 1) { return -1; } return arr[index] == num ? index : search

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

相关推荐

随机推荐