1. 图算法基础与核心概念图算法是计算机科学中处理图结构数据的重要工具。图由顶点节点和边连接组成这种结构能完美模拟现实世界中的各种关系网络。我第一次接触图算法是在开发社交网络好友推荐系统时当时就被它强大的表达能力所震撼。图的两种主要存储方式各有特点。邻接矩阵用二维数组表示顶点间的连接关系适合稠密图。比如用Java实现时可以这样定义class Graph { private int[][] matrix; private int vertexCount; public Graph(int size) { matrix new int[size][size]; vertexCount size; } public void addEdge(int v1, int v2, int weight) { matrix[v1][v2] weight; matrix[v2][v1] weight; // 无向图需要双向设置 } }邻接表则更适合稀疏图它用链表存储每个顶点的邻居。Python中可以这样实现class Graph: def __init__(self, vertices): self.adj {v: [] for v in range(vertices)} def add_edge(self, u, v, weight): self.adj[u].append((v, weight)) self.adj[v].append((u, weight)) # 无向图实际项目中我遇到过内存不足的问题。当处理百万级顶点时邻接矩阵会消耗TB级内存这时必须改用邻接表。有次优化地图导航系统改用邻接表后内存使用从32GB降到了800MB。2. 图的遍历DFS与BFS实战深度优先搜索DFS和广度优先搜索BFS是图算法的两大基础。去年开发知识图谱系统时我深刻体会到了它们的区别。DFS像走迷宫时右手扶墙的策略会一直深入直到碰壁。它的非递归实现需要栈def dfs(graph, start): visited set() stack [start] while stack: vertex stack.pop() if vertex not in visited: visited.add(vertex) for neighbor in graph[vertex]: stack.append(neighbor) return visitedBFS则像水波扩散一层层推进。我们在社交网络的好友推荐中就用了BFSvoid bfs(MapInteger, ListInteger graph, int start) { QueueInteger queue new LinkedList(); SetInteger visited new HashSet(); queue.offer(start); while (!queue.isEmpty()) { int node queue.poll(); for (int neighbor : graph.get(node)) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.offer(neighbor); } } } }实际使用时要注意DFS可能陷入深层分支导致栈溢出我曾因此不得不改用迭代加深搜索BFS则可能消耗大量内存在处理大规模图时需要谨慎。3. 最短路径算法深度解析Dijkstra算法是我在物流路径规划中最常用的工具。它的核心思想是贪心策略每次选择当前最短路径的节点进行扩展。看这个Java实现void dijkstra(int[][] graph, int src) { int[] dist new int[V]; boolean[] visited new boolean[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] 0; for (int count 0; count V-1; count) { int u minDistance(dist, visited); visited[u] true; for (int v 0; v V; v) { if (!visited[v] graph[u][v] ! 0 dist[u] ! Integer.MAX_VALUE dist[u] graph[u][v] dist[v]) { dist[v] dist[u] graph[u][v]; } } } }但Dijkstra不能处理负权边。有次我遇到运费补贴场景相当于负权边不得不改用Bellman-Ford算法。而Floyd算法则是全源最短路径的利器它的动态规划思想很巧妙def floyd(graph): n len(graph) dist [[graph[i][j] for j in range(n)] for i in range(n)] for k in range(n): for i in range(n): for j in range(n): if dist[i][j] dist[i][k] dist[k][j]: dist[i][j] dist[i][k] dist[k][j] return dist在实时导航系统中我结合了A*算法和Dijkstra利用启发式函数将查询速度提升了5倍。4. 最小生成树的工程实践Prim和Kruskal是构建最小生成树的两种经典算法。去年设计园区光纤网络时我对比了它们的表现。Prim算法类似Dijkstra适合稠密图。这是它的核心实现def prim(graph): n len(graph) parent [-1] * n key [float(inf)] * n key[0] 0 mst_set [False] * n for _ in range(n): u min_key(key, mst_set) mst_set[u] True for v in range(n): if graph[u][v] 0 and not mst_set[v] and graph[u][v] key[v]: key[v] graph[u][v] parent[v] u return parentKruskal算法则基于并查集适合稀疏图。我在处理大型社交网络社区发现时选择了它class Kruskal { class Edge implements ComparableEdge { int src, dest, weight; public int compareTo(Edge e) { return this.weight - e.weight; } } void kruskalMST() { Edge[] result new Edge[V]; Arrays.sort(edges); int[] parent new int[V]; Arrays.fill(parent, -1); int e 0, i 0; while (e V-1 i edges.length) { Edge next edges[i]; int x find(parent, next.src); int y find(parent, next.dest); if (x ! y) { result[e] next; union(parent, x, y); } } } }实际项目中当边数接近V²时Prim更快当边数远小于V²时Kruskal更优。我曾通过预处理将10万节点的运行时间从小时级降到分钟级。