精华内容
下载资源
问答
  • 简单方法判断邻接矩阵的有向图是否有环求解思路实现代码如有不同见解,欢迎讨论 求解思路 1.统计所有节点的出度及其前序节点,初始化一个空的访问集合; 2.将出度为零的节点放入访问集合... * 判断有向图是否有环 ...

    简单方法判断邻接矩阵的有向图是否有环

    求解思路

    1.统计所有节点的出度及其前序节点,初始化一个空的访问集合;
    2.将出度为零的节点放入访问集合,并将其前序节点的出度数减1;
    3.重复第2步骤,直到所有节点从头到尾完整遍历一遍;
    4.判断已访问节点个数是否等于节点个数,是则有向图无环,否则有向图有环。

    实现代码

    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Set;
    
    public class AlgorithmUtil {
        /**
         * 判断有向图是否有环
         * 根据每个节点的入度和出度计算,把出度为零的依次去掉并更改其前序节点的出度个数,统计最后访问过的节点个数
         */
        public static boolean isDag(int[][] graph) {
            int nodeNum = graph.length;
            // 记录每个有入度的节点,及其所有的前序节点
            Map<Integer, List<Integer>> inEdge = new HashMap<>(nodeNum);
            // 记录每个节点的出度个数
            int[] outEdgeNum = new int[nodeNum];
            // 初始化数据
            for (int i = 0; i < nodeNum; i++) {
                for (int j = 0; j < nodeNum; j++) {
                    if (graph[i][j] != Integer.MAX_VALUE) {
                        outEdgeNum[i]++;
                        if (inEdge.get(j) == null) {
                            List<Integer> list = new ArrayList<>();
                            list.add(i);
                            inEdge.put(j, list);
                        } else {
                            inEdge.get(j).add(i);
                        }
                    }
                }
            }
    
            // 已访问的节点
            Set<Integer> visitedSet = new HashSet<>(nodeNum);
            // 循环遍历所有节点的出度
            while (visitedSet.size() < nodeNum) {
                for (int i = 0; i < nodeNum; i++) {
                    if (outEdgeNum[i] == 0 && !visitedSet.contains(i)) {
                        visitedSet.add(i);
                        for (int temp = 0; inEdge.get(i) != null && temp < inEdge.get(i).size(); temp++) {
                            outEdgeNum[inEdge.get(i).get(temp)]--;
                        }
                        break;
                    }
                    // 节点遍历一遍后,判断是否访问了过所有节点
                    if ((i == nodeNum - 1) && visitedSet.size() != nodeNum) {
                        return true;
                    }
                }
            }
    
            return false;
        }
    }
    

    测试用例

    import org.junit.Test;
    
    public class AlgorithmUtilTest {
    
        private int NAN = Integer.MAX_VALUE;
    
        @Test
        public void isDag() {
            int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, NAN}};
            assert !AlgorithmUtil.isDag(graph);
        }
    
        @Test
        public void isDag2() {
            int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {1, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, NAN}};
            assert AlgorithmUtil.isDag(graph);
        }
    
        @Test
        public void isDag3() {
            int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {1, NAN, NAN, NAN}};
            assert AlgorithmUtil.isDag(graph);
        }
    }
    

    知识背景

    leetcode 207题 课程表
    简单方法查找邻接矩阵有向图的有序集合
    如有不同见解,欢迎留言讨论

    展开全文
  • 1构成一个环,所以返回1表示环 输入:[[0,1,0],[0,0,1],[0,0,0]] 输出:0 解释:1->2->3,这是一条拓扑路径,所以返回0表示没有环 #include<iostream> #include<vector> #i...

    输入:[[0,1,0],[0,0,1],[1,0,0]]

    输出:1

    解释:1->2->3->1构成一个环,所以返回1表示有环

    输入:[[0,1,0],[0,0,1],[0,0,0]]

    输出:0

    解释:1->2->3,这是一条拓扑路径,所以返回0表示没有环

    #include<iostream>
    #include<vector>
    #include<queue>
    #include<cstdio>
    #include<sstream>
    
    using namespace std;
    
    bool ExistLoop(const vector<vector<bool>>& AdajstGraph){
        int Length = AdajstGraph.size();
        vector<int> in(Length,0);
        queue<int> q;
        for(int i = 0;i < Length;i ++){
            for(int j = 0;j < Length;j ++){
                if(AdajstGraph[j][i] == 1){
                    in[i]++;
                }
            }
        }
        for(int i = 0;i < Length;i ++){
            if(in[i] == 0){
                q.push(i);
            }
        }
        int NumOfList = 0;
        while(!q.empty()){
            int p = q.front();
            q.pop();
            NumOfList++;
            for(int i = 0;i < Length;i ++){
                if(AdajstGraph[p][i] == 1){
                    in[i]--;
                    if(in[i] == 0){
                        q.push(i);
                    }
                }
            }
        }
        return NumOfList != Length;
    }
    
    int main(){
        string s;
        vector<vector<bool>> AdajstGraph;
        getline(cin,s);
        for(int i = 1;i < s.length();i ++){
            if(s[i] == '['){
                AdajstGraph.push_back(vector<bool>());
            }
            else if(s[i] == '0' || s[i] == '1'){
                AdajstGraph.back().push_back(s[i] - '0');
            }
        }
        if(ExistLoop(AdajstGraph)){
            printf("1\n");
        }
        else{
            printf("0\n");
        }
        return 0;
    }
    

     

    展开全文
  • [ZZ]如何判断有向图是否成环

    千次阅读 2010-10-29 00:45:00
     如何判断有向图是否成环 原文链接:http://blog.csdn.net/nomad2/archive/2007/04/10/1559664.aspx<br />(1)如何判断一个图是不是含有环? a. DFS,出现返回边则有环。 b. 拓扑排序,若所有...

     

    如何判断有向图是否成环

    原文链接:http://blog.csdn.net/nomad2/archive/2007/04/10/1559664.aspx

    (1)如何判断一个图是不是含有环?

    a. DFS,出现返回边则有环。

    b. 拓扑排序,若所有的顶点都出现在拓扑排序中,则不出现环。

    (2)拓扑排序

    a.什么是偏序,全序?from:

    http://www.programfan.com/club/showbbs.asp?id=221968

    偏序是由实数中的>=和<=抽象出来的
    在一个集合F中定义一个比较关系, 这个关系不要求任意两个元素都能比较
    这个关系可以任意定义,记为< , 但是定义的关系要满足以下3个条件
    1) 任意a属于F,有a < a;               ...说明元素自己可以和自己比较
    2) 如果a和b能比较 且a < b, b和c能比较,且 b < c
       那么a和c就能比较,且a < c          ...说明比较关系具有传递性
    3) 如果a和b能比较,且a < b, b < a, 那么a = b 
    定义的这种满足以上3条公理的比较关系就叫偏序,和所在的集合记为( F, < )

    全序首先是偏序,但是比偏序多一个要求:集合中的任意两个元素都是可比的。

    b.拓扑排序:

    由偏序定义得到拓扑有序的操作便是拓扑排序(topological order)。

    算法:

    (1) 在有向图中选一个没有前驱的顶点输出。

    (2) 从图中删除该定点和所有以它为尾的弧。

    (3) 重复前两步,直至所有节点都输出,或当前图中不存在无前驱的节点(存在环)。

    图采用邻接表实现,头文件代码如下:

    #define MAX_VERTEX_NUM 20

    typedef int InfoType;
    typedef char VertexType;

    typedef enum  {DG, DN, UDG, UDN} GraphKind;

    typedef struct ArcNode {
        int adjvex;
        struct ArcNode *next;
        InfoType info;
    }
    ArcNode;

    typedef struct VNode {
        int in_degree;
        VertexType data;
        ArcNode *firstarc;
    }
    VNode, AdjList[MAX_VERTEX_NUM];

    typedef struct  {
        AdjList vertex;
        int vexnum, arcnum;
        GraphKind kind;
    }
    algraph;

    源文件代码:

    #include "algraph_topo.h"

    #include "stdio.h"
    #include "stdlib.h"

    void createDN(algraph &g) {}
    void createUDN(algraph &g) {}
    void createUDG(algraph &g) {}

    //locate the name vertice's index
    int locate(algraph g, char name) {
        for(int i = 0; i < g.vexnum; i++){
            if(name == g.vertex[i].data){
                return i;
            }

        }

        return -1;
    }


    void createDG(algraph &g) {
        printf("input the number of vertex and arcs: ");
        scanf("%d %d", &g.vexnum, &g.arcnum);
        fflush(stdin);
        
        int i = 0, j = 0, k = 0;
        
        printf("input the name of vertex: ");
        
        for(i = 0; i < g.vexnum; i++){
            scanf("%c", &g.vertex[i].data);
            fflush(stdin);
            g.vertex[i].firstarc = NULL;
            g.vertex[i].in_degree = 0;
        }

        
        //construct the adjacent list
        char v1, v2;
        int w;
        ArcNode *p;

        printf("input the %d arcs v1 v2 and weight: ", g.arcnum);
        for(k = 0; k < g.arcnum; k++){
            scanf("%c %c %d", &v1, &v2, &w);
            fflush(stdin);
            i = locate(g, v1);
            j = locate(g, v2);

            //new a node
            p = (ArcNode *)malloc(sizeof(ArcNode));
            p->adjvex = j;
            p->info = w;
            p->next = NULL;

            //insert the node in the head of list
            if(!g.vertex[i].firstarc){
                g.vertex[i].firstarc = p;
            }
    else{
                p->next = g.vertex[i].firstarc;
                g.vertex[i].firstarc = p;
            }


            g.vertex[j].in_degree++;
        }

    }


    //print the list
    void printGraph(algraph g) {
        for(int i = 0; i < g.vexnum; i++){
            printf("%c's adjacent list is: ", g.vertex[i].data);
            ArcNode *p = g.vertex[i].firstarc;
            while(p){
                printf("%c(%d) ", g.vertex[p->adjvex].data, p->info);
                p = p->next;
            }

            printf(" ");
        }

    }


    void createGragh(algraph &g) {
        
        printf("please input the type of graph: ");
        scanf("%d", &g.kind);
        
        switch(g.kind){
        case DG: 
            createDG(g);
            //printGraph(g);
            break;
        case DN: 
            createDN(g);
            break;
        case UDG: 
            createUDG(g);
            break;
        case UDN: 
            createUDN(g);
            break;
        }

    }


    //²éÕÒÏÂÒ»¸ö
    int findNext(algraph g) {
        for(int i = 0; i < g.vexnum; i++){
            if(g.vertex[i].in_degree == 0){
                return i;
            }

        }

        return -1;
    }


    //topo order
    void topoSort(algraph g) {
        printf("the topo sort of graph is: ");
        for(int i = 0; i < g.vexnum; i++){
            int index = findNext(g);
            if(index > -1){
                printf("%c ", g.vertex[index].data);

                //don't consider the vertice again
                g.vertex[index].in_degree = -1;
                
                ArcNode *p = g.vertex[index].firstarc;
                while(p){
                    g.vertex[p->adjvex].in_degree--;
                    p = p->next;
                }

            }
    else{
                break;
            }

        }

        printf(" ");
    }


    void main() {
        algraph g;
        createGragh(g);
        topoSort(g);
    }

    程序的运行结果如下:

    please input the type of graph:
    0
    input the number of vertex and arcs:
    6 8
    input the name of vertex:
    a
    b
    c
    d
    e
    f
    input the 8 arcs v1 v2 and weight:
    a d 1
    a c 1
    a b 1
    c e 1
    c b 1
    d e 1
    f e 1
    f d 1
    the topo sort of graph is:
    a       c       b       f       d       e
    Press any key to continue

    说明:

    (1) 为了避免重复检测入度为0的顶点,可设置一个栈暂存所有入度为0的顶点,复杂度为O(n + e)。而在程序中采用的是

        //don't consider the vertice again
        g.vertex[index].in_degree = -1;

    来实现的。复杂度要高一些。

    (2) 可以使用DFS,退出DFS函数的顺序即为逆向的拓扑有序序列。

    (3)关键路径 

    a. AOV网:用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网(activity on vertex network)。AOV网中,没有有向环。

    b. AOE网:边表示活动的网络(顶点表示事件,弧表示活动),用来估算工程的完成时间,通常只有一个源点和一个汇点。

    c. 求AOE算法的复杂度是O(n + e)

     

    展开全文
  • Floyd-Warshall方法求有向图传递闭包

    千次阅读 2009-09-13 15:56:00
    有向图G的传递闭包定义为:G*=(V,E*),其中E*={(i,j)}:图G中存在一条从i到j的路径。 在floyd-warshall求每对顶点间的最短路径算法中,可以通过O(v^3)的方法求出图的传递闭包。可以位每条边赋以权值1,然后运行Floyd-...

    有向图G的传递闭包定义为:G*=(V,E*),其中
    E*={(i,j)}:图G中存在一条从i到j的路径。

    在floyd-warshall求每对顶点间的最短路径算法中,可以通过O(v^3)的方法求出图的传递闭包。可以位每条边赋以权值1,然后运行Floyd-Wareshall。如果从i    到j存在一条路径,则d(i,j)<N,否则d(i,j)=MAX。
     一种改进的算法是:由于我们需要的只是判断是否从i到j存在一条通路,所以在Floyd-Wareshall中的动态规划比较中,我们可以把min和+操作改为逻辑or(||    )和逻辑与(&&)。
     设tk(i,j)=1表示从i到j存在一条通路p,且p的所有中间节点都在0,1,2,...,k中,否则tk(i,j)=0。我们把边(i,j)加入到E*中当且仅当tn(i,j)=1。  

    展开全文
  • 第一次写博客,不太会用,话不多说 直接上代码 详细可以看注释,无向图判断是否存在环比有向图相对复杂一点 ,需要判断访问的节点的临接表中的节点与父节点是否相同。 /** * @Description:判断无向图是否有环 深度...
  • 有向图和无向图差别就是一句代码的差别 ,无向图中代码注释掉即可 有向图和有向网的差别也就是权值的差别 有向网需要赋予权值 有向图有连线自动赋值为1 深度优先采用递归方法(参考前面几篇文章,里面有具体的...
  • 【图结构专题】有向图

    万次阅读 2018-03-19 22:00:26
    有向图 一. 有向图的相关术语 在有向图中,边是单向的:每条边连接的两个顶点都是一个有序对,它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图:比如任务調度的依赖关系,社交网络的任务关系等等...
  • 有向图找环

    千次阅读 2013-07-01 20:49:44
    有向图判断环与无向图不同,比如A->B A->C->B 若看做无向图是有环的,若看做有向图是无环的。这也比较好做,用拓扑排序的方法若最后能把所有顶点排好序就说明没有环。 (拓扑排序:一个无前驱的结点出发,然后珊...
  • 十六、图算法之有向图

    千次阅读 2016-04-18 00:07:09
    有向图有向图的数据结构采用链表public class Digraph { private static final String NEWLINE = System.getProperty("line.separator"); private final int V; // number of vertices in this digraph privat
  • PGM:有向图模型:贝叶斯网络

    万次阅读 2016-09-09 17:26:10
     简言之,把某个研究系统中涉及的随机变量,根据是否条件独立绘制在一个有向图中,就形成了贝叶斯网络。其主要用来描述随机变量之间的条件依赖,用圈表示随机变量(random variables),用箭头表示条件依赖...
  • 目录 无向连通图的相关定义 主要算法流程  DFS判断: BFS判断: ... 无向连通图:若在无向图G中,任意两点都是连通的,则称图G为连通图。 主要算法流程  DFS判断: 从任一结点开始,进行一...
  • 那么在有向图中要判断v到w是否可达,我们只需要以v为起点遍历一遍图,看能否遍历到w即可。当然在遍历时可以自己适当的加一些限制条件,提高算法效率,如:不需要遍历完所有顶点,只要遍历到w就可以结束遍历。所以...
  • 有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected),如果有向图G的每两个顶点都强连通,称G是一个强连通图.通俗的说法是:从图G内任意一个点出发,存在通向图G内任意一点的的一条路径....
  • 判断图的连通性

    千次阅读 2020-06-11 22:23:52
    通过矩阵判断图的连通性的过程类似于使用定义求解传递闭包的过程,但是要注意一些细节上的判断
  • 传递函数

    千次阅读 2020-10-24 16:32:30
    分母为 1+G*H,1+G*H=0的根即该闭环系统的极点,用来判断闭环系统是否稳定。 特征根的实数为负,即极点都在s平面的左半平面,则系统稳定 开环传递函数F(s) = G*H写作分数形式 F(s) = A(s)/B(s),则特征方程为 1+...
  • UIView 事件传递

    千次阅读 2017-01-06 17:24:07
    : 悬浮的三个按钮下方一个可以点击的灰色区域,但是点击按钮之间的透明区域, 这三个按钮的contentView会响应这个点击事件,这时候需要让这个contentView不响应这个点击事件。 解决方法如下(将此方法...
  • 图论 Warshall 和Floyd 矩阵传递闭包

    千次阅读 2016-06-20 09:10:07
    我们来说下有向图,一般的有向图也是图,图可以分为稠密图,稀疏图,那么从意思上,稠密图就是点的边比较多,稀疏图就是边比较少的图。为什么稠密图放在矩阵比较省空间,因为邻接表在边之间存储需要多余的指针,而...
  • 【OpenGL】Shader中传递数据

    万次阅读 多人点赞 2013-04-21 16:23:18
    传递顶点属性信息 之前讲过,vertex shader会被每个顶点调用,通常一个顶点会包含很多信息,例如顶点坐标、顶点法向量、纹理坐标等等,我们称这些信息为顶点的属性。在之前的OpenGL版本里,每个属性都对应了一...
  • 数据结构 有向无环

    千次阅读 2007-04-10 21:23:00
    (1)如何判断一个是不是含有环?a. DFS,出现返回边则环。b. 拓扑排序,若所有的顶点都出现在拓扑排序中,则不出现环。(2)拓扑排序a.什么是偏序,全序?from:...
  • iOS之深入解析事件传递的响应链

    万次阅读 2021-08-30 20:44:37
    五、pointInside:withEvent: 判断触摸点是否在视图内: /** * @brief 判断一个点是否落在范围内 */ - (BOOL)pointInside:(CGPoint)point withEvent:(UIEvent *)event 如果现在要扩大按钮 2 的点击范围怎么办?...
  • 前面已经介绍怎么样把赋值表达式变换到树的中间表示,接着下来编译器要做的事情就是怎么样把树变换成有向无环。也许你会问为什么要把树变换成有向无环,而不是直接生成最终代码呢?其实,学习过数据结构就很清楚...
  • Android基础入门教程——3.3 Handler消息传递机制浅析标签(空格分隔): Android基础入门教程本节引言前两节中我们对Android中的两种事件处理机制进行了学习,关于响应的事件响应就这两种;本节给大家讲解的 是...
  • HHUOJ 1650 算法7-12:有向无环的拓扑排序 题目描述 由某个集合上的一个偏序得到该集合上的一个全序,这个操作被称为拓扑排序。偏序和全序的定义分别如下: 若集合X上的关系R是自反的、反对称的和传递的,则称R是...
  • 夜深人静写算法(十)- 有向图强连通和2-sat问题

    万次阅读 多人点赞 2018-03-01 22:19:40
    有向图强连通分量和2-sat问题
  • 向图的割顶和桥

    万次阅读 2017-07-15 08:06:13
    对于无向图G, 如果删除某个点u后, 连通分量数目增加, 称u为图的 关节点( articulation vertex) 或割顶( cut vertex) 。 对于连通图, 割顶就 是删除之后使图不再连通的点。 如何求出图的所有割顶呢? 我们...
  • Golang和Erlang消息传递机制对比

    千次阅读 2015-12-11 15:25:22
    上一篇文章介绍了 Go 和 Erlang 在调度器的实现,本文将简要介绍这两种并发语言的消息传递机制简要对比Erlang和Go虽然在实现及功能上差异较大,但是都支持高并发的轻量级用户任务(Erlang的轻量进程,Go的Goroutine...
  • Android 事件传递机制总结

    千次阅读 2019-06-15 17:47:55
    Android 事件传递机制总结 Android View虽然不是四大组件,但是其重要程度堪比四大组件。初级工程师到中高级工程师,这些都是很重要的,因为事件分发机制面试也会经常被提及,如果我们能get到要领,并跟面试官深入...
  • 里面三个判断,如果三个都为1,就会执行return true,不往下走了。而默认的onTouch监听返回false,只要一个是false,就不会返回true。接着往下看,程序执行onTouchEvent: if (onTouchEvent(event)) { return ...
  • iOS 手势操作和事件传递响应链

    千次阅读 2018-06-05 17:59:29
    iOS 手势操作和事件传递响应链 概述 iOS中的事件可以分为3大类型:触摸事件、加速计事件、远程控制事件。 在我们点击屏幕的时候,iphone OS获取到了用户进行了“单击”这一行为,操作系统把包含这些点击事件的...
  • Android Touch事件传递机制

    千次阅读 2015-09-13 14:25:36
    Touch事件传递机制,其实说起来还是比较复杂的,所涉及的内容和细节也都比较多。为了方便理解,本文将由浅入深的进行讲解。 首先要知道我们对于屏幕的所有操作,包括点击、放开、滑动,以及由这些基本操作组成的放大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 207,019
精华内容 82,807
关键字:

判断有向图是否是可传递的