Java图的遍历知识点（含面试大厂题和源码）

图的遍历是图论中的一个基本概念，主要指的是按照某种规则，系统地访问图中的每一个顶点，且每个顶点仅被访问一次。图遍历的主要目的是为了搜索图中的信息或检查图中是否存在特定的路径或圈。图的遍历算法主要有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索算法从图中的某个顶点开始，探索尽可能深的分支，直到找到目标顶点，或者遇到没有未探索的相邻顶点为止。然后回溯，探索下一个分支。

算法步骤：
1. 从起始顶点开始，将其标记为已访问。
2. 选择一个与当前顶点相连的未访问过的顶点，从该顶点再次执行DFS。
3. 重复步骤2，直到没有未访问的顶点为止。
4. 如果还有其他未访问的顶点，选择一个未访问的顶点，重复步骤1。

DFS常用于寻找所有可达的顶点、拓扑排序、检测环等。

广度优先搜索（BFS）

广度优先搜索算法从图的某个顶点开始，先访问距离起点最近的顶点，然后是次近的，依此类推，直到所有顶点都被访问过。

算法步骤：
1. 从起始顶点开始，将其标记为已访问，并加入队列中。
2. 从队列中取出一个顶点，并访问其所有未访问的邻接顶点，将它们标记为已访问，并加入队列。
3. 重复步骤2，直到队列为空。

BFS常用于寻找最短路径、层次遍历、广播消息等。

实现注意点

存储结构：图的遍历可以在图的两种主要存储结构上实现，即邻接矩阵和邻接表。
避免重复访问：无论是DFS还是BFS，在访问顶点时都需要标记顶点，避免重复访问。
选择起点：图的遍历可以从图中任意一个顶点开始，但不同的起点可能导致遍历的结果不同。

图的遍历是理解和实现更复杂图算法的基础，掌握DFS和BFS对于深入学习图论和解决实际问题非常重要。以下是三道常见的面试题目，涵盖了不同的编程概念和技术点，每个题目都附带了Java实现的源码。

题目1: 二叉树的右视图

题目描述：给定一个二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例：

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]

解题思路：使用广度优先搜索（BFS）进行层序遍历，每层遍历到的最后一个节点就是从右侧看到的节点。

Java代码实现：

java">import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                if (i == levelSize - 1) {
                    result.add(currentNode.val);
                }
                if (currentNode.left != null) queue.offer(currentNode.left);
                if (currentNode.right != null) queue.offer

(currentNode.right);
            }
        }
        return result;
    }
}

题目2: LRU缓存机制

题目描述：设计和实现一个 LRU (最近最少使用) 缓存机制。实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组 key-value。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

解题思路：使用哈希表加双向链表的方式实现。哈希表用于快速定位节点位置，双向链表用于表示节点间的先后顺序，便于快速添加和删除节点。

Java代码实现：

java">import java.util.*;

class LRUCache {

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
   

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        // 如果 key 存在，先通过哈希表定位，再移动到头部
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        } else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移动到头部
            node.value = value;
            moveToHead(node);
        }
    }
    
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

题目3: 合并K个升序链表

题目描述：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如上所示，将它们合并到一个升序链表中得到。

解题思路：可以使用优先队列来优化合并过程。优先队列可以帮助我们每次从各个链表中选出当前最小的元素添加到结果链表中。

Java代码实现：

java">class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        for (ListNode node : lists) {
            if (node != null) queue.add(node);
        }
        
        while (!queue.isEmpty()) {
            tail.next = queue.poll();
            tail = tail.next;
            if (tail.next != null) queue.add(tail.next);
        }
        
        return dummy.next;
    }
}