精华内容
下载资源
问答
  • 简单方法判断邻接矩阵的有向图是否求解思路实现代码如有不同见解,欢迎讨论 求解思路 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题 课程表
    简单方法查找邻接矩阵有向图的有序集合
    如有不同见解,欢迎留言讨论

    展开全文
  • 今天师兄做笔试题,我也跟着看,碰到了一个要构建有向图判断节点是否的题。 另一位师兄说这个题可以用并查集做,并且做出来了,我用并查集试了试做不出来。。 我觉得这题大概是要用有向图做,考察...

    这里的代码参考了很多别人的代码和文章。。

    今天师兄做笔试题,我也跟着看,碰到了一个要构建有向图并判断节点是否有环的题。



    另一位师兄说这个题可以用并查集做,并且做出来了,我用并查集试了试做不出来。。

    我觉得这题大概是要用有向图做,考察有向图的构建及寻找有向环


    但是我只会对着书本抄代码构建有向图,不会寻找环,就尝试了一下用前不久做爬虫用到的广度遍历来寻找有向环。。


    import java.util.*;
    
    public class test
    {
    	public static void main(String[] args)
    	{
    		UF uf = new UF();
    		
    		//构建有向图
    		uf.AddDependency(1, 2);
    		uf.AddDependency(2, 4);
    		uf.AddDependency(4, 1);
    		uf.AddDependency(1, 6);
    		uf.AddDependency(6, 5);
    		uf.AddDependency(5, 7);
    		uf.AddDependency(4, 7);
    		
    		boolean isCycle;
    		
    		isCycle = uf.MouldelsCycularDependency(7);	//判断对应节点是否有环
    				
    		System.out.println(isCycle);
    	}
    }
    
    class UF
    {
    	final int N = 10;	//节点个数
    	//private static int E;
    	static Stack<Integer>[] adj;
    	
    	public UF()	//创建一个N个节点但没有边的图
    	{
    		adj = (Stack<Integer>[]) new Stack[N];
    		for(int n = 0; n < N;n++)
    		{
    			adj[n] = new Stack<Integer>();
    		}
    	}
    	
    	public static void addEdge(int v,int w)	//加边,v朝向w
    	{
    		adj[v].add(w);
    	}
    	
    	public static Stack<Integer> adj(int v)
    	{
    		return adj[v];
    	}
    	
    	public void clear()	
    	{
    		adj = (Stack<Integer>[]) new Stack[N];
    		for(int n = 0; n < N;n++)
    		{
    			adj[n] = new Stack<Integer>();
    		}
    	}
    	
    	public static void AddDependency(int Moduleld, int DependModuleld)	//往图里加边
    	{
    		int v = Moduleld;
    		int w = DependModuleld;
    		
    		addEdge(v,w);
    	}
    	 
    	public static boolean MouldelsCycularDependency(int Moduleld)	//判断是否有环
    	{
    		int v = Moduleld;
    		
    		HashMap<Integer,Boolean> oldMap = new HashMap<Integer,Boolean>();
    		
    		for(int i: adj(v))
    		{
    			oldMap.put(i, false);
    		}		
    		
    		oldMap = reDo(oldMap,v);
    		
    		if(oldMap.containsKey(v))
    		{
    
    			return true;
    		}
    
    		return false;
    	}
    	
    	/**
    	 * 广度优先遍历。递归,但是当N过大会StackOverFlow
    	 * @param oldMap
    	 * @param v 判断的节点
    	 * @return
    	 */
    	public static HashMap<Integer,Boolean> reDo(HashMap<Integer,Boolean> oldMap,int v)	
    	{
    		//定义newMap
    		HashMap<Integer,Boolean> newMap = new HashMap<Integer,Boolean>();
    		
    		for(Map.Entry<Integer, Boolean> k : oldMap.entrySet())
    		{
    			if(k.getValue() == false)
    			{
    				for(int i: adj(k.getKey()))
    				{
    					if(i == v)
    					{
    						oldMap.put(i, false);
    						return oldMap;
    					}
    					if(!oldMap.containsKey(i))
    					{
    						newMap.put(i, false);
    					}
    				}	
    				oldMap.replace(k.getKey(),false, true);
    			}
    		}
    		
    		//有新节点,继续遍历
    		if (!newMap.isEmpty())
    		{
    			oldMap.putAll(newMap);
    			oldMap.putAll(reDo(oldMap,v)); 
    		}
    		return oldMap;
    	}	
    }

    有一个致命的缺点,题给的节点数目超多,上面代码进行递归的时候八成会StackOverflow。。


    但还是很有成就感的,思考了一晚上至少把最基本功能实现了。。

    展开全文
  • 判断无向图/有向图是否存在

    千次阅读 2019-02-03 11:54:50
    利用DFS判断有向图是否存在,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,下面对这种方法及其实现进行详细的阐述。 首先,利用DFS判断无向图中是否换的原理是:若在深度优先搜索的...

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

    一 无向图

    1.利用DFS进行判断

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

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

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

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

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

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

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    #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<<"<-";//输出环

                        temp = father[temp];

                    }

                    cout<<temp<<endl;

                }

                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.拓扑排序

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

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    65

    66

    67

    68

    69

    70

    71

    72

    73

    74

    75

    76

    77

    78

    #include<iostream>

    #include<unordered_map>

    #include<queue>

    #include<cstring>

    #include<cstdlib>

    #include<cmath>

    #include<algorithm>

    #include<sstream>

    #include<set>

    #include<map>

    #include<stack>

    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<int> 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<<TuoPu(G)<<endl;

     

    }

     

      

     

    2.利用改进的DFS

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

    展开全文
  • 此题是美团2017春招实习生在线笔试题,题目是“如何判断有向图有没有回路”,这里给出两种解法以供参考。解法一:深度遍历假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有。我们用一个...

    此题是美团2017春招实习生在线笔试题,题目是“如何判断有向图有没有回路”,这里给出两种解法以供参考。

    解法一:深度遍历

    假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有环。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后结点都被访问过),然后判断每一个结点的深度遍历路线即可。
    因为采用邻接矩阵存储,一般至少需要将矩阵中元素的一半给过一下,由于矩阵元素个数为n^2, 因此时间复杂度就是O(n^2)。如果采用邻接表存储,则只存储了边结点(e条边,无向图是2e条边),加上表头结点为n(也就是顶点个数),因此时间复杂度为O(n+e)
    Java实现如下:

    import java.util.Scanner;
    
    public class test2 {
    	//邻接矩阵
    	static int[][] graph = new int[200][200];
    	//结点个数和边的个数
    	static int vNum,eNum;
    	//标记矩阵,0为当前结点未访问,1为访问过,-1表示当前结点后边的结点都被访问过。
    	static int[] color = new int[200];
    	//是否是DAG(有向无环图)
    	static boolean isDAG = true;
    	
    	//图的深度遍历函数
    	void DFS(int i){
    		System.out.println("正在访问结点"+i);
    		//结点i变为访问过的状态
    		color[i] = 1;
    		for(int j=1;j<=vNum;j++){
    			//如果当前结点有指向的结点
    			if(graph[i][j] != 0){	
    				//并且已经被访问过
    				if(color[j] == 1){
    					isDAG = false;//有环
    					break;
    				}else if(color[j] == -1){
    					//当前结点后边的结点都被访问过,直接跳至下一个结点
    					continue;
    				}else{
    					DFS(j);//否则递归访问
    				}
    			}
    		}
    		//遍历过所有相连的结点后,把本节点标记为-1
    		color[i] = -1;
    	}
    	
    	//创建图,以邻接矩阵表示
    	void create(){
    		Scanner sc = new Scanner(System.in);
    		System.out.println("正在创建图,请输入顶点个数vNum:");
    		vNum = sc.nextInt();
    		System.out.println("请输入边个数eNum:");
    		eNum = sc.nextInt();
    		//初始化邻接矩阵为0(如果3个顶点,顶点分别是1,2,3)
    		for(int i=1;i<=vNum;i++){
    			for(int j=1;j<=vNum;j++){
    				graph[i][j] = 0;
    			}
    		}
    		//输入边的情况
    		System.out.println("请输入边的头和尾:");
    		for(int k=1;k<=eNum;k++){
    			int i = sc.nextInt();
    			int j = sc.nextInt();
    			graph[i][j] = 1;
    		}
    		//初始化color数组为0,表示一开始所有顶点都未被访问过
    		for(int i=1;i<=vNum;i++){
    			color[i] = 0;
    		}
    	}
    	
    	public static void main(String[] args) {
    		test2 t = new test2();
    		t.create();
    		//保证每个节点都遍历到,排除有的结点没有边的情况
    		for(int i=1;i<=vNum;i++){
    			//该结点后边的结点都被访问过了,跳过它
    			if(color[i] == -1){
    				continue;
    			}
    			t.DFS(i);
    			if(!isDAG){
    				System.out.println("有环!");
    				break;
    			}
    		}
    		if(isDAG){
    			System.out.println("没环。。。");
    		}
    	}
    }
    

    测试输入输出如下:

    正在创建图,请输入顶点个数vNum:
    5
    请输入边个数eNum:
    5
    请输入边的头和尾:
    1 2
    2 3
    3 4
    2 5
    5 4
    正在访问结点1
    正在访问结点2
    正在访问结点3
    正在访问结点4
    正在访问结点5
    没环。。。
    

    解法二:拓扑排序

    方法是重复寻找一个入度为0的顶点,将该顶点从图中删除(即放进一个队列里存着,这个队列的顺序就是最后的拓扑排序,具体见程序),并将该结点及其所有的出边从图中删除(即该结点指向的结点的入度减1),最终若图中全为入度为1的点,则这些点至少组成一个回路。
    采用邻接矩阵存储时,遍历二维数组,求各顶点入度的时间复杂度是O(n^2)。 遍历所有结点,找出入度为0的结点的时间复杂度是O(n)。对于n个入度为0的结点,删除他们的出边的复杂度为O(n^2)。 所以总的复杂度为O(n^2)
    对于邻接表,遍历所有边,求各顶点入度的时间复杂度是O(e),即边的个数。遍历所有结点,找出入度为0的结点的时间复杂度是O(n),即顶点的个数。遍历所有边,删除入度为0的结点的出边的复杂度为O(e),即边的个数。所以总的时间复杂度是O(n+e)
    Java实现如下:

    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class test1 {
    	//邻接矩阵
    	static int[][] graph = new int[200][200];
    	//结点个数和边的个数
    	static int vNum,eNum;
    	//记录每个结点的入度,初始化为0
    	static int[] count = new int[200];
    	//用队列保存拓扑序列
    	static Queue<Integer> queue = new LinkedList<>();
    	
    	//拓扑排序
    	void topoSort(){
    		//入度为0的结点的个数,也就是入队个数
    		int number = 0;
    		//暂时存放拓扑序列
    		Queue<Integer> temp = new LinkedList<Integer>();
    		//遍历图中所有结点,找入度为0的结点删除(放进队列)
    		for(int i=1;i<=vNum;i++){
    			if(count[i] == 0){
    				queue.offer(i);
    			}
    		}
    		//删除这些被删除结点的出边(即对应结点入度减一)
    		while(!queue.isEmpty()){
    			int i = queue.peek();
    			temp.offer(queue.poll());
    			number++;
    			for(int j=1;j<=vNum;j++){
    				if(graph[i][j] == 1){
    					count[j] -= 1;
    					//出现了新的入度为0的结点,删除
    					if(count[j] == 0){
    						queue.offer(j);
    					}
    				}
    			}
    		}
    		if(number != vNum){
    			System.out.println("最后存在入度为1的结点,这个有向图是有回路的。");
    		}else{
    			System.out.println("这个有向图不存在回路,拓扑序列为:" + temp.toString());
    		}
    	}
    	
    	//创建图,以邻接矩阵表示
    	void create(){
    		Scanner sc = new Scanner(System.in);
    		System.out.println("正在创建图,请输入顶点个数vNum:");
    		vNum = sc.nextInt();
    		System.out.println("请输入边个数eNum:");
    		eNum = sc.nextInt();
    		//初始化邻接矩阵为0(如果3个顶点,顶点分别是1,2,3)
    		for(int i=1;i<=vNum;i++){
    			for(int j=1;j<=vNum;j++){
    				graph[i][j] = 0;
    			}
    		}
    		//输入边的情况
    		System.out.println("请输入边的头和尾:");
    		for(int k=1;k<=eNum;k++){
    			int i = sc.nextInt();
    			int j = sc.nextInt();
    			graph[i][j] = 1;
    		}
    		//计算每个结点的入度
    		Arrays.fill(count, 0);//先初始化为0
    		for(int i=1;i<=vNum;i++){
    			for(int j=1;j<=vNum;j++){
    				if(graph[i][j] == 1){
    					count[j] = count[j] + 1;
    				}
    			}
    		}
    	}
    	
    	public static void main(String[] args) {
    		test1 t = new test1();
    		t.create();
    		t.topoSort();
    	}
    }
    
    
    展开全文
  • 判断有向图是否

    千次阅读 2018-08-28 00:25:48
    要想对一副有向图进行拓扑排序,必须要保证有向图是无的,那么我们如何判断是否含有呢?我们可以使用深度优先搜索来遍历图,并创建一个数组来标记顶点是否已经在递归栈中,这样,当一个顶点指向的顶点已经在...
  • Python 判断 有向图 是否

    千次阅读 2017-04-17 20:48:48
    import numpy from numpy import * ...用到 numpy 模块,读取的 txt 文件为 有向图的连边,其中第一行 第一个数字 为 边的数量,第二个数字为 节点数 第二行及以后 前两个数字,第一个为 起点, 第二个为 落点。
  • 方法1:DFS判断有向图是否 对一个节点u进行DFS,判断是否能从u回到自己这个节点,即是否存在u到u的回路。 color数组代表每个节点的状态 -1代表还没访问,0代表正在被访问,1代表访问结束 如果一个状态为0的节点...
  • 两种方式判断有向图是否-python实现 1. DFS判断有向图是否 假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后...
  • 判断有向图是否有三种方法:拓扑排序、深度遍历+回溯、深度遍历 + 判断后退边 这里使用 拓扑排序 和 深度遍历 + 回溯判断是不是环。使用 深度遍历 + 判断后退边找出个数 以及环中元素 1、拓扑排序 ...
  • 【三种解法】判断有向图是否

    千次阅读 2020-07-17 12:03:38
    我们最常用的是topsort来判断是否有环,因为这个方法简单。 我去网上找了很多关于如何用dfs来判断的算法,可谓五花八门且很容易被hack掉。 以上,所以写这篇文章来总结一下我知道的且常用有效的三种判断方法。 ...
  • 1. 判断有向图是否 给定有向图,检查该图是否包含循环。如果给定图包含至少一个循环,则函数应返回true,否则返回false。 1.1. 方法一:DFS 1.1.1. 思路 对一个图进行DFS, 则DFS的路径可以生成一个棵树。 ...
  • Java 判断有向图是否 拓扑排序

    千次阅读 2020-03-13 22:32:27
    拓扑排序,先从入度为0的顶点入手,之后若产生入度为0的顶点就不断加入队列 import java.util.*; public class Demo1{ public static void ... } } } /*方法一:遍历所有顶点,是否出度和入度都为0 * for(int i=1;i
  • 判断有向图是否及环中元素

    千次阅读 多人点赞 2017-08-17 13:04:40
    在访问节点n时,若该节点不在栈中,则将其入栈,否则说明存在,并且环中元素为栈中从节点n到栈顶的所有点。 # 输入:第一行为中的边数,余下行为两个节点组成的边,以空格划分 例: 8 1 2 2 3 3 1 3 4 5 4 5 ...
  • 判断有向图是否存在

    千次阅读 多人点赞 2018-09-04 22:36:43
    简介  前面讨论的很多文章里,都是...和无向图比起来,有向图更加多了一种出入度的概念。因为方向的有向性,很多以前在无向图里看起来比较简单的问题在这里会变得更加有意思。   有向图定义  一个常用的有向...
  • DFS判断有向图是否存在 对一个节点有三种情况,还未访问,正在访问,访问结束 我们用0,1,-1,正在访问表示还在递归中未出来,如果相连节点都正在访问 说明在DFS过程中一条道路上访问了两次同一个节点,这说明有...
  • 判断一个图是否 无向图 有向图

    千次阅读 2013-05-06 21:35:22
    判断一个图是否 无向图 有向图 没有找到原文出处,请参考一下链接: http://www.cnblogs.com/hiside/archive/2010/12/01/1893878.html ...方法1:
  • 判断有向图是否存在

    千次阅读 2017-03-18 10:58:10
    步骤1:从0跳(节点自身)开始根据邻接矩阵逐跳添加节点:即如果节点i经过k-1跳可达节点m,且m存在到n的有向边;则i经过k跳可达n(注意处理i到n的其他更短路径),将n添加到nodeset_dst[i][k][ ]数组中;并将nodeset_...
  • /*判断一个有向图是否,使用DFS的改进算法来判断  设置标志位C,如果C=0,此节点没被访问过  如果C=-1,此节点被访问过且正在遍历其子节点,有  如果C=1,此节点被访问过且其字节点也都被访问过,没...
  • 0.1.2有向图判断是否存在 0.2无向图判 0.3有向图 1.有向图的拓扑排序 2.关键路径  2.1.邻接链表存储AOE网  2.1.1拓扑排序: bool TopologicalOrder(): 2.1.2关键路径:bool CriticalPath() 求...
  • 【0】README0.1) 本文总结于 数据结构与算法分析, 源代码均为原创, 旨在 理解 “DFS应用——遍历有向图+判断有向图是否有圈” 的idea 并用源代码加以实现 ; 0.2) 判断有向图是否有圈的rule—— 一个有向图是无...
  • 判断有向图是否(python)

    千次阅读 2019-09-11 23:00:14
    2020英语流利说算法笔试题 没做出来,结束了学习一下。 思路是记下每个节点的入和出的数量,不断删去只出不入(或只入不出)的边,直到不能继续删除,再观察此时是否还剩有有度的节点...''' 给定一个有向图,矩阵...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 64,073
精华内容 25,629
关键字:

哪个方法判断有向图是否有环