每日算法---207. 课程表   原题链接

     今天带来一题 拓扑规划 的题目,首先介绍一下拓扑规划,拓扑规划是一张 有向无环图,怎么确定一张图是有向无环图呢?我们可利用队列或者栈,下面介绍利用栈的用法,

      1.将所有入度为零的顶点入栈

      2.将栈顶出栈,删除顶点所有的边,(其实可以拿出任何一个入度为零的节点,但是我们使用的是栈,只能出栈顶)

      3.重复 1,2

      4.知道栈为空,则是一张拓扑图,否则,就证明中有环。

    利用队列的用法相似,并无太大区别。


    当然,处理利用拓扑判断一张有向图中是否有环之外,还可以利用深搜 来判断图中是否有环,作为每日必须算法,我们就不去一一介绍这些用法啦。那么废话不多说,我们来看看题目。


题目:(力扣)

     你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。

     在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

     给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?

示例1:

输入: 2, [[1,0]] 
输出: true

解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
示例2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

提示:

    1.输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵 。详情请参见图的表示法。

    2.你可以假定输入的先决条件中没有重复的边。

    3.1 <= numCourses <= 10^5


思路:

   题意很简单明了,让我们给出是不是可以完成全部课程。那么完成全部课程的前提条件是,不能存在 我们修课程A,必须完成课程B,但是我们修课程B,又必须完成课程A。这样一个环状。很显然,这是一个有向环,这当然是个简单的环,因为只有两个节点。那如果n个节点组成的环呢?这时候我们能想到,拓扑规划就是解决有向图中环问题,既然有了解题思路,那我们开始编写代码。


题解:(JAVA)

class Solution {
   public boolean canFinish(int numCourses, int[][] prerequisites) {
        int len = prerequisites.length;
        
        if(len == 0) return true;
        //创建栈
        Stack temp = new Stack();
        //存放入度
        int[] count = new int[numCourses];
        for (int i = 0; i < len; i++) {
            count[prerequisites[i][1]] ++;
        }
        //把所有入度为零的节点入栈
        for (int i = 0; i < numCourses; i++) {
            if(count[i] == 0) temp.push(i);
        }
        
        int m = 0 , result = 0;
        //只要栈不空,循环执行1,2
        while(!temp.isEmpty()) {
            //出栈一个节点,结构加一
            m = (Integer) temp.pop();
            result ++;
            //删掉所有与此节点连接的边
            for (int i = 0; i < len; i++) {
                if(prerequisites[i][0] == m) {
                    count[prerequisites[i][1]] --;
                    //删除边之后,如果入度为零,入栈
                    if(count[prerequisites[i][1]] == 0) 
                        temp.push(prerequisites[i][1]);
                }
            }
        }
        return result == numCourses;
    }
}


思考:

  其实最开始写这个题的时候,我用邻接矩阵 来表示的图,然后哪一列全部没有边(即为0,也表示入度为零),那么我就将与这列大小所对应的行全部置为0,然后去循环这样的操作,如果最后结果全部为零,那么这将是一张 有向无环图 ;不过这种算法有一个最大的缺点,也是我们不允许的,那就是算法时间复杂度达到了(n^3)。

那我还是把代码贴出来,也算是一种了解吧。


代码:(了解)

class Solution {
   public boolean canFinish(int numCourses, int[][] prerequisites) {
		int[] count = new int[numCourses];
		int sum = 0;
		//定义矩阵存放边
        int[][] flag = new int[numCourses][numCourses]; 
        for(int i = 0 ; i < prerequisites.length ; i ++) {
        		flag[ prerequisites[i][1] ][ prerequisites[i][0] ] = 1;
        }
        //定义
        for(int k = 0 ; k < numCourses ; k ++) {
          for (int i = 0; i < numCourses; i++) {
        	int temp = 0;
			for (int j = 0; j < numCourses; j++) {
				if(flag[j][i] != 0) {
					temp = 1;
					break;
				}
			}
			//如果是入度为零,删除边和顶点
			if(temp == 0) {
				for (int j = 0; j < numCourses; j++) {
					if(flag[i][j] != 0) flag[i][j] = 0;
				}
				if(count[i] != 1) sum ++;
				count[i] = 1;
			}
			System.out.println(sum);
		  }
          if(sum >= numCourses) return true;
        }
		return false;
    }
}