在计算机领域的面试中，图论相关的问题是常见的考察点，像岛屿数量、课程表问题以及最短路径问题，都涉及图论的知识。下面我们就来详细探讨这些问题的解法。
一、岛屿数量问题
应用场景
岛屿数量问题在很多实际场景中都有应用。比如在地理信息系统（GIS）中，我们可能需要统计一片海域中岛屿的数量；在图像处理里，也可以把图像中的连通区域看作“岛屿”来进行分析。
问题描述
给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。一个岛屿被水包围，并且它是通过水平或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
解法思路
我们可以使用深度优先搜索（DFS）或者广度优先搜索（BFS）来解决这个问题。这里以 DFS 为例。
示例代码（Java 技术栈）
public class NumberOfIslands {
// 定义四个方向：上、下、左、右
private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
// 遇到陆地，进行 DFS 标记
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
int rows = grid.length;
int cols = grid[0].length;
// 检查边界条件和是否为陆地
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1') {
return;
}
// 标记为已访问
grid[i][j] = '0';
for (int[] dir : DIRECTIONS) {
int newRow = i + dir[0];
int newCol = j + dir[1];
// 递归调用 DFS
dfs(grid, newRow, newCol);
}
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
NumberOfIslands solution = new NumberOfIslands();
int islands = solution.numIslands(grid);
System.out.println("岛屿数量: " + islands);
}
}
代码解释
numIslands方法：遍历整个二维网格，当遇到陆地（'1'）时，调用dfs方法进行深度优先搜索，并将岛屿数量加 1。dfs方法：将当前陆地标记为已访问（'0'），然后递归地对其上下左右相邻的陆地进行搜索。
技术优缺点
- 优点：DFS 实现简单，代码量少，空间复杂度相对较低。
- 缺点：在处理大规模数据时，可能会导致栈溢出，因为递归调用会使用系统栈。
注意事项
- 要注意边界条件的判断，避免越界访问。
- 标记已访问的节点，防止重复访问。
二、课程表问题
应用场景
课程表问题在学校的课程安排、项目任务调度等场景中非常有用。比如学校要安排一系列课程，有些课程有先修要求，我们需要判断是否能合理安排课程顺序。
问题描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。判断是否可能完成所有课程的学习。
解法思路
这是一个典型的拓扑排序问题。我们可以使用 Kahn 算法或者深度优先搜索来解决。这里以 Kahn 算法为例。
示例代码（Java 技术栈）
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class CourseSchedule {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 存储每个节点的入度
int[] inDegree = new int[numCourses];
// 存储图的邻接表
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adjList.add(new ArrayList<>());
}
// 构建图和入度数组
for (int[] prerequisite : prerequisites) {
int ai = prerequisite[0];
int bi = prerequisite[1];
adjList.get(bi).add(ai);
inDegree[ai]++;
}
// 存储入度为 0 的节点
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
count++;
// 遍历该节点的所有邻接节点
for (int neighbor : adjList.get(node)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return count == numCourses;
}
public static void main(String[] args) {
int numCourses = 2;
int[][] prerequisites = {{1, 0}};
CourseSchedule solution = new CourseSchedule();
boolean canFinish = solution.canFinish(numCourses, prerequisites);
System.out.println("是否能完成所有课程: " + canFinish);
}
}
代码解释
- 首先构建图的邻接表和入度数组。
- 将入度为 0 的节点加入队列。
- 不断从队列中取出节点，减少其邻接节点的入度，如果邻接节点的入度变为 0，则加入队列。
- 最后判断完成的课程数量是否等于总课程数。
技术优缺点
- 优点：Kahn 算法时间复杂度为 O(V + E)，其中 V 是节点数，E 是边数，效率较高。
- 缺点：需要额外的空间来存储入度数组和邻接表。
注意事项
- 要正确构建邻接表和入度数组。
- 处理入度为 0 的节点时要注意顺序。
三、最短路径问题
应用场景
最短路径问题在地图导航、物流配送等领域有广泛应用。比如在地图导航中，我们需要找到从起点到终点的最短路径。
问题描述
给定一个带权有向图，找到从起点到终点的最短路径。
解法思路
常见的最短路径算法有 Dijkstra 算法和 Bellman - Ford 算法。这里以 Dijkstra 算法为例。
示例代码（Java 技术栈）
import java.util.*;
public class Dijkstra {
private static final int INF = Integer.MAX_VALUE;
public int[] dijkstra(int[][] graph, int start) {
int n = graph.length;
// 存储最短距离
int[] dist = new int[n];
// 标记节点是否已访问
boolean[] visited = new boolean[n];
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0];
if (visited[u]) {
continue;
}
visited[u] = true;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}
public static void main(String[] args) {
int[][] graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
Dijkstra solution = new Dijkstra();
int[] dist = solution.dijkstra(graph, 0);
for (int i = 0; i < dist.length; i++) {
System.out.println("从节点 0 到节点 " + i + " 的最短距离: " + dist[i]);
}
}
}
代码解释
- 初始化距离数组
dist和访问标记数组visited。 - 使用优先队列存储待处理的节点，按照距离从小到大排序。
- 不断从优先队列中取出距离最小的节点，更新其邻接节点的距离。
技术优缺点
- 优点：Dijkstra 算法效率较高，时间复杂度为 O((V + E) log V)。
- 缺点：不能处理负权边。
注意事项
- 要正确初始化距离数组和优先队列。
- 处理负权边时不能使用 Dijkstra 算法，需要使用 Bellman - Ford 算法。
四、文章总结
本文详细介绍了图论中岛屿数量、课程表问题和最短路径问题的解法。岛屿数量问题可以使用 DFS 或 BFS 来解决，课程表问题可以使用拓扑排序（如 Kahn 算法），最短路径问题可以使用 Dijkstra 算法（适用于无负权边的图）。这些问题在实际应用中都有广泛的场景，掌握它们的解法对于解决相关问题非常有帮助。在实际应用中，我们需要根据具体情况选择合适的算法，并注意算法的优缺点和使用条件。
评论