频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
Course Schedule:判断有向图是否有环
2018-02-01 14:29:21         来源:小雄鹿的博客  
收藏   我要投稿

Course Schedule:判断有向图是否有环。

There are a total ofncourses you have to take, labeled from0ton - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]

Given the total number of courses and a list of prerequisitepairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

  1. The input prerequisites is a graph represented bya list of edges, not adjacency matrices. Read more abouthow a graph is represented.You may assume that there are no duplicate edges in the input prerequisites.

    click to show more hints.

    Hints:
    1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.Topological Sort via DFS- A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.Topological sort could also be done viaBFS. 思路:提示里已经说得很明白了,有dfs或者bfs做拓扑排序判断是否有环。

      我是用dfs,假设每个定点有三种状态:未访问、正在访问、访问完成。当沿着一条边深度优先访问时碰到了正在访问的顶点,则说明有环,否则未发现环。访问结束记得将访问中的状态改为访问完成。

      class Solution {
          public boolean canFinish(int numCourses, int[][] prerequisites) {
              if(numCourses == 0) return true;
              if(prerequisites.length == 0) return true;
              HashMap> graph = new HashMap>();
              for(int[] edge:prerequisites){//构造图
                  if(graph.get(edge[1]) == null){
                      ArrayList l = new ArrayList();
                      l.add(edge[0]);
                      graph.put(edge[1],l);
                  }else{
                      graph.get(edge[1]).add(edge[0]);
                  }
              }
              //dfs判断图是否有环,采用三种颜色:0 未访问 、1 正在访问 、 2 已访问 
              int[] state = new int[numCourses];
              boolean res = true;
              for(int i = 0 ;i < numCourses; i++ ){
                  res = res && dfs(graph,state,i); 
                  if(res == false) return false;
              }
              return res;             
          }
          
          public boolean dfs(HashMap> graph,int[] state,int vertex){
              if(state[vertex] == 1){
                  return false;
              }else if(state[vertex] == 2){
                  return true;
              }else{
                  state[vertex] = 1;
                  List edges = graph.get(vertex);
                  if(edges == null) {
                      state[vertex] = 2;
                      return true;
                  }
                  boolean res = true;
                  for(int v : edges){
                      res = res && dfs(graph,state,v);
                  }
                  state[vertex] = 2;
                  return res;
              }
          }
      }
      bfs的方式则从入度的角度考虑。类似于人工考察是否有环,先将入度为0的顶点排除,且将之指向的顶点的入度减1,不断重复,直到所有顶点均被排除则证明无环,否则便是无环。下面是jiayuliu961的答案。比我的简洁多了。
      public boolean canFinish(int numCourses, int[][] prerequisites) {
          int[][] matrix = new int[numCourses][numCourses]; // i -> j
          int[] indegree = new int[numCourses];
          
          for (int i=0; i queue = new LinkedList();
          for (int i=0; i
       
点击复制链接 与好友分享!回本站首页
上一篇:SylixOS定时器测试误差分析
下一篇:编程开发分布式Session介绍
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站