精华内容
下载资源
问答
  • 判断有向图是否是可传递的
    千次阅读
    2013-01-05 15:39:12
    /*判断无向图是否有环(求图传递闭包)*/
    #include <iostream>
    #include <stdlib.h>
    #include <vector>
    #include <memory.h>
    using namespace std;
    
    int n,m;
    int matrix[1001][1001];
    
    
    inline bool noLoop()
    {          
        //求出图的传递闭包
        // 例如 i->k,i可以到达k,则就在i列中,找出可以到达i的j,扫描k列所有行即可 
        for(int i=1; i<=n; i++)
          for(int k=1; k<=n; k++)
              if(matrix[i][k])
              {
                 //扫描k列所有的行 
                 for(int j=1; j<=n; j++)
                   if(matrix[j][i])  //如果存在j可达i,则说明j也可到k 则令其为1
                     matrix[j][k] =1;             
              }        
              
        //找完闭包后,要判断是否形成回路闭包,只需要判断是否存在节点i可以连通到自身
        for(int i=1; i<=n ; i++)
           if(matrix[i][i])
             return false; 
        return true;
    }
    
    
    int main()
    {
        while(cin >> n >> m)
        {
           //memset(visit, 0, sizeof(visit));
           memset(matrix, 0, sizeof(matrix));
           for(int i=1; i<= m; i++)
           {
              int start, end;
              cin >> start >> end;
              matrix[start][end] = 1;
              matrix[end][start] =1;       
           }
          
          if(!noLoop())
          {
             cout << "no" << endl;      
          }    
          else
             cout << "yes" << endl;
                   
        }   
        system("pause");
        return 0;
    }

    更多相关内容
  • 目录 无向连通图的相关定义 主要算法流程  DFS判断: BFS判断: ... 无向连通图:若在无向图G中,任意两点都是连通的,则称图G为连通图。 主要算法流程  DFS判断: 从任一结点开始,进行一...

    目录

    无向连通图的相关定义

    主要算法流程

     DFS判断:

    BFS判断:

    Warshell判断:

    Union-Find判断:

    Tarjan判断:


    无向连通图的相关定义

    1. 连通性:在图G中,两个不同的结点u和结点v之间若存在一条路,则称结点u和结点v是连通的。
    2. 无向连通图:若在无向图G中,任意两点都是连通的,则称图G为连通图。

    主要算法流程

     DFS判断:

    • 从任一结点开始,进行一次深度优先遍历。深度优先遍历的结果是一个图的连通分量。当一次遍历没有访问到所有结点,那么就说明图是不连通。
    • 算法步骤及相关分析

    a)算法步骤:
        从顶点v出发,访问顶点v,并令visited[v] = 1;
        依次查找v的所有邻接点w,若visited[w] 为0,则从w出发,深度优先遍历图。
        进行判断,遍历visited数组,若visited数组中有一个值不为1,则说明该点未被访问,图不连通。
    b)时间复杂度::算法运行时间主要是耗费在寻找邻接w处,寻找一个符合条件的w的时间复杂度是O(V),V个节点就是O(V^2),尽管可能不会寻找V次。
    c)空间复杂度:空间复杂度仅耗费在辅助数组visited[]上,空间复杂度为O(V)。
    d)改进:
        设置全局静态变量count,记录访问结点的数量,所以判断时不必遍历visited数组,只要判断count值是        否等于结点数量V即可;
        visited数组设置为全局变量,与BFS函数共享。
    • 代码:
    //DFS递归
    public void  DFS(int[] visited, int v) {
        visited[v] = 1;
    	judgeDFSCount ++;
    	for(int i=0; i<this.vertexNum; i++) {
    	    if(this.a[v][i] != 0 && visited[i] == 0)	//寻找下一个有边的未访问结点
    			DFS(visited, i);
    		}	
    	}
    //DFS判断,调用DFS递归
    public boolean DFSGraph() {
    	judgeDFSCount = 0;     				    //记录遍历的点个数,为全局变量
    	boolean flag = false;
    	visited = new int[this.vertexNum];		//初始数组就是全0
    
    	DFS(visited, 0);						//从0号结点开始
    	if(judgeDFSCount == this.vertexNum)		//如果遍历的点个数等于图的结点个数
    		flag = true;						//说明一次DFS遍历就搜索了所有的点
    	return flag;
    }

    BFS判断:

    • 从一个结点开始,访问与其关联的所有结点,将这些结点入队,重复此过程,直至队列为空。访问的结点构成一个连通分量,若该连通分量未包含所有结点,则无向图不连通。

    • 算法步骤及相关分析:

    a)算法步骤:
        从顶点v开始,访问v并置visited[v] = 1,将v入队;
        只要队列不空,就重复一下操作:
        队首顶点v出队;
        依次查找v所有邻接点w,如果visited[w]值为0,则访问w并置visited[w] = 1,将w放入队列中;
        进行判断,遍历visited数组,若有一个值不为1,则图就不连通。
    b)时间复杂度:BFS的时间复杂度主要是耗费在搜索邻接点上,与DFS类型,复杂度也是O(V^2)。
    c)空间复杂度:使用一个队列以及辅助数组visited[],空间复杂度也是O(V)。
    • 代码:

    此处Queue类为自写的,可简单实现。

    //BFS判断
    public boolean BFS() {
    	int count = 0 ;							//由于BFS不用递归,所以定义局部变量
    	boolean flag = false;
    	Queue Q = new Queue();				    //使用队列进行BFS
    	visited = new int[this.vertexNum];		//记录结点被访问情况
    	Q.add(0);								//首先访问0号结点
    	while(!Q.isEmpty()) {       			//队列未空进行如下操作
    		int s = Q.front();					//首先队首出列,并获取队首元素
    		Q.remove();
    		visited[s] = 1;						//队首被访问 
    		count ++;							//更新count值
    		for(int j=0; j<this.vertexNum; j++) {	//搜索与s结点相连的未被访问的结点
    			if(this.a[s][j] == 1 && visited[j] == 0 ){
    				    visited[j] = 1;				//访问这些点并将其入队
    					Q.add(j);
    			}							
    		}
    	}	
    	if(count == this.vertexNum)				//如果一次访问后遍历了所有点
    			flag = true;						//那么就是无向连通图
    
    	return flag;
    }

    Warshell判断:

    • 图中点与点之间构成边,也可以理解为存在边的两个结点之间存在关系,那么就可以使用Warshell算法求这些关系的传递闭包。Warshell算法更改矩阵的依据实质上是关系的继承,若结点i与结点j之间有边,那么结点 i 就继承结点 j 的连通关系。

    • 主要算法步骤及相关分析:

    a)算法步骤:
        复制邻接矩阵给矩阵A,即令A = M ;
        置变量i = 1;
        对所有j如果A[j,i] = 1,则k = 1,2,3,…,n
            A[j,k] = A[j,k] + A[i,k];
        i加1;
        如果i <= n,则转步骤(3),否则进入下一步判断;
        判断矩阵A,A中所有值都为1则无向图连通,否则不连通。
    b)时间复杂度:代码的主要时间开销在矩阵的计算上,复杂度为O(V^3)。
    c)空间复杂度:空间开销在于需要一个邻接矩阵的复制矩阵,复杂度为O(V^2)。
    • 代码:

    由于Java不支持整型的逻辑运算,所以针对上述算法步骤中的步骤3,需要构造一个与邻接矩阵(0-1)对应的Boolean型数组。

    或者步骤三的逻辑或直接化成整型的“+”,最后仍是判断矩阵是否存在0。

    //Warshell算法判断可达性矩阵
    public boolean Warshell() {
    	int count = 0;							//计算关键步运行次数以判断时间复杂度
    	boolean flag = true;
    	boolean[][] tmp = new boolean[this.vertexNum][this.vertexNum];
    	for(int i=0; i<this.vertexNum; i++)    //因为Java不支持0-1整型的逻辑运算
    		for(int j=0; j<this.vertexNum; j++)
    			if(this.a[i][j] == 1)
    				tmp[i][j] = true;			//使用boolean型进行逻辑运算
    			else
    				tmp[i][j] = false;
    	for(int i=0; i<this.vertexNum; i++)
    		for(int j=0; j<this.vertexNum; j++)
    			if(tmp[j][i])                   //如果j与i之间有关系
    				for(int k=0; k<this.vertexNum; k++) {
                        tmp[j][k] = tmp[j][k] ||  tmp[i][k];    //那么把i的关系传递给j
    					count ++;			//关键步计算
    				}
    	//System.out.println("count = " + count);
    	for(int i=0; i<this.vertexNum; i++)
    		for(int j=0; j<this.vertexNum; j++)
    			if(!tmp[i][j]) {					//遍历矩阵,只要有一个元素不为true
    				flag = false;				    //就说明无向图不连通
    				break;					        //退出,不必进行下面的计算
    			}
    
    	return flag;							//返回判断结果
    }
    • 改进尝试:

    其实这个改进效果并不好,而且其本事仍存在问题。解决简单问题没问题,但是图稍微复杂就会出现问题,若有大神有解决方案,请务必指教。

    改进效果,通过count变量的大小来体现,与上面的Warshell的count相比,有一定改进。

    ​
    由于无向图邻接矩阵的对称性,所以邻接矩阵的一个半角矩阵就包含了结点之间的关系。所以针对Warshell算法,我进行了相关修改,使其只求解一个半角矩阵。
        修改关系的继承规则:若结点i与结点j右边,那么i继承j的连通关系,并将i的连通关系同赋给j。
        改进关键步骤:
            对所有j,j∈[1,i],i∈[2,n],如果A[i,j] = 1,则对k∈[1,i]
                // A[i,k] = A[i,k] + A[j,k];  		//承载j列关系
                // A[i,k] = A[i,k] + A[k,j];			//承载j行关系
                A[i,k] = A[i,k] + A[j,k] + A[k.j]; 	//合并以上两行
                A[j,k] = A[j,k] + A[i,k];			//j与i的关系保持一样
        改进后:
            时间复杂度上,核心的的计算代码从n^3改进为n(n+1)(2n+1)/3,有一定改进;
            其次,空间复杂度上,图的存储只使用半角矩阵,空间复杂度降低一半,但还是O(V^2)。但就目前来说,仅仅是一次尝试,仍需改进。
    
    ​

    Union-Find判断:

    • 根据读入的边对进行集合的划分,读入的边对证明是相连的,那么我们就划分到一个集合中,然后读入新的边对就划分到新的集合中,一旦读入的边对(两个顶点)都在同一个集合中出现过,那么证明是相互连通的,如果读入的边对,两个顶点是出现在两个集合中,那么说明这两个集合至少通过该边是可以相连的,那么集合进行合并。重复以上过程,即可得到求解结果。最后只要判断所以结点是否在一个集合就可得到图是否连通,若在一个集合,则图连通,反之不连通。

    • 算法步骤及相关分析:

    a)算法:
        unionFindJudge():使用并查集进行集合判断
        关键代码:
            for(int j = 1; j<this.vertexNum; j++) 
    		    if(! union.isConnected(Search(this.vexs[0]), Search(this.vexs[j]))){
                    flag = false;
                   	break;
                }			
        相关解释分析:
            通过判断0号以外的元素是否和0号元素在一个集合中来对图的连通性进行判断,若所有元素都在同一集合中,那么图就是连通的。
    b)时间复杂度
        unionFindJudge():
            实际上,在构造并查集对象的过程中,已经调用很多次find函数,那么find函数再次调用,复杂度应该是O(1),即isConnect()调用一次的复杂度是O(1)。遍历一次图中所有点即可得到判断结果,复杂度是O(V)。
    c)空间复杂度
        空间消耗主要是两个辅助数组,所以复杂度是O(V)。
    • 代码:

    Union-Find,并查集类的实现请参考以下博文:http://www.cnblogs.com/noKing/p/8018609.html

    public boolean UnionFindJudge() {
    	boolean flag = true;
    	for(int j = 1; j<this.vertexNum; j++) {		//判断其他点是否和0号结点同一集合
    	    if(! union.isConnected(Search(this.vexs[0]), Search(this.vexs[j]) )){
    				flag = false;				// 只要有一个不和0号结点同一集合
    				break;					//就不连通,跳出循环
    		}
        }
        return flag ;
    }

    Tarjan判断:

    • 该算法可以用来求有向图的强连通分量。在无向图中,两点之间的连通其实等价于有向图中的强连通,都是互相可达的概念。所以,就可以使用Tarjan算法来得到无向图的“强”连通分量。如果无向图只有一个“强”连通分量,那么这个图就是一个连通图。
    • 主要算法步骤及相关分析:

    dfn[]:记录一个结点的搜索次序;

    low[]:记录结点或结点所在的子树能够追溯到的最早的栈中结点的次序号

    其实就是结点i,被访问的时间戳就是dfn[i],low[i]是其所在强连通分量的根。如果这两个值相等,说明i就是树根,那么栈中i上面的元素都是这个强连通分量的元素。

    中间的具体操作,实现原理请自己查阅。

    • 代码:

    ​​​​​​​此处判断依据是:进行一次判断,得到一个强连通分量,如果这个强连通分量的个数与图的点个数想法,就是连通图。

    本次代码使用数组模拟栈,读者可自由发挥,知道需要用到栈即可。

    • public boolean tarjan() {
          judgeTarjanCount = 0;					//记录一个连通分量的结点数
      	top = -1; t =0;							//top为栈顶,t为访问结点的时间,全局变量
      
      	tarjan(0);							    //从0号结点开始,只访问一个连通分量
      
      	if(judgeTarjanCount == this.vertexNum)	//如果该连通分量的结点数与图总结点数
      		return true;						//相同,那么图就是连通的
      	else									//否则不连通
      		return false;
      }
      private void tarjan(int current) {
      	dfn[current] = low[current] = ++ t;			//赋初值,为当前时间戳
      	z[++top]=current;  					        //入栈,用数组模拟栈
      	dist[current] = 1;  						//标记current已在栈中
      	for(int i=0;i<this.vertexNum;i++) {		//一个dfs过程
      		if(this.a[current][i] != 0) {			//有边
      			if(dfn[i] == 0) {				//i号结点未入栈
      				tarjan(i);  			 	//递归,访问
      				if(low[current]>low[i])		//low[current]=min{low[current],low[i]}
      					low[current] = low[i];
      			}else if(dist[i] == 1 && low[current] > dfn[i]) {	//若在栈中
      				low[current] = dfn[i]; 		
                                                   //low[current]=min{low[current],dfn[i]}
      			}
      		}
      	}
      	if(low[current] == dfn[current]) {			//如果相等,说明是连通分量
      		do {									    //将连通分量出栈
      			judgeTarjanCount ++;			        //记录连通分量的结点个数
      		}while(z[top--] != current);			
      	}
      }

       

    展开全文
  • 第一次写博客,不太会用,话不多说 直接上代码 详细可以看注释,无向图判断是否存在环比有向图相对复杂一点 ,需要判断访问的节点的临接表中的节点与父节点是否相同。 /** * @Description:判断无向图是否有环 深度...

    第一次写博客,不太会用,话不多说 直接上代码 详细可以看注释,无向图判断是否存在环比有向图相对复杂一点需要判断访问的节点的临接表中的节点与父节点是否相同。

    /**
     * @Description:判断无向图是否有环 深度优先遍历
     * 需要保存父节点
     * @Create 2020-04-03 21:04
     * @Email:1173748742@qq.com
     */
    public class IsHaveLoop {
        public static void main(String[] args) {
            IsHaveLoop isHaveLoop = new IsHaveLoop();
            int[][] graph = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {2, 4}};
            int n = 5;
            boolean haveLoop = isHaveLoop.isHaveLoop(graph, n);
            System.out.println(haveLoop);
        }
        /**
         * @param graph 图的连接边
         * @param n     图的节点个数
         * @return 是否存在环
         */
        public boolean isHaveLoop(int[][] graph, int n) {
            //这段代码可要可不要,可以提前判断结果
    //        if (graph.length >= n) {//当边数大于节点的个数时,必定存在环 自己可以画图推导
    //            return true;
    //        }
            //习惯上转换成临接表的形式
            List<Integer>[] adj = new ArrayList[n];
            for (int[] edg : graph) {
                int node1 = edg[0];
                int node2 = edg[1];
                if (adj[node1] == null) {
                    adj[node1] = new ArrayList<>();
                }
                if (adj[node2] == null) {
                    adj[node2] = new ArrayList<>();
                }
                adj[node1].add(node2);
                adj[node2].add(node1);
            }
            boolean[] visited = new boolean[n];//定义一个节点状态数组  判断是否访问过
            int[] a = {0};
            for (int i = 0; i < n; i++) {
                if (visited[i] == false) {//如果没有进行访问  则进行深度优先搜索回溯
                    dfsCycle(adj, i, -1, visited, a);//引用传递  函数内部修改值后退出函数可见
    //                System.out.println(a[0]);
                    if (a[0] == 1) {//只要有一次i循环时存在环路那就直接提前返回,说明存在环
                        return true;
                    }
                }
            }
            return a[0] == 1;
        }
    
    
        /**
         * @param adj     图的临接表
         * @param current 当前节点
         * @param parent  父节点
         * @param visited 判断是否访问
         * @param flag    是否存在环
         */
        private void dfsCycle(List<Integer>[] adj, int current, int parent, boolean[] visited, int[] flag) {
            visited[current] = true;//首先 访问当前节点   并进行标记
            List<Integer> list = adj[current];  //获取到当前节点能够到达的所有节点
            for (Integer can : list) {
                if (visited[can] == false) {//如果节点没有被访问过
                    dfsCycle(adj, can, current, visited, flag);//当前节点就是父节点,循环的节点就是子节点
                } else if (can != parent) {// 在节点被访问过的情况下 如果该节点不等于父节点  ,说明有环
                    flag[0] = 1;
                }
                //循环节点等于父节点的情况直接跳过,不用处理
            }
        }
    }
    

    更新2020-8-17

    添加一个使用并查集的方法。如果没有了解过并查集的话可以推荐看看这个视频,灯神讲的真好。思想就是不断对两个边进行联合,如果能够联合,这说明这条边加上去不能使集合产生环,继续向后遍历,如果存在一条边在进行联合时,没办法联合,说明会产生环。下边贴一下java代码。有的位置加了注释应该可以理解。

    package com.atschool.algorithm;
    
    import java.util.Arrays;
    
    /**
     * @Description:查看无向图中有没有环
     * @Create 2020-08-17 14:42
     * @Email:1173748742@qq.com
     */
    public class DisjoinSet {
    
        private int[] parent;
        private int[] rank;
    
        /**
         * 这里要求节点编号从0开始进行编号
         * 如果不是的话就不可以用数组来作为map,可能需要用两个HashMap才行
         *
         * @param edges 边
         * @param n     节点个数
         * @return
         */
        public boolean detecteCycle(int[][] edges, int n) {
            parent = new int[n];
            Arrays.fill(parent, -1);
            rank = new int[n];
            for (int i = 0; i < edges.length; i++) {
                int x = edges[i][0];
                int y = edges[i][1];
                if (!union(x, y)) {
                    return true;
                }
            }
            return false;
        }
    
        /**
         * 连接节点
         *
         * @param x
         * @param y
         * @return
         */
        private boolean union(int x, int y) {
            int x_root = find_root(x);
            int y_root = find_root(y);
            if (x_root == y_root) {
                return false;   // 连接失败  // 说明有环
            } else {
                // 可以进行连接
                // 下边的判断是为了降低树的高度  一个小优化
                if (rank[x_root] > rank[y_root]) {
                    parent[y_root] = x_root;
                } else if (rank[x_root] < rank[y_root]) {
                    parent[x_root] = y_root;
                } else {
                    parent[x_root] = y_root;
                    rank[y_root]++;
                }
                return true;
            }
        }
    
        /**
         * 找到根节点函数
         *
         * @param x
         * @return
         */
        private int find_root(int x) {
            int x_root = x;
            while (parent[x_root] != -1) {
                x_root = parent[x_root];
            }
            return x_root;
        }
    
    
        public static void main(String[] args) {
            DisjoinSet disjoinSet = new DisjoinSet();
            int[][] edges = {{0, 1}, {1, 2}, {1, 3}, {3, 4}, {2, 4}, {4, 5}}; // 有环
    //        int[][] edges = {{0, 1}, {1, 2}, {1, 3}, {3, 4}, {4, 5}};  无环
            boolean b = disjoinSet.detecteCycle(edges, 6);
            if (b) {
                System.out.println("detected cycle !");
            } else {
                System.out.println("no cycle!");
            }
        }
    }
    
    
    展开全文
  • 有向图中,用顶点表示活动,用有向边<Vi,Vj>表示活动i是活动j的必须条件,这种有向图为顶点表示活动的网简称为AOV网络。 在AOV网络中,如果活动Vi 必须在Vj 之前进行,则存在有向边<Vi,Vj>,并称Vi是...

    数据结构与算法——拓扑排序

    在有向图中,用顶点表示活动,用有向边<Vi,Vj>表示活动i是活动j的必须条件,这种有向图为顶点表示活动的网简称为AOV网络。

    在AOV网络中,如果活动Vi 必须在Vj 之前进行,则存在有向边<Vi,Vj>,并称Vi是Vj的直接前驱,Vj是Vi的直接后继;这种前驱与后继的关系具有传递性和反自反性,这要求AOV网络中不能出现回路,即有向环;因此,对于给定的AOV网络,必须判断它是否存在有向环。

    拓扑排序描述

      检测有向环可以通过对AOV网络进行拓扑排序,该过程将各个顶点排列成一个线性有序的序列,使得AOV网络中所有的前驱和后继关系都能得到满足。 如果拓扑排序能够将AOV网络的所有顶点都排入一个拓扑有序的序列中,则说明该AOV网络中没有有向环,否则AOV网络中必然存在有向环。AOV网络的顶点的拓扑有序序列不唯一。可以将拓扑排序看做是将图中的所有节点在一条水平线上的展开,图的所有边都从左指向右。

      用计算机专业的几门课程的学习次序来描述拓扑关系 ,显然对于一门课来说,必须先学习它的先导课程才能更好地学习这门课程,比如学数据结构必须先学习C语言和离散数学,而且先导课程中不能有环,否则没有尽头了

     

       而且还可以发现,如果两门课程之间没有直接或间接的先导关系,那么这两门课的学习先后是任意的(比如“C语言”和“离散数学”的学习顺序就是任意的),于是上述课程就可以排成一个水平展开的先后顺序,如下图

     

       拓扑排序的结果不唯一,比如“C语言”和“离散数学”就可以换下顺序,又或者把“计算机导论”向前放在任何一个位置都可以。总结一下就是,如果某一门课没有先导课程或是所有的先导课程都已经学习完毕,那么这门课就可以学习了。如果同时有多门这样的课,它们的学习顺序任意。

    算法实现

    这里多有向图的存储方式是邻接表,如上图所示,在邻接表的顶点数组中,另外添加一个域用于表示当前顶点的入度,数据结构如下:

    #include <iostream>
    using namespace std;

    #define MAXVER 14
    typedef struct EdgeNode 
    {
        int adjvex;
        int weight;
        struct EdgeNode* next;
    };

    typedef struct VertexNode 
    {
        int in;
        int data;
        EdgeNode* firstedge;
    }VertexNode,AdjList[MAXVER];


    typedef struct 
    {
        AdjList adjList;
        int numVertexes, numEdges;
    }graphAdjList,*GraphAdjList;

    拓扑排序的实现:

    bool TopoLogicalSort(GraphAdjList GL) 
    {
        EdgeNode* e;
        int i, k, gettop;
        int top = 0;
        int count = 0;
        int *stack;

        stack = (int*)malloc(GL->numVertexes*sizeof(int));
        for (size_t i = 0; i < GL->numVertexes; i++)
        {
            if (GL->adjList[i].in == 0) 
            {
                stack[++top] = i;//获取所有入读为0的顶点
            }
        }

        while (top != 0)//遍历所有入度为0的顶点
        {
            gettop = stack[top--];
            cout << GL->adjList[gettop].data << endl;
            count++;
            for (e = GL->adjList[gettop].firstedge; e; e = e->next) 
            {
                k = e->adjvex;
                /*
                *1. 对入度为0的节点的弧尾结点的入度减1
                *2. 对减一后的顶点判断,如果入度为0,入栈
                */
                if (!(--GL->adjList[k].in))
                    stack[++top] = k;
            }
        }

        if (count < GL->numVertexes)
            return false;//有环
        else
            return true;//找到拓扑排序序列为stack

    }

    算法描述

    对于一个有向无环图

    (1)统计所有节点的入度,对于入度为0的节点就可以分离出来,然后把这个节点指向所有的节点的入度−1−1。

    (2)重复(1),直到所有的节点都被分离出来,拓扑排序结束。

    (3)如果最后存在入度不为0的节点,那就说明有环,无解。

    解释一下,假设A为一个入度为0的结点,就表示A结点没有前驱结点,可以直接做,把A完成后,对于A的所有后继结点来说,前驱结点就完成了一个,入度进行−1。

     

    以上参考:

     

     

     

    展开全文
  • 【图结构专题】有向图

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

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

    千次阅读 2019-02-09 11:29:31
    在游戏里每人都一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为 Ti 的同学。 游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息...
  • 判断字符串是否为回文 python

    千次阅读 2021-01-13 08:15:12
    Java - 判断字符串是否是回文 首先,回文是指类似于“12345”,“abcdcba”的形式,即正念和反念都是一样的字符串 判断字符串是否是回文,这边介绍3种办法 将字符串翻转,判断翻转后的字符串和原字符串是否相等 public s...
  • 本题判断二元关系的性质:自反性、对称性、传递性。
  • 十六、图算法之有向图

    千次阅读 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
  • 有向图和无向图差别就是一句代码的差别 ,无向图中代码注释掉即可 有向图和有向网的差别也就是权值的差别 有向网需要赋予权值 有向图有连线自动赋值为1 深度优先采用递归方法(参考前面几篇文章,里面有具体的...
  • PGM:有向图模型:贝叶斯网络

    万次阅读 2016-09-09 17:26:10
     简言之,把某个研究系统中涉及的随机变量,根据是否条件独立绘制在一个有向图中,就形成了贝叶斯网络。其主要用来描述随机变量之间的条件依赖,用圈表示随机变量(random variables),用箭头表示条件依赖...
  • 一、传递性 、 二、传递性示例 、 三、传递性定理 、
  • 有向图找环

    千次阅读 2013-07-01 20:49:44
    有向图判断环与无向图不同,比如A->B A->C->B 若看做无向图是有环的,若看做有向图是无环的。这也比较好做,用拓扑排序的方法若最后能把所有顶点排好序就说明没有环。 (拓扑排序:一个无前驱的结点出发,然后珊...
  • 有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected),如果有向图G的每两个顶点都强连通,称G是一个强连通图.通俗的说法是:从图G内任意一个点出发,存在通向图G内任意一点的的一条路径....
  • HHUOJ 1650 算法7-12:有向无环的拓扑排序 题目描述 由某个集合上的一个偏序得到该集合上的一个全序,这个操作被称为拓扑排序。偏序和全序的定义分别如下: 若集合X上的关系R是自反的、反对称的和传递的,则称R是...
  • 在本项目中,子组件为Right,父组件为Experiment,如下所示: 1、先给子组件绑定一个点击事件,这个点击事件负责监听子组件的状态 2、在ts中给这个点击事件构造函数,函数里面定义一个事件名,这个事件名将负责...
  • 那么在有向图中要判断v到w是否可达,我们只需要以v为起点遍历一遍图,看能否遍历到w即可。当然在遍历时可以自己适当的加一些限制条件,提高算法效率,如:不需要遍历完所有顶点,只要遍历到w就可以结束遍历。所以...
  • 楼主你好,你所提及的传递函数是含有非最小相位环节的,这种题目仍然是可以用奈氏判据解决的.不过一些点需要注意.首先绘制概略奈氏,起点w→0,GH=5/(jw*(-1))故起点为+90°的无穷远点终点w→∞,GH=5/(jw*jw)为-180...
  • 传递闭包

    千次阅读 2020-11-13 22:37:10
    人话 : 建立传递闭包的过程,就是给定一个有向(无向),对于节点 i 和节点 j ,如果他们联通但不直接相连,我们就建一个 i 到 j 的边. 求法 我们可以用 Floyd 算法在 O(n3)O(n^3)O(n3) 的时间内求得传递闭包 我们用 d...
  • iOS之深入解析事件传递的响应链

    万次阅读 2021-08-30 20:44:37
    五、pointInside:withEvent: 判断触摸点是否在视图内: /** * @brief 判断一个点是否落在范围内 */ - (BOOL)pointInside:(CGPoint)point withEvent:(UIEvent *)event 如果现在要扩大按钮 2 的点击范围怎么办?...
  • 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-...
  • 相信很多人对于传递闭包(用关系矩阵求传递闭包怎么求)并不是非常的了解,因此小编在这里为您详解的讲解一下相关信息!方法:warshall法,即运行n次,每次使得MR[n][i],MR[i][n]都为1时使得MR[i][j]为1,否则还是为MR...
  • 传递函数

    千次阅读 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+...
  • 使用FormData格式在前后端传递数据

    千次阅读 2021-02-01 03:43:03
    为什么一定要使用formdata格式……很大原因是因为当时我犯蠢……前端肯定是JS了,具体不写了,使用Postman测试,后端语言是Java,框架Spring Boot,使用IntelliJ IDEA一、基本类型例:可以看到form-data只能传递键值...
  • UIView 事件传递

    千次阅读 2017-01-06 17:24:07
    : 悬浮的三个按钮下方一个可以点击的灰色区域,但是点击按钮之间的透明区域, 这三个按钮的contentView会响应这个点击事件,这时候需要让这个contentView不响应这个点击事件。 解决方法如下(将此方法...
  • 【Android笔记】用Intent在多个Activity之间传递参数

    万次阅读 多人点赞 2018-03-12 23:52:49
    一、下一个活动传递数据 1. 传递简单数据 2. 传递数据包 3. 传递值对象 (1) Serializable序列化接口 (2) Parcelable序列化接口 二、返回数据给上一个活动 一、下一个活动传递数据 前面...
  • 2. 无向图节点间的达关系为等价关系(具有自反性、对称性和传递性) 3. 达关系——连通分支 4. 点割集与边割集 5. 点割集的定义与示例(割点) 6.边割集的定义与示例(割边) 7. 点...
  • iOS 手势操作和事件传递响应链

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

    千次阅读 2019-05-30 22:01:33
    slot传递数值 parent.vue //在父组件里面通过slot-scope='p',{{p.属性}}来获取属性值,slot属性来获取子组件插槽,以name作为区分 < template > < B : color = "dataColor" > < div slot = "app" ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 233,443
精华内容 93,377
关键字:

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