c++图解析

1. 引言图Graph是一种重要的非线性数据结构由顶点Vertex和边Edge组成。它用于表示实体之间的关系广泛应用于社交网络、路径规划、推荐系统等领域。2. 基本概念2.1 顶点与边顶点也称为节点是图的基本单位边是连接两个顶点的线。边可以是有方向的有向图或无方向的无向图。2.2 有向图与无向图在有向图中边有方向从起点指向终点。在无向图中边没有方向表示双向关系。2.3 权重边可以带有权重表示连接的成本、距离或强度这样的图称为加权图。3. 图的表示方法3.1 邻接矩阵使用二维数组表示顶点之间的连接关系。对于有 N 个顶点的图创建一个 N×N 的矩阵。如果顶点 i 和 j 之间有边则 matrix[i][j] 1或权重值否则为 0或无穷大。// Java 邻接矩阵示例 public class GraphMatrix { private int[][] matrix; private int numVertices; public GraphMatrix(int n) { numVertices n; matrix new int[n][n]; } public void addEdge(int i, int j, int weight) { matrix[i][j] weight; // 如果是无向图还需设置 matrix[j][i] weight; } }3.2 邻接表为每个顶点维护一个列表存储与其相邻的顶点。这种方式更节省空间尤其适用于稀疏图。// Java 邻接表示例使用 List of Lists import java.util.*; public class GraphList { private ListListint[] adjList; // 每个内层列表存储 [邻居顶点, 权重] public GraphList(int n) { adjList new ArrayList(n); for (int i 0; i n; i) { adjList.add(new ArrayList()); } } public void addEdge(int u, int v, int weight) { adjList.get(u).add(new int[]{v, weight}); // 如果是无向图还需添加 adjList.get(v).add(new int[]{u, weight}); } }4. 图的遍历算法4.1 深度优先搜索DFS沿着一条路径深入探索直到末端再回溯。通常使用递归或栈实现。// Java DFS 示例递归 public void dfs(int node, boolean[] visited, ListListInteger graph) { visited[node] true; System.out.print(node ); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { dfs(neighbor, visited, graph); } } }4.2 广度优先搜索BFS从起点开始逐层向外探索。通常使用队列实现。// Java BFS 示例 import java.util.*; public void bfs(int start, ListListInteger graph) { boolean[] visited new boolean[graph.size()]; QueueInteger queue new LinkedList(); visited[start] true; queue.offer(start); while (!queue.isEmpty()) { int node queue.poll(); System.out.print(node ); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] true; queue.offer(neighbor); } } } }5. 常见图算法5.1 最短路径Dijkstra 算法适用于带非负权重的图求单源最短路径。Floyd-Warshall 算法动态规划思想求所有顶点对之间的最短路径。5.2 最小生成树Prim 算法从任意顶点开始逐步添加权重最小的边直到包含所有顶点。Kruskal 算法按权重从小到大排序边依次添加不构成环的边。5.3 拓扑排序对有向无环图DAG的顶点进行线性排序使得对于每条有向边 (u, v)u 都排在 v 前面。常用于任务调度、依赖解析。6. 应用场景社交网络用户是顶点关注/好友关系是边。地图导航地点是顶点道路是带权重的边。网络拓扑路由器/交换机是顶点连接是边。知识图谱实体是顶点关系是边。编译器控制流图、依赖图。7. 总结图是一种强大而灵活的数据结构能够建模复杂的关系网络。掌握其基本概念、表示方法和核心算法是解决许多实际工程问题的关键。