【数据结构】图的数据结构核心知识点与代码实现-育师

数据结构“图”章节核心知识点与代码实现

一、图的基础知识点

知识点	核心内容
图的定义	图`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 LinkedList<Integer> 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]; LinkedList<Integer> 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 LinkedList<Integer> 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]++; } } Queue<Integer> queue = new LinkedList<>(); // 将所有入度为0的顶点加入队列 for (int i = 0; i < V; i++) { if (indegree[i] == 0) { queue.add(i); } } int cnt = 0; // 记录已输出的顶点数 List<Integer> 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 } }