尧图网页设计 
数据结构“图”章节核心知识点与代码实现一、 图的基础知识点知识点核心内容图的定义图G(V, E)由顶点集合 V和边集合 E组成用于表示多对多关系。图的分类1. 有向图 vs 无向图边是否有方向。2. 带权图 vs 无权图边是否有权重。3. 连通图 vs 非连通图任意两顶点间是否有路径。图的存储结构1. 邻接矩阵二维数组适合稠密图查询边快O(1)。2. 邻接表数组链表适合稀疏图节省空间。3. 邻接多重表/十字链表用于优化特定操作。图的遍历算法1. 深度优先搜索 (DFS)递归或栈实现探索图的深度。2. 广度优先搜索 (BFS)队列实现探索图的广度。图的应用算法1. 最短路径Dijkstra单源无负权、Floyd多源。2. 最小生成树Prim加点法、Kruskal加边法。3. 拓扑排序用于有向无环图 (DAG) 的任务排序。4. 关键路径AOE网中决定项目工期的路径。二、 核心代码段Java实现1. 图的邻接表表示与DFS/BFS遍历import java.util.*; // 使用邻接表表示无向图 class Graph { private int V; // 顶点数 private LinkedListInteger adj[]; // 邻接表 // 构造函数 Graph(int v) { V v; adj new LinkedList[v]; for (int i 0; i v; i) { adj[i] new LinkedList(); } } // 添加边无向图 void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); // 有向图则注释此行 } //深度优先搜索 (DFS) 递归实现 void DFSUtil(int v, boolean visited[]) { visited[v] true; // 标记当前节点为已访问 System.out.print(v ); // 递归访问所有未访问的邻接顶点 for (int n : adj[v]) { if (!visited[n]) { DFSUtil(n, visited); } } } void DFS(int v) { boolean visited[] new boolean[V]; DFSUtil(v, visited); } // 广度优先搜索 (BFS) 队列实现 void BFS(int s) { boolean visited[] new boolean[V]; LinkedListInteger queue new LinkedList(); visited[s] true; queue.add(s); while (!queue.isEmpty()) { s queue.poll(); // 从队列头部取出顶点 System.out.print(s ); // 将该顶点的所有未访问邻接点入队 for (int n : adj[s]) { if (!visited[n]) { visited[n] true; queue.add(n); } } } } } public class Main { public static void main(String args[]) { Graph g new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println(从顶点0开始的深度优先遍历:); g.DFS(0); // 输出: 0 1 2 3 System.out.println( 从顶点0开始的广度优先遍历:); g.BFS(0); // 输出: 0 1 2 3 } }2. Dijkstra算法求单源最短路径邻接矩阵无负权import java.util.*; class DijkstraAlgorithm { // 辅助方法找到未处理顶点中距离最小的顶点索引 int minDistance(int dist[], Boolean sptSet[], int V) { int min Integer.MAX_VALUE, minIndex -1; for (int v 0; v V; v) { if (!sptSet[v] dist[v] min) { min dist[v]; minIndex v; } } return minIndex; } // 打印最短路径结果 void printSolution(int dist[], int V) { System.out.println(顶点 \t距源点距离); for (int i 0; i V; i) { System.out.println(i \t\t dist[i]); } } // Dijkstra算法核心实现 void dijkstra(int graph[][], int src, int V) { int dist[] new int[V]; // 存储源点到各点的最短距离 Boolean sptSet[] new Boolean[V]; // 标记顶点是否已处理 // 初始化距离设为无穷大集合设为空 for (int i 0; i V; i) { dist[i] Integer.MAX_VALUE; sptSet[i] false; } dist[src] 0; // 源点到自身的距离为0 // 循环 V-1 次每次确定一个顶点的最短路径 for (int count 0; count V - 1; count) { // 选取未处理顶点中距离最小的顶点u int u minDistance(dist, sptSet, V); sptSet[u] true; // 标记为已处理 // 更新u的所有邻接顶点的距离 for (int v 0; v V; v) { // 更新条件1.边存在2.未处理 3.新路径更短 if (!sptSet[v] graph[u][v] ! 0 dist[u] ! Integer.MAX_VALUE dist[u] graph[u][v] dist[v]) { dist[v] dist[u] graph[u][v]; } } } printSolution(dist, V); } public static void main(String[] args) { int V 5; // 顶点数 int graph[][] new int[][] { { 0, 10, 0, 0, 5 }, // 邻接矩阵0表示无边 { 10, 0, 1, 0, 2 }, { 0, 1, 0, 4, 0 }, { 0, 0, 4, 0, 3 }, { 5, 2, 0, 3, 0 } }; DijkstraAlgorithm t new DijkstraAlgorithm(); System.out.println(Dijkstra算法结果源点为顶点0); t.dijkstra(graph, 0, V); } }3. 拓扑排序基于BFS的Kahn算法import java.util.*; class TopologicalSort { private int V; // 顶点数 private LinkedListInteger adj[]; // 邻接表 TopologicalSort(int v) { V v; adj new LinkedList[v]; for (int i 0; i v; i) { adj[i] new LinkedList(); } } // 添加有向边 v - w void addEdge(int v, int w) { adj[v].add(w); } // 拓扑排序主函数 void topologicalSort() { int indegree[] new int[V]; // 存储每个顶点的入度 // 计算所有顶点的入度 for (int i 0; i V; i) { for (int node : adj[i]) { indegree[node]; } } QueueInteger queue new LinkedList(); // 将所有入度为0的顶点加入队列 for (int i 0; i V; i) { if (indegree[i] 0) { queue.add(i); } } int cnt 0; // 记录已输出的顶点数 ListInteger topOrder new ArrayList(); while (!queue.isEmpty()) { int u queue.poll(); topOrder.add(u); // 遍历u的所有邻接点将其入度减1 for (int node : adj[u]) { // 如果入度减为0则加入队列 if (--indegree[node] 0) { queue.add(node); } } cnt; } // 检查是否存在环 if (cnt ! V) { System.out.println(图中存在环无法进行拓扑排序); return; } // 输出拓扑排序结果 System.out.println(拓扑排序结果:); for (int i : topOrder) { System.out.print(i ); } } public static void main(String args[]) { TopologicalSort g new TopologicalSort(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); g.topologicalSort(); // 一种可能输出: 5 4 2 3 1 0 } }参考来源计算机类本科毕业设计论文大纲设计及论文撰写指南Java期末复习题详解Java毕业设计基于VueSpringBoot企业个性化展示平台(代码数据库文档LW运行成功)写作经验分享【29】目标检测硕士论文从开题到答辩的模块化写作指南【持续更新】AI提示词实战指南从核心心法到结构化模板提升大模型协作效率 【数据结构】图的数据结构核心知识点与代码实现
数据结构“图”章节核心知识点与代码实现一、 图的基础知识点知识点核心内容图的定义图G(V, E)由顶点集合 V和边集合 E组成用于表示多对多关系。图的分类1. 有向图 vs 无向图边是否有方向。2. 带权图 vs 无权图边是否有权重。3. 连通图 vs 非连通图任意两顶点间是否有路径。图的存储结构1. 邻接矩阵二维数组适合稠密图查询边快O(1)。2. 邻接表数组链表适合稀疏图节省空间。3. 邻接多重表/十字链表用于优化特定操作。图的遍历算法1. 深度优先搜索 (DFS)递归或栈实现探索图的深度。2. 广度优先搜索 (BFS)队列实现探索图的广度。图的应用算法1. 最短路径Dijkstra单源无负权、Floyd多源。2. 最小生成树Prim加点法、Kruskal加边法。3. 拓扑排序用于有向无环图 (DAG) 的任务排序。4. 关键路径AOE网中决定项目工期的路径。二、 核心代码段Java实现1. 图的邻接表表示与DFS/BFS遍历import java.util.*; // 使用邻接表表示无向图 class Graph { private int V; // 顶点数 private LinkedListInteger adj[]; // 邻接表 // 构造函数 Graph(int v) { V v; adj new LinkedList[v]; for (int i 0; i v; i) { adj[i] new LinkedList(); } } // 添加边无向图 void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); // 有向图则注释此行 } //深度优先搜索 (DFS) 递归实现 void DFSUtil(int v, boolean visited[]) { visited[v] true; // 标记当前节点为已访问 System.out.print(v ); // 递归访问所有未访问的邻接顶点 for (int n : adj[v]) { if (!visited[n]) { DFSUtil(n, visited); } } } void DFS(int v) { boolean visited[] new boolean[V]; DFSUtil(v, visited); } // 广度优先搜索 (BFS) 队列实现 void BFS(int s) { boolean visited[] new boolean[V]; LinkedListInteger queue new LinkedList(); visited[s] true; queue.add(s); while (!queue.isEmpty()) { s queue.poll(); // 从队列头部取出顶点 System.out.print(s ); // 将该顶点的所有未访问邻接点入队 for (int n : adj[s]) { if (!visited[n]) { visited[n] true; queue.add(n); } } } } } public class Main { public static void main(String args[]) { Graph g new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println(从顶点0开始的深度优先遍历:); g.DFS(0); // 输出: 0 1 2 3 System.out.println( 从顶点0开始的广度优先遍历:); g.BFS(0); // 输出: 0 1 2 3 } }2. Dijkstra算法求单源最短路径邻接矩阵无负权import java.util.*; class DijkstraAlgorithm { // 辅助方法找到未处理顶点中距离最小的顶点索引 int minDistance(int dist[], Boolean sptSet[], int V) { int min Integer.MAX_VALUE, minIndex -1; for (int v 0; v V; v) { if (!sptSet[v] dist[v] min) { min dist[v]; minIndex v; } } return minIndex; } // 打印最短路径结果 void printSolution(int dist[], int V) { System.out.println(顶点 \t距源点距离); for (int i 0; i V; i) { System.out.println(i \t\t dist[i]); } } // Dijkstra算法核心实现 void dijkstra(int graph[][], int src, int V) { int dist[] new int[V]; // 存储源点到各点的最短距离 Boolean sptSet[] new Boolean[V]; // 标记顶点是否已处理 // 初始化距离设为无穷大集合设为空 for (int i 0; i V; i) { dist[i] Integer.MAX_VALUE; sptSet[i] false; } dist[src] 0; // 源点到自身的距离为0 // 循环 V-1 次每次确定一个顶点的最短路径 for (int count 0; count V - 1; count) { // 选取未处理顶点中距离最小的顶点u int u minDistance(dist, sptSet, V); sptSet[u] true; // 标记为已处理 // 更新u的所有邻接顶点的距离 for (int v 0; v V; v) { // 更新条件1.边存在2.未处理 3.新路径更短 if (!sptSet[v] graph[u][v] ! 0 dist[u] ! Integer.MAX_VALUE dist[u] graph[u][v] dist[v]) { dist[v] dist[u] graph[u][v]; } } } printSolution(dist, V); } public static void main(String[] args) { int V 5; // 顶点数 int graph[][] new int[][] { { 0, 10, 0, 0, 5 }, // 邻接矩阵0表示无边 { 10, 0, 1, 0, 2 }, { 0, 1, 0, 4, 0 }, { 0, 0, 4, 0, 3 }, { 5, 2, 0, 3, 0 } }; DijkstraAlgorithm t new DijkstraAlgorithm(); System.out.println(Dijkstra算法结果源点为顶点0); t.dijkstra(graph, 0, V); } }3. 拓扑排序基于BFS的Kahn算法import java.util.*; class TopologicalSort { private int V; // 顶点数 private LinkedListInteger adj[]; // 邻接表 TopologicalSort(int v) { V v; adj new LinkedList[v]; for (int i 0; i v; i) { adj[i] new LinkedList(); } } // 添加有向边 v - w void addEdge(int v, int w) { adj[v].add(w); } // 拓扑排序主函数 void topologicalSort() { int indegree[] new int[V]; // 存储每个顶点的入度 // 计算所有顶点的入度 for (int i 0; i V; i) { for (int node : adj[i]) { indegree[node]; } } QueueInteger queue new LinkedList(); // 将所有入度为0的顶点加入队列 for (int i 0; i V; i) { if (indegree[i] 0) { queue.add(i); } } int cnt 0; // 记录已输出的顶点数 ListInteger topOrder new ArrayList(); while (!queue.isEmpty()) { int u queue.poll(); topOrder.add(u); // 遍历u的所有邻接点将其入度减1 for (int node : adj[u]) { // 如果入度减为0则加入队列 if (--indegree[node] 0) { queue.add(node); } } cnt; } // 检查是否存在环 if (cnt ! V) { System.out.println(图中存在环无法进行拓扑排序); return; } // 输出拓扑排序结果 System.out.println(拓扑排序结果:); for (int i : topOrder) { System.out.print(i ); } } public static void main(String args[]) { TopologicalSort g new TopologicalSort(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); g.topologicalSort(); // 一种可能输出: 5 4 2 3 1 0 } }参考来源计算机类本科毕业设计论文大纲设计及论文撰写指南Java期末复习题详解Java毕业设计基于VueSpringBoot企业个性化展示平台(代码数据库文档LW运行成功)写作经验分享【29】目标检测硕士论文从开题到答辩的模块化写作指南【持续更新】AI提示词实战指南从核心心法到结构化模板提升大模型协作效率