当前位置： 面试刷题>> 课程表(经典算法150题)
### 题目描述
假设你正在设计一个大学课程表系统，其中课程之间可能存在先修关系。例如，学习课程B之前必须先完成课程A。现在给你一个课程数量n和一个二维数组`prerequisites`，其中`prerequisites[i] = [ai, bi]`表示学习课程`bi`之前必须先完成课程`ai`。
你的任务是编写一个函数来判断是否存在一个合理的学习顺序，使得所有的课程都可以被学习。如果存在这样的顺序，则返回`true`；否则返回`false`。
**注意**：
1. 输入的课程数量n是一个正整数。
2. `prerequisites`中的每个课程对`[ai, bi]`都是唯一的，并且保证`bi`不会在`ai`的先修课程列表中。
### 示例
**示例 1**:
```
输入: n = 2, prerequisites = [[1,0]]
输出: true
解释: 存在一种学习顺序 [0,1]，其中 0 是 1 的先修课程。
```
**示例 2**:
```
输入: n = 2, prerequisites = [[1,0],[0,1]]
输出: false
解释: 不存在一种学习顺序可以同时满足 0 是 1 的先修课程和 1 是 0 的先修课程。
```
### PHP 示例代码
```php
function canFinish($numCourses, $prerequisites) {
// 构建邻接表表示课程之间的先修关系
$graph = array_fill(0, $numCourses, []);
for ($i = 0; $i < count($prerequisites); $i++) {
$graph[$prerequisites[$i][1]][] = $prerequisites[$i][0];
}
// 初始化访问状态数组
$visited = array_fill(0, $numCourses, 0); // 0: 未访问, 1: 正在访问, 2: 已访问
// 遍历每个课程，检查是否存在环
for ($i = 0; $i < $numCourses; $i++) {
if (hasCycle($graph, $visited, $i)) {
return false;
}
}
return true;
}
function hasCycle($graph, &$visited, $course) {
if ($visited[$course] == 1) {
// 发现环
return true;
}
if ($visited[$course] == 2) {
// 课程已访问过，无环
return false;
}
$visited[$course] = 1; // 标记为正在访问
foreach ($graph[$course] as $preReq) {
if (hasCycle($graph, $visited, $preReq)) {
return true;
}
}
$visited[$course] = 2; // 标记为已访问
return false;
}
```
### Python 示例代码
```python
from collections import defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
for pre, course in prerequisites:
graph[course].append(pre)
visited = [0] * numCourses # 0: 未访问, 1: 正在访问, 2: 已访问
def dfs(course):
if visited[course] == 1:
return True
if visited[course] == 2:
return False
visited[course] = 1
for pre in graph[course]:
if dfs(pre):
return True
visited[course] = 2
return False
for i in range(numCourses):
if dfs(i):
return False
return True
```
### JavaScript 示例代码
```javascript
function canFinish(numCourses, prerequisites) {
const graph = new Array(numCourses).fill(0).map(() => []);
for (const [pre, course] of prerequisites) {
graph[course].push(pre);
}
const visited = new Array(numCourses).fill(0); // 0: 未访问, 1: 正在访问, 2: 已访问
function dfs(course) {
if (visited[course] === 1) {
return true;
}
if (visited[course] === 2) {
return false;
}
visited[course] = 1;
for (const pre of graph[course]) {
if (dfs(pre)) {
return true;
}
}
visited[course] = 2;
return false;
}
for (let i = 0; i < numCourses; i++) {
if (dfs(i)) {
return false;
}
}
return true;
}
```
以上代码均实现了检查课程表中是否存在合理的学习顺序的逻辑，使用了深度优先搜索（DFS）来检测图中是否存在环，从而判断是否存在合理的学习顺序。