第二十八天

一、核心知识点梳理

1. 图的定义与本质：由顶点（Vertex）和边（Edge）组成的非线性数据结构，用于描述多对多的关联关系（区别于树的父子层级关系）。
2. 关键概念区分：

• 有向图（边带方向，如社交软件的关注关系） vs 无向图（边无方向，如朋友关系）；
• 加权图（边含权重，如地图路径距离） vs 无权图；
• 连通图（任意两顶点可达） vs 非连通图，环（顶点到自身的边）、度（顶点关联的边数）。
  3. 存储方式（重点）：
• 邻接矩阵：二维数组  graph[i][j]  表示顶点i与j的关联（有权值则存权重，无则存0/1），优点是查询快，缺点是空间复杂度O(n²)（n为顶点数）；
• 邻接表：数组+链表/ArrayList，数组存顶点，链表存该顶点的邻接顶点，优点是空间高效，适合稀疏图，缺点是查询需遍历链表。
  4. 核心算法（含代码思路）：
• 遍历算法：
• 深度优先搜索（DFS）：递归/栈实现，“一条路走到底再回溯”，适合路径查找、连通性判断；
  代码框架（邻接表）： void dfs(int v, boolean[] visited) { visited[v] = true; for (int neighbor : adj[v]) { if (!visited[neighbor]) dfs(neighbor, visited); } }
• 广度优先搜索（BFS）：队列实现，“逐层遍历”，适合最短路径（无权图）、层级遍历；
  代码框架（邻接表）： Queue q = new LinkedList<>(); q.add(start); visited[start] = true; while (!q.isEmpty()) { int v = q.poll(); for (int neighbor : adj[v]) { if (!visited[neighbor]) { visited[neighbor] = true; q.add(neighbor); } } }
• 最短路径：迪杰斯特拉算法（加权图，无负权边）、弗洛伊德算法（多源最短路径）。

二、实践案例与问题

1. 动手实现：用Java实现无向图的邻接表存储，完成DFS和BFS遍历（顶点为整数，边通过addEdge方法添加）。
2. 遇到的问题：

• 递归实现DFS时，顶点编号从0还是1开始容易混淆，需统一初始化逻辑；
• BFS中队列的入队时机需配合visited数组，避免重复访问。
  3. 解决方案：定义顶点编号从0开始，初始化visited数组时长度与顶点数一致；入队前先标记visited为true，防止同一顶点多次入队。

三、总结与明日计划

1. 今日收获：明确图的应用场景（地图导航、社交网络、拓扑排序），掌握两种存储方式的优缺点及适用场景，能独立写出DFS和BFS的核心代码。
2. 待巩固点：加权图的存储的实现、迪杰斯特拉算法的代码落地。