c++ - 有向图中的DFS遍历和循环

问题描述

我有一个有向图。最初，假定所有节点都未被访问，并且标志为 -1 in vector<int>flag。现在我们从一个源节点开始并推入stack<int>s并制作flag[source]=0. 现在我做 DFS 遍历 & 推送节点if(flag[node]==-1)& make flag[node]=0. 如果访问了所有 DFS 定向链接，我会弹出堆栈的元素并标记它flag[s.top()]=1；在推送时，如果我们遇到带有的节点flag[nodes]==0，则检测到循环并且我在变量中进行增量int final；`

你可以在我的代码中看到，我将DFS遍历存储在一个temp向量中，我认为这是垃圾，我怎样才能直接通过这些连接的节点来检查标志并检测循环。目前我的代码有效，但对于更大的输入失败。请寻求帮助。

#include<iostream>
#include<vector>
#include<stack>
#include<map>
using namespace std;
int mx=1e5+5;
vector<bool>vist(mx);
vector<vector<int>>Graph(mx);
void dfs(int node,vector<int>&dfs_vec){
    vist[node]=true;
    dfs_vec.push_back(node);
    for(int neigh: Graph[node]){
        if(!vist[neigh]){
            dfs(neigh,dfs_vec);
        }
    }
}
//my temp vector is in while loop of main.
int main(){
    int num_vertex;int num_edge;
    cin>>num_vertex>>num_edge;
    int u,v;
    for(int i=0;i<num_edge;i++){
        cin>>u>>v;
        Graph[u].push_back(v);
    }
    vector<int>flag(num_vertex+1,-1);
    stack<int>s;
    int source=1;
    s.push(source);
    flag[source]=0;
    int final=0;
    while(!s.empty()){
        int x=s.top();
        vector<int>temp;
        dfs(Graph[x][0],temp);
        for(auto y:temp){
            if(flag[y]==-1){
                s.push(y);
                flag[y]=0;
            }
            else if(flag[y]==0){
                final++;
            }
        }
        flag[s.top()]=1;
        s.pop();
        vist.clear();
        vist.resize(mx);

    }
    if(final>0){
        std::cout<<"Graph is cyclic";
    }
    else{
        std::cout<<"Graph is not cyclic";
    }
}

标签： c++algorithmdata-structuresgraph-theory

如果要处理大型数据集，重要的是最小化递归函数签名中的参数。每次调用都需要将参数保存在堆栈上，这是一个相当有限的资源。

要最小化参数，请在类上使用一种方法，该方法尽可能仅将参数数据的一个副本存储为属性。对于 DFS，除了当前访问的节点的索引之外的所有内容都可以移出参数列表。

这是我在包含数十万个顶点的图上成功使用的 DFS 的直接实现。

    void cPathFinder::depthRecurse(
        int v )
    {
        visitor(v);

        // remember this node has been visited
        myPath[v] = 1;

        // look for new adjacent nodes
        for (int w : adjacent(v))
            if (!myPath[w])
            {
                // search from new node
                depthRecurse(w, visitor);
            }
    }

仅供参考，这里是对设计类以实现图论算法时要考虑的一些问题的简要讨论。https://github.com/JamesBremner/PathFinder2/wiki/cGraph-Class-Design

c++ - 有向图中的DFS遍历和循环

问题描述

解决方案

推荐阅读