检查图是否包含环

淡淡的烟草味﹌ 2022-09-26 15:51 166阅读 0赞

我们常常用检查一张图中是否包含环来判断是否可以对这张图进行拓扑排序。但是对于无向图，由于无向图中每条边都可以表示成其对应某点的入边和出边，所以不能用拓扑排序的方法来检查是否包含环。但是我们可以用DFS方法来进行检查：从某一个点开始进行DFS遍历，如果在某个点所连接的点中，包含一个已经经过过的且不是这个点的父节点的点，说明有环。  
代码：

//有向图
    bool checkLoop(vector<vector<int>>& graph,vector<int>& inDegree){
        int n = graph.size();
        vector<bool> v(n,false); //检查点是否被经过过
        queue<int> vv(n,true);//入度为0的点
        vector<int> in = inDegree;
        for(int i = 0;i < n;++i)
            if(in[i] == 0)
                vv.push(i);
        while(vv.size()){
            int x = vv.front();
            vv.pop();
            v[x] = true;
            for(int i = 0;i < n;++i)
                if(graph[x][i] == 1 && v[i] == false){
                    in.push(i);
                    --in[i];
                    if(in[i] == 0)
                        vv.push(i);
                }
        }
        for(int i = 0;i < n;++i)
            if(v[i] == false)
                return true;
        return false;
    }

//无向图
    bool checkLoop(vector<vector<int>> &graph)
    {
        int n = graph.size();
        stack<int> v;
        vector<pair<bool,int>> through(n, make_pair(false,0));//bool表示有没有through，int表示父节点
        v.push(0);
        while (v.size()) {
            int x = v.top();
            v.pop();
            if (through[x].first)continue;
            through[x].first = true;
            for (int i = 0; i < n; ++i) {
                if (graph[x][i] == 1) {
                    if (through[i].first && through[i].second != i)
                        return true;
                    else if (!through[i].first) {
                        v.push(i);
                        through[i] = make_pair(false, x);
                    }
                }
            }
            for (int i = 0; i < n; ++i)
                if (!through[i].first)
                    return true;
            return false;
        }
    }