当前位置：首页 > news >正文

Java图论实战：深入理解有向图与无向图的构建与应用

news 2026/5/2 20:26:19

Java图论实战：深入理解有向图与无向图的构建与应用

图（Graph）是计算机科学中不可或缺的非线性数据结构，广泛应用于社交网络、地图导航、任务调度等领域。本文将以Java语言为核心，深入讲解有向图与无向图的基本概念、Java实现方式及实际应用场景，帮助开发者快速掌握图论基础，为后续学习更复杂的图算法打下坚实基础。

什么是图？从顶点到边

图由两个核心元素构成：顶点（Vertex/Node）和边（Edge）。顶点代表对象，如用户、城市或任务；边则连接两个顶点，表示它们之间的关系。数学上，图通常表示为 G = (V, E)，其中V是顶点集合，E是边集合。

图的分类：根据边的方向性，图可分为无向图和有向图。此外，根据边是否带有权重，又可分为加权图和非加权图。理解这些分类对于选择合适的算法至关重要。

在实际开发中，图的表示方式直接影响性能。例如，在JavaScript、TypeScript或Python中，常用邻接表或邻接矩阵；而在Java中，我们通常利用集合框架（如ArrayList和HashMap）来实现高效的图结构。Go语言则更倾向于使用切片和映射。本文重点聚焦Java实现，但核心思想可迁移至其他语言。

无向图：对称关系的基石

无向图中的边没有方向，表示对称的双向关系。如果顶点A和B之间存在一条边，那么可以从A到达B，也可以从B到达A。这种结构非常适合建模对称的连接。

实际应用场景：

社交网络：微信好友关系（互为好友）
交通网络：城市间的双向道路
协作关系：项目团队成员之间的合作关系
网络拓扑：局域网中设备的连接关系

Java实现无向图通常采用邻接表方式，每个顶点维护一个相邻顶点列表。下面是一个典型实现示例：

import java.util.*;

/*** 无向图的实现（使用邻接表）*/
public class UndirectedGraph {   // 使用HashMap存储图，key为顶点，value为邻接顶点列表   private Map> adjList;      public UndirectedGraph() {       this.adjList = new HashMap<>();   }      /**    * 添加顶点    */   public void addVertex(String vertex) {       adjList.putIfAbsent(vertex, new ArrayList<>());   }      /**    * 添加边（无向边，需要双向添加）    */   public void addEdge(String v1, String v2) {       // 确保两个顶点都存在       addVertex(v1);       addVertex(v2);              // 添加双向边       adjList.get(v1).add(v2);       adjList.get(v2).add(v1);   }      /**    * 移除边    */   public void removeEdge(String v1, String v2) {       List v1Neighbors = adjList.get(v1);       List v2Neighbors = adjList.get(v2);              if (v1Neighbors != null) {           v1Neighbors.remove(v2);       }       if (v2Neighbors != null) {           v2Neighbors.remove(v1);       }   }      /**    * 移除顶点    */   public void removeVertex(String vertex) {       // 移除所有与该顶点相连的边       List neighbors = adjList.get(vertex);       if (neighbors != null) {           for (String neighbor : new ArrayList<>(neighbors)) {               removeEdge(vertex, neighbor);           }       }       // 移除顶点       adjList.remove(vertex);   }      /**    * 获取顶点的度（连接的边的数量）    */   public int getDegree(String vertex) {       List neighbors = adjList.get(vertex);       return neighbors != null ? neighbors.size() : 0;   }      /**    * 获取邻接顶点    */   public List getNeighbors(String vertex) {       return adjList.getOrDefault(vertex, new ArrayList<>());   }      /**    * 深度优先搜索（DFS）    */   public void dfs(String start) {       Set visited = new HashSet<>();       dfsHelper(start, visited);   }      private void dfsHelper(String vertex, Set visited) {       visited.add(vertex);       System.out.print(vertex + " ");              for (String neighbor : getNeighbors(vertex)) {           if (!visited.contains(neighbor)) {               dfsHelper(neighbor, visited);           }       }   }      /**    * 广度优先搜索（BFS）    */   public void bfs(String start) {       Set visited = new HashSet<>();       Queue queue = new LinkedList<>();              visited.add(start);       queue.offer(start);              while (!queue.isEmpty()) {           String vertex = queue.poll();           System.out.print(vertex + " ");                      for (String neighbor : getNeighbors(vertex)) {               if (!visited.contains(neighbor)) {                   visited.add(neighbor);                   queue.offer(neighbor);               }           }       }   }      /**    * 打印图结构    */   public void display() {       System.out.println("无向图结构：");       for (Map.Entry> entry : adjList.entrySet()) {           System.out.println(entry.getKey() + " -> " + entry.getValue());       }   }
}

使用示例：

public class UndirectedGraphDemo {   public static void main(String[] args) {       UndirectedGraph graph = new UndirectedGraph();              // 构建社交网络       graph.addEdge("Alice", "Bob");       graph.addEdge("Alice", "Charlie");       graph.addEdge("Bob", "David");       graph.addEdge("Charlie", "David");       graph.addEdge("David", "Eve");              // 显示图结构       graph.display();              System.out.println("\n各顶点的度：");       System.out.println("Alice的度: " + graph.getDegree("Alice"));       System.out.println("David的度: " + graph.getDegree("David"));              System.out.println("\n深度优先搜索（从Alice开始）：");       graph.dfs("Alice");              System.out.println("\n\n广度优先搜索（从Alice开始）：");       graph.bfs("Alice");   }
}

⚠️ 注意事项：在无向图中添加边时，务必双向记录，否则会导致图结构不对称，影响后续遍历和算法结果。

有向图：单向关系的利器

有向图中的边具有明确的方向性，从一个顶点指向另一个顶点。边 <A, B> 表示从A到B的单向关系，但不代表可以从B回到A。这种结构适合建模非对称的依赖或流向。

实际应用场景：

微博关注：用户A关注用户B，但B不一定关注A
网页链接：网页间的超链接关系
任务依赖：项目中任务的先后顺序
交通系统：单行道网络
课程prerequisite：课程的先修关系

Java实现有向图同样可以使用邻接表，但边只记录单向关系。示例代码如下：

import java.util.*;

/*** 有向图的实现（使用邻接表）*/
public class DirectedGraph {   private Map> adjList;      public DirectedGraph() {       this.adjList = new HashMap<>();   }      /**    * 添加顶点    */   public void addVertex(String vertex) {       adjList.putIfAbsent(vertex, new ArrayList<>());   }      /**    * 添加有向边（从v1指向v2）    */   public void addEdge(String from, String to) {       addVertex(from);       addVertex(to);              // 只添加单向边       adjList.get(from).add(to);   }      /**    * 移除边    */   public void removeEdge(String from, String to) {       List neighbors = adjList.get(from);       if (neighbors != null) {           neighbors.remove(to);       }   }      /**    * 移除顶点    */   public void removeVertex(String vertex) {       // 移除从该顶点出发的所有边       adjList.remove(vertex);              // 移除指向该顶点的所有边       for (List neighbors : adjList.values()) {           neighbors.remove(vertex);       }   }      /**    * 获取出度（从该顶点出发的边数）    */   public int getOutDegree(String vertex) {       List neighbors = adjList.get(vertex);       return neighbors != null ? neighbors.size() : 0;   }      /**    * 获取入度（指向该顶点的边数）    */   public int getInDegree(String vertex) {       int count = 0;       for (List neighbors : adjList.values()) {           if (neighbors.contains(vertex)) {               count++;           }       }       return count;   }      /**    * 获取邻接顶点（出边指向的顶点）    */   public List getNeighbors(String vertex) {       return adjList.getOrDefault(vertex, new ArrayList<>());   }      /**    * 拓扑排序（Kahn算法）    * 适用于有向无环图（DAG）    */   public List topologicalSort() {       List result = new ArrayList<>();       Map inDegree = new HashMap<>();       Queue queue = new LinkedList<>();              // 计算所有顶点的入度       for (String vertex : adjList.keySet()) {           inDegree.put(vertex, getInDegree(vertex));       }              // 将入度为0的顶点加入队列       for (Map.Entry entry : inDegree.entrySet()) {           if (entry.getValue() == 0) {               queue.offer(entry.getKey());           }       }              // BFS处理       while (!queue.isEmpty()) {           String vertex = queue.poll();           result.add(vertex);                      // 减少邻接顶点的入度           for (String neighbor : getNeighbors(vertex)) {               inDegree.put(neighbor, inDegree.get(neighbor) - 1);               if (inDegree.get(neighbor) == 0) {                   queue.offer(neighbor);               }           }       }              // 如果结果包含所有顶点，说明没有环       if (result.size() != adjList.size()) {           System.out.println("图中存在环，无法进行拓扑排序！");           return new ArrayList<>();       }              return result;   }      /**    * 检测是否存在环（使用DFS）    */   public boolean hasCycle() {       Set visited = new HashSet<>();       Set recStack = new HashSet<>();              for (String vertex : adjList.keySet()) {           if (hasCycleHelper(vertex, visited, recStack)) {               return true;           }       }       return false;   }      private boolean hasCycleHelper(String vertex, Set visited,                                   Set recStack) {       if (recStack.contains(vertex)) {           return true; // 发现环       }       if (visited.contains(vertex)) {           return false;       }              visited.add(vertex);       recStack.add(vertex);              for (String neighbor : getNeighbors(vertex)) {           if (hasCycleHelper(neighbor, visited, recStack)) {               return true;           }       }              recStack.remove(vertex);       return false;   }      /**    * 深度优先搜索    */   public void dfs(String start) {       Set visited = new HashSet<>();       dfsHelper(start, visited);   }      private void dfsHelper(String vertex, Set visited) {       visited.add(vertex);       System.out.print(vertex + " ");              for (String neighbor : getNeighbors(vertex)) {           if (!visited.contains(neighbor)) {               dfsHelper(neighbor, visited);           }       }   }      /**    * 打印图结构    */   public void display() {       System.out.println("有向图结构：");       for (Map.Entry> entry : adjList.entrySet()) {           System.out.println(entry.getKey() + " -> " + entry.getValue());       }   }
}

使用示例：

public class DirectedGraphDemo {   public static void main(String[] args) {       DirectedGraph graph = new DirectedGraph();              // 构建课程依赖关系图       graph.addEdge("数据结构", "算法");       graph.addEdge("离散数学", "数据结构");       graph.addEdge("离散数学", "算法");       graph.addEdge("程序设计", "数据结构");       graph.addEdge("算法", "人工智能");       graph.addEdge("数据结构", "数据库");              // 显示图结构       graph.display();              System.out.println("\n各顶点的入度和出度：");       System.out.println("数据结构 - 入度: " + graph.getInDegree("数据结构") +                         ", 出度: " + graph.getOutDegree("数据结构"));       System.out.println("算法 - 入度: " + graph.getInDegree("算法") +                         ", 出度: " + graph.getOutDegree("算法"));              System.out.println("\n检测环：");       System.out.println("是否存在环: " + graph.hasCycle());              System.out.println("\n拓扑排序（课程学习顺序）：");       List order = graph.topologicalSort();       System.out.println(order);              System.out.println("\n深度优先搜索（从离散数学开始）：");       graph.dfs("离散数学");   }
}

关键点：有向图中，判断两个顶点是否连通需要区分方向，这也是拓扑排序、强连通分量等高级算法的基础。在Python或JavaScript中，类似实现通常使用字典或Map结构。

邻接矩阵：稠密图的另一种选择

除了邻接表，图还可以用邻接矩阵表示，特别适合边数较多的稠密图。邻接矩阵是一个二维数组，matrix[i][j]表示顶点i到顶点j的边是否存在（或权重）。

Java实现示例：

/*** 使用邻接矩阵实现的图（支持有向图和无向图）*/
public class GraphMatrix {   private int[][] matrix;   private Map vertexIndex;   private Map indexVertex;   private int vertexCount;   private boolean isDirected;      public GraphMatrix(int maxVertices, boolean isDirected) {       this.matrix = new int[maxVertices][maxVertices];       this.vertexIndex = new HashMap<>();       this.indexVertex = new HashMap<>();       this.vertexCount = 0;       this.isDirected = isDirected;   }      /**    * 添加顶点    */   public void addVertex(String vertex) {       if (!vertexIndex.containsKey(vertex)) {           vertexIndex.put(vertex, vertexCount);           indexVertex.put(vertexCount, vertex);           vertexCount++;       }   }      /**    * 添加边    */   public void addEdge(String v1, String v2) {       addVertex(v1);       addVertex(v2);              int index1 = vertexIndex.get(v1);       int index2 = vertexIndex.get(v2);              matrix[index1][index2] = 1;              // 如果是无向图，需要添加反向边       if (!isDirected) {           matrix[index2][index1] = 1;       }   }      /**    * 检查是否存在边    */   public boolean hasEdge(String v1, String v2) {       Integer index1 = vertexIndex.get(v1);       Integer index2 = vertexIndex.get(v2);              if (index1 == null || index2 == null) {           return false;       }              return matrix[index1][index2] == 1;   }      /**    * 打印邻接矩阵    */   public void display() {       System.out.println("邻接矩阵：");       System.out.print("    ");       for (int i = 0; i < vertexCount; i++) {           System.out.printf("%-8s", indexVertex.get(i));       }       System.out.println();              for (int i = 0; i < vertexCount; i++) {           System.out.printf("%-4s", indexVertex.get(i));           for (int j = 0; j < vertexCount; j++) {               System.out.printf("%-8d", matrix[i][j]);           }           System.out.println();       }   }
}

邻接表 vs 邻接矩阵：

邻接表：空间复杂度O(V + E)，适合稀疏图（边少），遍历邻接点快，但判断两点是否相邻较慢。
邻接矩阵：空间复杂度O(V²)，适合稠密图（边多），判断两点是否相邻只需O(1)，但会浪费空间存储不存在的边。

选择建议：如果图规模较小或边非常密集，优先使用邻接矩阵；否则，邻接表更灵活高效。在Go或Java中，还可以结合位图进行内存优化。

[AFFILIATE_SLOT_1]

有向图 vs 无向图：对比总结

特性	无向图	有向图
边的表示	(v1, v2) 无序对	<v1, v2> 有序对
方向性	双向，对称关系	单向，非对称关系
度的概念	度（Degree）	入度和出度
最大边数	n(n-1)/2	n(n-1)
存储开销	邻接矩阵对称	邻接矩阵不对称
特有算法	最小生成树	拓扑排序、强连通分量