dfs的两种处理方法

方法一：

对于源点s，初始化vis[s]=1，并且在dfs之后vis[s]=1，为下一次调用做准备。对于dfs递归中的寻找后继的循环体，入栈出栈语句写在循环内。

模板：

//调用

vis[s]=;

dfs(s);

vis[s]=;

//dfs

void dfs(int s){

    if(s==e){

        return;    //一定要有返回

    }

    for(i){

        path.push_back(i);

        vis[i]=;

        dfs(i);

        vis[i]=;

        path.pop_back();

    }

}

这样得到的路径path，是不包含源点的。注意在输出时加上源点。

方法二：

不用标记源点已访问。出入栈与访问标记抹去语句写在循环外。

模板：

//调用

dfs(s);

//dfs

void dfs(int s){

    if(s==e){

        return;    //一定要有返回

    }

    path.push_back(s);

    vis[s]=;

    for(i){

        dfs(i);

    }

    vis[s]=;

    path.pop_back();

}

这样得到的路径path，是不包含终点的。注意在输出时加上终点。

巴特西

dfs的两种处理方法

最新文章

热门文章