当前位置： 面试刷题>> 课程表Ⅰ (经典算法题500道)
### 题目描述补充
**课程表Ⅰ**
给定一个整数n，表示有n门课程，编号从1到n。再给定一个二维数组`edges`，其中`edges[i] = [from_course, to_course]`表示存在一门先修课关系，即在学习`to_course`之前必须先完成`from_course`。
现在请你判断是否存在一种学习顺序，使得可以学完所有课程。如果存在这样的顺序，则返回`true`；否则返回`false`。
**注意**：
- 课程中可能存在循环依赖。
- 输入的先修关系都是有效的，即`from_course`不会等于`to_course`。
### 示例
**输入**：
```
n = 2
edges = [[1, 0]]
```
**输出**：
```
true
```
**解释**：存在一种学习顺序，例如先学习课程0再学习课程1。
**输入**：
```
n = 2
edges = [[1, 0], [0, 1]]
```
**输出**：
```
false
```
**解释**：课程之间存在循环依赖，无法完成所有课程的学习。
### PHP 示例代码
```php
function canFinish($numCourses, $prerequisites) {
$graph = array_fill(0, $numCourses, []);
$visited = array_fill(0, $numCourses, 0); // 0: 未访问, 1: 访问中, 2: 已完成
foreach ($prerequisites as $edge) {
$graph[$edge[1]][] = $edge[0];
}
for ($i = 0; $i < $numCourses; $i++) {
if (!dfs($i, $graph, $visited)) {
return false;
}
}
return true;
function dfs($course, $graph, &$visited) {
if ($visited[$course] == 1) {
return false; // 发现环
}
if ($visited[$course] == 2) {
return true; // 已访问过，无需再检查
}
$visited[$course] = 1;
foreach ($graph[$course] as $preReq) {
if (!dfs($preReq, $graph, $visited)) {
return false;
}
}
$visited[$course] = 2;
return true;
}
}
// 示例用法
$numCourses = 2;
$prerequisites = [[1, 0], [0, 1]];
echo canFinish($numCourses, $prerequisites) ? "true" : "false";
```
### Python 示例代码
```python
def canFinish(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
visited = [0] * numCourses # 0: 未访问, 1: 访问中, 2: 已完成
for prereq in prerequisites:
graph[prereq[1]].append(prereq[0])
for i in range(numCourses):
if not dfs(i, graph, visited):
return False
return True
def dfs(course, graph, visited):
if visited[course] == 1:
return False # 发现环
if visited[course] == 2:
return True # 已访问过，无需再检查
visited[course] = 1
for preReq in graph[course]:
if not dfs(preReq, graph, visited):
return False
visited[course] = 2
return True
# 示例用法
numCourses = 2
prerequisites = [[1, 0], [0, 1]]
print(canFinish(numCourses, prerequisites))
```
### JavaScript 示例代码
```javascript
function canFinish(numCourses, prerequisites) {
const graph = new Array(numCourses).fill(null).map(() => []);
const visited = new Array(numCourses).fill(0); // 0: 未访问, 1: 访问中, 2: 已完成
for (const [to, from] of prerequisites) {
graph[to].push(from);
}
for (let i = 0; i < numCourses; i++) {
if (!dfs(i, graph, visited)) {
return false;
}
}
return true;
function dfs(course, graph, visited) {
if (visited[course] === 1) {
return false; // 发现环
}
if (visited[course] === 2) {
return true; // 已访问过，无需再检查
}
visited[course] = 1;
for (const preReq of graph[course]) {
if (!dfs(preReq, graph, visited)) {
return false;
}
}
visited[course] = 2;
return true;
}
}
// 示例用法
const numCourses = 2;
const prerequisites = [[1, 0], [0, 1]];
console.log(canFinish(numCourses, prerequisites));
```
**码小课** 网站中有更多关于算法和数据结构的相关内容分享给大家学习，包括更复杂的课程表问题、图论问题、深度优先搜索（DFS）和广度优先搜索（BFS）等算法的深入讲解和实战应用。