[C++] C++ DFS 记录层数两种写法dfs(int v) dfs(int v,int level)

2017-01-04 08:19:47来源:CSDN作者:u014786849人点击

DFS

完整源码

DFS.cpp

// DFS.cpp#include <iostream>using namespace std;bool marked[10];int G[10][10];int V,E;int count;void dfs(int v) {    count++;    int level;    level = count;    for(int i = 0 ;i < level ;i++)        cout << " ";    cout << "DFS   " << v << " start :  " << endl;    marked[v] = true;    for(int i = 0; i < V;i++)        if(!marked[i] && G[v][i]) dfs(i);    for(int i = 0 ;i < level ;i++)        cout << " ";    cout << "DFS   " << v << " end.  " << endl;}void readData() {    for(int i = 0; i < 10;i++)        for(int j = 0; j < 10; j++)            G[i][j] = -1;    cin >> V >> E;    for(int i = 0 ; i < E; i++) {        int v , w;        cin >> v >> w;        G[v][w] = 1;    }    count = 0;}int main(){    readData();    dfs(0);}

DFS2.cpp

// DFS2.cpp#include <iostream>using namespace std;bool marked[10];int G[10][10];int V,E;void dfs(int v, int level) {    level++;    for(int i = 0 ;i < level ;i++)        cout << " ";    cout << "DFS   " << v << " start :  " << endl;    marked[v] = true;    for(int i = 0; i < V;i++)        if(!marked[i] && G[v][i]) dfs(i, level);    for(int i = 0 ;i < level ;i++)        cout << " ";    cout << "DFS   " << v << " end.  " << endl;}void readData() {    for(int i = 0; i < 10;i++)        for(int j = 0; j < 10; j++)            G[i][j] = -1;    cin >> V >> E;    for(int i = 0 ; i < E; i++) {        int v , w;        cin >> v >> w;        G[v][w] = 1;    }}int main(){    readData();    dfs(0, 0);}

模拟数据

DFS

测试运行

430 11 22 3 DFS   0 start :  DFS   1 start :   DFS   2 start :    DFS   3 start :    DFS   3 end.   DFS   2 end.  DFS   1 end. DFS   0 end.--------------------------------Process exited after 0.9161 seconds with return value 0请按任意键继续. . .

代码说明

有向图的表示

int G[10][10];
  • 整型二维数组来表示有向图,G[v][w] == 1 表示 顶点v 到 顶点w 可达;

DFS过程

  • DFS的本质过程,如果用伪代码来描述应该是 :
DFS(int v){    标记 v 为: 已访问;    for 对于每个从v可达的顶点w :        如果 w 还没被访问过 ,那就 DFS(w);}
  • 基于本文使用的二维数组来表示图,所以代码实现层面可以简单地用for() 来遍历整个二维数组的一行,并且基于G[v][i] 的值来判断是不是从v可达,具体代码如下:
dfs(int v) {    marked[v] = true;        for(int i = 0; i < V;i++)            if(!marked[i] && G[v][i]) dfs(i);}

DFS.cpp 全局变量count与本地变量level

int count;void dfs(int v) {    count++;    int level;    level = count;    }
  • count在本文中被声明为一个全局变量,这样就不需要在DFS方法中增加参数,直接写个count++ 就可以在DFS往深处搜索的时候+1count变量初始值是0、从第一层的1开始最终会变成4
  • level变量是一个局部变量,是dfs函数内部的变量,目的是记住每个dfs当前的层数,以便在dfs开始start结束end输出相同数量的空格;

DFS2.cpp 与DFS.cpp记层数

dfs(int v)

void dfs(int v) {    count++;    int level;    level = count;    marked[v] = true;    for(int i = 0; i < V;i++)        if(!marked[i] && G[v][i]) dfs(i);}

dfs(int v,int level)

void dfs(int v, int level) {    level++;    marked[v] = true;    for(int i = 0; i < V;i++)        if(!marked[i] && G[v][i]) dfs(i, level);}
  • 区别还是很明显的,如果想要记录下层数,这两种写法都是OK的。

联系思考

  • 之前实现过 带权有向图的环检测以及环输出(点我,或者见引用[1]),当时用到的就是一种DFS的变形,算法核心的就是在DFS 开头以及 结束(对应本文两次for{} cout 输出)的位置,显式地用一个onStak[] 布尔数组来记录当前被访问的顶点是不是正处在本次DFS递归调用;
  • 无论是从模拟数据的图片还是从测试运行部分的输出来看,都可以很直观地感受到DFS,这种递归的痕迹,0->1->2->3->3->2->1->0,栈的FILO非常明显;

引用参考

[1][C++]C++ STL 环检测 带权有向图 DFS
http://blog.csdn.net/cook2eat/article/details/53980745

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台