Java拓扑排序知识点（含面试大厂题和源码）

作者：我家自动化 | 2024-04-24 10:47:11

踩

在技术面试中，大厂可能会要求候选人实现或优化一些与图相关的算法，比如深度优先搜索（DFS）、广度优先搜索（BFS）和拓扑排序等。以下是三道与这些算法相关的面试题目，以及它们的Java源码示例。

1. 实现深度优先搜索（DFS）

题目：实现一个深度优先搜索算法，用于递归地遍历一个图的所有顶点。

源码：

import java.util.ArrayList;
import java.util.List;

public class DFSGraph {
    private final int V; // 顶点的数量
    private final List<List<Integer>> adj; // 邻接表

    public DFSGraph(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int dest) {
        adj.get(source).add(dest);
    }

    public void DFS(int v) {
        boolean[] visited = new boolean[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int i : adj.get(v)) {
            if (!visited[i]) {
                DFSUtil(i, visited);
            }
        }
    }

    public static void main(String[] args) {
        DFSGraph graph = new DFSGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        graph.DFS(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2. 实现广度优先搜索（BFS）

题目：实现一个广度优先搜索算法，用于遍历一个图，并找到最短路径。

源码：

import java.util.*;

public class BFSGraph {
    private final int V; // 顶点的数量
    private final List<List<Integer>> adj; // 邻接表

    public BFSGraph(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int dest) {
        adj.get(source).add(dest);
    }

    public void BFS(int s) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.offer(s);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");

            for (Integer i : adj.get(v)) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFSGraph graph = new BFSGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        graph.BFS(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

3. 检测图是否包含环

题目：给定一个图，使用DFS实现一个算法来检测图中是否存在环。

源码：

import java.util.ArrayList;
import java.util.List;

public class GraphCycleDetection {
    private final int V; // 顶点的数量
    private final List<List<Integer>> adj; // 邻接表
    private boolean[] visited;
    private boolean[] recStack;
    private boolean isCycle;

    public GraphCycleDetection(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int dest) {
        adj.get(source).add(dest);
    }

    public boolean isGraphCyclic() {
        visited = new boolean[V];
        recStack = new boolean[V];
        isCycle = false;

        for (int i = 0; i < V; i++) {
            if (isCycle) break;
            if (!visited[i]) {
                detectCycle(i);
            }
        }

        return isCycle;
    }

    private void detectCycle(int v) {
        if (isCycle) return;

        visited[v] = true;
        recStack[v] = true;

        for (Integer neighbour : adj.get(v)) {
            if (!visited[neighbour] && detectCycle(neighbour)) {
                isCycle = true;
                return;
            } else if (recStack[neighbour]) {
                isCycle = true;
                return;
            }
        }

        recStack[v] = false;
    }

    public static void main(String[] args) {
        GraphCycleDetection graph = new GraphCycleDetection(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1); // 此边创建环

        System.out.println("图中是否存在环: " + graph.isGraphCyclic());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

以上三道题目分别考察了DFS、BFS的实现以及如何使用DFS来检测图中的环。这些题目都是大厂面试中常见的题型，旨在考察候选人对图算法的理解和实现能力。在技术面试中，大厂可能会要求候选人实现或优化一些与图相关的算法，比如深度优先搜索（DFS）、广度优先搜索（BFS）和拓扑排序等。以下是三道与这些算法相关的面试题目，以及它们的Java源码示例。