精华内容
下载资源
问答
  • 判断有向图中是否有环
    2021-01-15 02:38:00

    本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。

    一 无向图

    1.利用DFS进行判断

    利用DFS判断有向图是否存在环,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,下面对这种方法及其实现进行详细的阐述。

    首先,利用DFS判断无向图中是否换的原理是:若在深度优先搜索的过程中遇到回边(即指向已经访问过的顶点的边),则必定存在环。

    所以说,是否存在环的关键在于是否存在满足条件的“回边”,那么如何判断回边呢?

    (1)首先,对图中的所有顶点定义三种状态:顶点未被访问过、顶点刚开始被访问、顶点被访问过并且其所有邻接点也被访问过。这三种状态,在visited数组中分别用0、1、2来表示。那么,存在环的情况可以定义为:在遍历过程中,发现某个顶点的一条边指向状态1的顶点,此时就存在环。状态2可以理解为其生成树上的所有的子孙节点都已经访问完。

    (2)此外,我们要定义一个father数组,用以存储在DFS过程中顶点的父顶点(或者说是生成树上的父节点)。其主要作用是为了区分邻接点中环中的顶点和遍历过程中的父节点 (单纯的用visited数组无法区分)。

    整个过程的实现代码如下:

    #define MAX_NUM 100

    #define INF 0x7fffffff

    /*DFS判断无向图中是否有环*/

    class Graph

    {

    public:

    int vertexNum;//顶点个数

    int arcNum;//弧的个数

    int vertex[MAX_NUM];//顶点表

    int arc[MAX_NUM][MAX_NUM];//弧信息表

    };

    int visited[MAX_NUM];//顶点访问表

    int father[MAX_NUM];//父节点表

    void DFS(int v,Graph G)

    {

    visited[v] = 1;

    for(int i = 0 ; i < G.vertexNum; i++)

    {

    if(i != v && G.arc[v][i] != INF)//邻接矩阵中节点v的邻接点

    {

    if(visited[i] == 1 && father[v] != i)//vi不是父节点,而且还访问过(而且为状态1,说明不是回溯过来的顶点),说明存在环(判断i不是v的父节点)

    {

    cout<

    int temp = v;

    while(temp != i)

    {

    cout<

    temp = father[temp];

    }

    cout<

    }

    else

    if(visited[i] == 0)

    {

    father[i] = v;//更新father数组

    DFS(i,G);

    }

    }

    }

    visited[v] = 2;//遍历完所有的邻接点才变为状态2

    }

    void DFSTraverse(Graph G)

    {

    memset(visited,0,sizeof(visited));

    memset(father,-1,sizeof(father));

    for(int i = 0 ; i < G.vertexNum; i++)

    if(!visited[i])

    DFS(i,G);

    }

    由此可见,visited数组相对于一般的情况,增加了个状态2,主要是为了防止在回溯过程中进行误判。所以才能仅用father数组和状态1判断存在环。

    状态2可以理解为其生成树上的所有的子孙节点都已经访问完。

    由于使用的是邻接矩阵来存储,所以该算法的时间复杂度为O(n^2),空间复杂度为O(n)。

    2.其他方法本文不再详述。

    二 有向图

    1.拓扑排序

    关于拓扑排序,资料很多,本文不再详述其原理,只给出其实现代码,代码如下:

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    #define MAX_NUM 100

    #define INF 0x7fffffff

    /*拓扑排序*/

    int indegree[MAX_NUM];//用以表示每个顶点的入度

    bool visited[MAX_NUM];//用以表示该顶点是否入栈

    class Graph

    {

    public:

    int vertexNum;//顶点个数

    int arcNum;//弧的个数

    int vertex[MAX_NUM];//顶点表

    int arc[MAX_NUM][MAX_NUM]= {{0,1,1},{INF,0,1},{INF,INF,0}}; //弧信息表

    };

    void Initindegree(Graph G)//初始化入度数组

    {

    memset(indegree,0,sizeof(indegree));

    for(int i = 0; i < G.vertexNum; i++)

    for(int j = 0; j < G.vertexNum; j++)

    {

    if(i != j && G.arc[i][j] != INF)

    indegree[j]++;//注意此处增加的是顶点vj的入度

    }

    memset(visited,0,sizeof(visited));

    }

    bool TuoPu(Graph G)

    {

    stack s;

    int cnt = 0;//用于记录拓扑序列中节点的个数

    for(int i = 0 ; i < G.vertexNum; i++)

    if(indegree[i] == 0)

    {

    s.push(i);

    visited[i] = true;//修改入栈顶点的入栈标记数组

    }

    while(!s.empty())

    {

    int v = s.top();

    cnt++;//顶点出栈得到时候,计数器加1

    s.pop();

    for(int i = 0; i < G.vertexNum; i++)

    {

    if(v != i && G.arc[v][i] != INF && visited[i] == false)//将所有顶点v的未入栈的邻接点的入度都减去1

    {

    indegree[i]--;

    if(indegree[i] == 0)//如果减1后入度为0了,此时需要将该邻接点入栈,且修改入栈标记数组

    {

    visited[i] = true;

    s.push(i);

    }

    }

    }

    }

    return cnt == G.vertexNum ? true : false;

    }

    int main()

    {

    Graph G;

    G.vertexNum = 3;

    Initindegree(G);

    cout<

    }

    2.利用改进的DFS

    对于有向图的话,如果直接应用一般的DFS的话,会出现误判的情况,一个典型的例子是:A->B,A->C->B,我们用DFS来处理这个图,我们会得出它有环,但实际上并没有。然而,本文中所说的无向图的DFS判断算法完全可以直接应用到有向图中来,即上述代码可以直接应用到有向图中来。所以说上述的DFS算法(或称为为改进的DFS算法)既适用于无向图,也适用于有向图。其对应的原理适用于这两种图,即只要我们在遍历过程中,只要发现一个顶点不是当前节点的父节点,同时他还被访问过了(状态为1),那么就可以认为此处存在环。(通常在DFS中一个顶点的未被访问的邻接点,相当于生成树中的该顶点的子孙节点)

    更多相关内容
  • 下面小编就为大家分享一篇Python 判断 有向图 是否的实例讲解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 图——判断有向图中是否

    千次阅读 2020-12-04 09:38:55
    1. 判断有向图中是否 给定有向图,检查该图是否包含循环。如果给定图包含至少一个循环,则函数应返回true,否则返回false。 1.1. 方法一:DFS 1.1.1. 思路 对一个图进行DFS, 则DFS的路径可以生成一个棵树。 ...

    1. 判断有向图中是否有环

    给定有向图,检查该图是否包含循环。如果给定图包含至少一个循环,则函数应返回true,否则返回false。

    1.1. 方法一:DFS

    1.1.1. 思路

    对一个图进行DFS, 则DFS的路径可以生成一个棵树。

    对于DFS树上的结点,如果存在指向祖先的边或指向自己边,则图存在回路。(这种边叫做后向边)


    下面通过图来描述一下:

    有向图,如下。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JzaHYM3F-1607045914066)(D:\笔记图片集\1606530749386.png)]

    其DFS树为:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8Tg2gtvY-1607045914068)(D:\笔记图片集\1606530878771.png)]

    但是当你DFS到3结点时 会存在后向边,如图:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z76xmhRi-1607045914070)(D:\笔记图片集\1606530964484.png)]

    所以这个有向图存在环路

    1.1.2. 实现过程

    首先需要两个辅助数组。

    vis数组:用来标记节点是否已被访问。

    recStack数组(或集合):一个用来标记递归栈中的节点(或者说递归过程中的节点)。

    1. 一个递归函数isCyclicUtil,标记当前节点v已被访问,并且标记它在递归栈中
    2. 循环遍历与v相连的节点
    3. 如果该节点未被访问,则递归调用该节点的isCyclicUtil,如果返回true,则当前就返回true
    4. 如果该节点已被访问,并且在递归栈中,则返回true
    5. 其他情况,返回false
    6. 创建一个isCyclic函数,循环调用每个节点的isCycticUtil。如果任意一个返回true,则该函数isCyclic返回true。否则返回false。

    其实isCyclicUtil就是DFS函数稍加修改。

    1.1.3. 实现代码

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 105;
    vector<vector<int> > g(N);
    bool isCyclicUtil(int v, bool vis[],bool recStack[])
    {
        if (!vis[v])
        {
            vis[v] = recStack[v] = true;
            for(int i = 0;i < g[v].size();++ i)
            {
                if (!vis[g[v][i]] && isCyclicUtil(g[v][i], vis, recStack))
                    return true;
                else if (recStack[g[v][i]])
                    return true;
            }
        }
        recStack[v] = false;
        return false;
    }
    
    bool isCyclic(int n)
    {
        bool vis[n],recStack[n];
        for(int i = 0;i < n;++ i)
            vis[i] = recStack[i] = false;
        for(int i = 0;i < n;++ i)
        {
            if (isCyclicUtil(i, vis, recStack))
                return true;
        }
        return false;
    }
    
    int main()
    {
        int n,m;
        cin >> n >> m;
        for(int i = 0;i < m;++ i)
        {
            int from, to;
            cin >> from >> to;
            g[from].push_back(to);
        }
        cout << (isCyclic(n) ? "yes" : "no");
        return 0;
    }
    /*
    input
    output
    */
    
    

    1.1.3. 复杂度分析

    时间复杂度: O ( V + E ) O(V + E) OV+E

    • 该方法的时间复杂度与DFS遍历的时间复杂度相同,为 O ( V + E ) O(V + E) OV+E

    空间复杂度: O ( V ) O(V) OV

    • 为了存储已访问结点和递归栈,需要 O ( V ) O(V) OV空间。

    参考

    • https://www.cnblogs.com/-yyyan/p/13383496.html
    • https://www.geeksforgeeks.org/detect-cycle-in-a-graph/
    展开全文
  • 拓扑排序判断有向图中是否

    千次阅读 2022-02-24 14:10:31
    拓扑排序是对一个有向图构造拓扑序列,解决工程是否能顺利进行的问题。构造时有222种结果: 此图全部顶点被输出:说明说明图中无「」存在, 是 AOV 网(有向无图) 没有输出全部顶点:说明图中有」存在,...

    拓扑排序的工程意义

    拓扑排序是对一个有向图构造拓扑序列,解决工程是否能顺利进行的问题。构造时有 2 2 2种结果:

    1. 此图全部顶点被输出:说明说明图中无「环」存在, 是 AOV 网(有向无环图)
    2. 没有输出全部顶点:说明图中有「环」存在,不是 AOV 网

    主要思想

    遍历所有入度为 0 0 0的节点,并由该节点刷新其指向节点的度,即将其指向节点的入度减 1 1 1,当该节点入度为 0 0 0,将其加入队列。最后查看所有节点的入度是否为 0 0 0,如果全部为 0 0 0,说明该网络是有向无环图。

    例题

    LeetCode.207 课程表

    你这个学期必须选修 n u m C o u r s e s numCourses numCourses门课程,记为 0 0 0 n u m C o u r s e s − 1 numCourses-1 numCourses1
    在选修某些课程之前需要一些先修课程。 先修课程按数组 p r e r e q u i s i t e s prerequisites prerequisites 给出,其中 p r e r e q u i s i t e s [ i ] = [ a i , b i ] prerequisites[i] = [a_i, b_i] prerequisites[i]=[ai,bi],表示如果要学习课程 a i a_i ai则必须先学习课程 b i b_i bi。例如,先修课程对 [ 0 , 1 ] [0, 1] [0,1]表示:想要学习课程 0 0 0,你需要先完成课程 1 1 1
    请你判断是否可能完成所有课程的学习?如果可以,返回 t r u e true true;否则,返回 f a l s e false false
    提示
    1 < = n u m C o u r s e s < = 1 0 5 1 <= numCourses <= 10^5 1<=numCourses<=105
    0 < = p r e r e q u i s i t e s . l e n g t h < = 5000 0 <= prerequisites.length <= 5000 0<=prerequisites.length<=5000
    p r e r e q u i s i t e s [ i ] . l e n g t h = = 2 prerequisites[i].length == 2 prerequisites[i].length==2
    0 < = a i , b i < n u m C o u r s e s 0 <= a_i, b_i < numCourses 0<=ai,bi<numCourses
    p r e r e q u i s i t e s [ i ] prerequisites[i] prerequisites[i]中的所有课程对互不相同

    思路

    使用拓扑排序来解题,当构成的有向图没有环,那么说明可以完成所有课程的学习。先修课程数组相当于有向图的边,当课程不需要先修课程即可学习,那么该课程入度为 0 0 0,否则入度就是需要先修课程的数量。

    代码

    class Solution {
        public boolean canFinish(int n, int[][] edges) {
            int[] d = new int[n];
            List<Integer>[] g = new List[n];
            for(int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
            }
            for(int[] x : edges) {
                int a = x[0], b = x[1];
                g[b].add(a);
                d[a]++;
            }
            Queue<Integer> q = new LinkedList<>();
            for(int i = 0; i < n; i++) {
                if(d[i] == 0) {
                    q.offer(i);
                }
            }
            int cnt = 0;
            while(q.size() > 0) {
                int x = q.poll();
                cnt++;
                for(int y : g[x]) {
                    d[y]--;
                    if(d[y] == 0) {
                        q.offer(y);
                    }
                }
            }
            return cnt == n;
        }
    }
    
    展开全文
  • 如果学习x课程前必须先学习y课程,学习y课程前必须先学习z课程,学习z课程前必须先学习x课程,那么一定是有问题了...1.1检测有向环的API设计 在API添加onStack[]布尔数组,索引为的顶点,当我们深度搜索的时: ...

    如果学习x课程前必须先学习y课程,学习y课程前必须先学习z课程,学习z课程前必须先学习x课程,那么一定是有问题了,我们就没有办法学习了,因为这三个条件没有办法同时满足。其中这三门课程x,y,z的条件组成了一个环。
    在这里插入图片描述
    因此,如果我们要使用拓扑排序解决优先级问题,首先得保证图中没有环的存在。
    1.1检测有向环的API设计
    在这里插入图片描述在API中添加onStack[]布尔数组,索引为图的顶点,当我们深度搜索的时:
    1:在如果当前顶点正在搜索,则把对应的onStack数组中的值修改为true,标识进栈;
    2:如果当前顶点搜索完毕,则把对应的onStack数组中的值改为false,标识出栈;
    3:如果即将要搜索某个顶点,但该顶点已经在栈中,则图中有环;
    在这里插入图片描述
    在这里插入图片描述
    代码实现

    public class DirectedCycle {
        //索引代表顶点,值表示当前顶点是否已经被搜索
        private boolean[] marked;
        //记录图中是否有环
        private boolean hasCycle;
        //索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜索的有向路径上
        private boolean[] onStack;
    
    
        //创建一个检测对象,检测图G中是否有环
        public DirectedCycle(Digraph G){
            //初始化marked数组
            this.marked = new boolean[G.V()];
            //初始化hasCycle数组
            this.hasCycle = false;
            //初始化onStack数组
            this.onStack = new boolean[G.V()];
    
            //找到图中每一个顶点,让每一个顶点作为入口,调用一次dfs进行搜索
            for(int v = 0;v < G.V(); v++){
                //判断如果当前顶点还没有被搜索过,则调用dfs进行搜索
                if(!marked[v]){
                    dfs(G,v);
                }
            }
        }
    
        /**
         * 基于深度优先搜索,检测图G中是否有环
         * @param G
         * @param v
         */
        private void dfs(Digraph G,int v){
            //把顶点v表示为已搜索
            marked[v] = true;
    
            //把当前顶点进栈
            onStack[v] = true;
    
            //进行深度搜索
            for (Integer w : G.adj(v)) {
                //判断如果当前顶点w没有被搜索过,则继续递归调用dfs方法完成深度优先搜索
                if(!marked[w]){
                    dfs(G,w);
                }
    
                //判断当前顶点w是否已经在栈中,如果已经在栈中,证明当前顶点之前处于正在搜索的状态
                if(onStack[w]){
                    hasCycle = true;
                    return;
                }
            }
        }
    
        /**
         * 判断有向环中是否有环
         * @return
         */
        public boolean hasCycle(){
            return hasCycle;
        }
    }
    
    
    展开全文
  • 第一次写博客,不太会用,话不多说 直接上代码 详细可以看注释,无向图判断是否存在环比有向图相对复杂一点 ,需要判断访问的节点的临接表的节点与父节点是否相同。 /** * @Description:判断无向图是否 深度...
  • 判断有向图是否

    千次阅读 2021-03-15 02:40:32
    方法一:拓扑排序时间复杂度O(n^2)比较常用的是用拓扑排序来判断有向图中是否存在。什么是拓扑排序呢?我们先定义一条u到v的边e=,u生成拓扑序列的算法就叫拓扑排序啦~算法流程描述while(节点个数次(N)循环)1.找出...
  • 有向图的java程序

    2020-05-03 10:58:15
    有向图寻找,java语言,文件读入为两个节点之间进行连接的数据,输出为长度为3到7的收尾相连的链,多次使用arraylist运行速度较慢。
  • //首先把所有入度为0的点放到que,再依次把这些点从图中删掉(即把它指向的点的入度减一); //再寻找入度为0的点,重复下去。直到所有的点都被从图中删掉。 bool toposort(int n) { vector<int>ans(n); ...
  • 判断给定的图是不是有向环图,方法是应用拓扑排序,代码如下
  • 两种方式判断有向图是否-python实现 1. DFS判断有向图是否 假设图以邻接矩阵表示,一条深度遍历路线如果有结点被第二次访问到,那么有。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后...
  • 代码】leetcode207.课程表(判断有向图是否
  • 最近想写一个识别线程死锁的算法,在网上找了半天没有合适的代码,自己写了个查找有向图中的代码(可以将死锁的资源依赖建模成含有向图)。本代码经过充分测试,内部有详细说明,可以放心下载。
  • 判断有向图中是否存在,用邻接表做存储结构
  • 题目:判断有向图中是否 问题描述 判断有向图中是否。 输入格式 输入数据第一行是一个正整数,表示n个有向图,其余数据分成n组,每组第一个为一个整数,表示图的顶点个数n,顶点数不超过100,之后为有...
  • } else { System.out.println("这个有向图不存在回路,拓扑序列为:" + temp.toString()); } } //创建图,以邻接矩阵表示 void create() { Scanner sc = new Scanner(System.in); System.out.println("正在创建图,...
  • 今天小编就为大家分享一篇python判断向图环是否存在的示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 用拓扑排序检测有向图中是否

    千次阅读 2021-09-02 10:26:13
    提示:由于拓扑排序的检测方式不涉及到边权或点权,所以拓扑序列的正环和负都能够被检测出来。检测可达负可以用Bellman-Ford或者SPFA。 算法主要步骤 1. 记录每个结点的入度,设置一个队列,专门存放入度为0...
  • /*判断一个有向图中是否,使用DFS的改进算法来判断  设置标志位C,如果C=0,此节点没被访问过  如果C=-1,此节点被访问过且正在遍历其子节点,有  如果C=1,此节点被访问过且其字节点也都被访问过,没...
  • 向图判断是否有环

    2021-03-15 17:35:25
    //深度优先遍历,当某个节点的子节点已经访问过,且该节点不是其父节点,肯定存在#include #include #include using namespace std;bool dfs(vector >&graph, vector&visited,int father,int &...
  • 有向图:主要有深度优先和拓扑排序2方法1、拓扑排序,如果能够用拓扑排序完成对图所有节点的排序的话,就说明这个图没有,而如果不能完成,则说明有。2、可以用Strongly Connected Components来做,我们...
  • 判断有向图中的回路

    2013-12-24 13:31:55
    数据结构的作业…拓扑排序 判断有向图中并打印
  • DFS 判断有向图是否存在 vis :DFS 遍历的结果 trace:也是遍历的结果,需要对结果进行分析,找到重复值时,判断重复值的索引位置,依次进行遍历,输出结果 程序 ## graph = { "a": ["b", "c"], "b": ["a", "d"]...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 77,865
精华内容 31,146
关键字:

判断有向图中是否有环