java代码如何实现图结构及邻接矩阵表示 java代码图结构的基础编写技巧​

答案：Java中图结构可用邻接矩阵（int[][]）表示，适合稠密图，访问边为O(1)，空间复杂度O(V²)；也可用邻接表（List）表示，适合稀疏图，空间O(V+E)，遍历邻居更高效。

在Java里实现图结构，尤其是用邻接矩阵来表示，核心思路就是利用一个二维数组。这个数组的每个元素

matrix[i][j]

用来表示节点

i

和节点

j

之间是否存在边，或者边的权重。这是一种直观且直接的方法，尤其对于边相对较多的“稠密图”来说，效率很高。基础的编写技巧围绕着如何初始化这个矩阵、添加/删除边以及遍历图展开。

解决方案

实现一个简单的

Graph

类，用

int[][]

作为邻接矩阵。

import java.util.Arrays;  public class GraphAdjacencyMatrix {     private int numVertices; // 顶点的数量     private int[][] adjMatrix; // 邻接矩阵      // 构造函数，初始化图     public GraphAdjacencyMatrix(int numVertices) {         this.numVertices = numVertices;         adjMatrix = new int[numVertices][numVertices];         // 默认所有元素都为0，表示没有边。如果是有向图，可以根据需求初始化。         // 对于无向图，adjMatrix[i][j] == adjMatrix[j][i]     }      // 添加边的方法     // 对于无向图，需要设置 (u, v) 和 (v, u)     public void addEdge(int u, int v) {         if (u >= 0 && u < numVertices && v >= 0 && v < numVertices) {             adjMatrix[u][v] = 1; // 表示有边             adjMatrix[v][u] = 1; // 无向图             // 如果是带权图，这里可以设置为权重值             // adjMatrix[u][v] = weight;             // adjMatrix[v][u] = weight;         } else {             System.out.println("无效的顶点索引。");         }     }      // 删除边的方法     public void removeEdge(int u, int v) {         if (u >= 0 && u < numVertices && v >= 0 && v < numVertices) {             adjMatrix[u][v] = 0; // 移除边             adjMatrix[v][u] = 0; // 无向图         } else {             System.out.println("无效的顶点索引。");         }     }      // 检查两个顶点之间是否有边     public boolean hasEdge(int u, int v) {         if (u >= 0 && u < numVertices && v >= 0 && v < numVertices) {             return adjMatrix[u][v] == 1; // 或 > 0 如果是带权图         }         return false;     }      // 打印邻接矩阵     public void printGraph() {         System.out.println("图的邻接矩阵表示:");         for (int i = 0; i < numVertices; i++) {             for (int j = 0; j < numVertices; j++) {                 System.out.print(adjMatrix[i][j] + " ");             }             System.out.println();         }     }      // 获取某个顶点的邻居     public void getNeighbors(int vertex) {         if (vertex < 0 || vertex >= numVertices) {             System.out.println("无效的顶点索引。");             return;         }         System.out.print("顶点 " + vertex + " 的邻居: ");         for (int i = 0; i < numVertices; i++) {             if (adjMatrix[vertex][i] == 1) {                 System.out.print(i + " ");             }         }         System.out.println();     }      public static void main(String[] args) {         GraphAdjacencyMatrix graph = new GraphAdjacencyMatrix(5); // 创建一个有5个顶点的图          // 添加一些边         graph.addEdge(0, 1);         graph.addEdge(0, 4);         graph.addEdge(1, 2);         graph.addEdge(1, 3);         graph.addEdge(1, 4);         graph.addEdge(2, 3);         graph.addEdge(3, 4);          graph.printGraph();          System.out.println("顶点 0 和 1 之间有边吗? " + graph.hasEdge(0, 1)); // true         System.out.println("顶点 0 和 2 之间有边吗? " + graph.hasEdge(0, 2)); // false          graph.getNeighbors(1); // 顶点 1 的邻居: 0 2 3 4         graph.removeEdge(1, 4);         graph.getNeighbors(1); // 顶点 1 的邻居: 0 2 3     } }

邻接矩阵在Java中如何高效存储和访问？

在Java中，邻接矩阵通常用

int[][]

或

boolean[][]

来表示。高效存储和访问主要体现在它的固有特性上。

首先，

int[][]

是最常见的选择，因为它可以轻松扩展以存储边的权重（比如距离、成本等），而不仅仅是“有边/无边”的布尔信息。如果只是表示是否存在边，

boolean[][]

会更节省内存，每个元素只需要一个位。但Java的

boolean[]

数组在JVM内部通常还是会用字节来存储，所以实际节省可能没有理论上那么大。

立即学习“Java免费学习笔记（深入）”；

访问效率上，邻接矩阵的优势非常明显。要检查任意两个顶点

u

和

v

之间是否存在边，你只需要直接访问

adjMatrix[u][v]

。这是一个O(1)的操作，非常快，这在需要频繁查询特定边是否存在时显得尤为高效。相比之下，如果用邻接表，可能需要遍历一个列表才能找到。

存储方面，邻接矩阵的空间复杂度是O(V²)，其中V是顶点的数量。这意味着，无论图有多少条边，只要顶点数量固定，所需的内存空间就是固定的。这对于顶点数量不多但边很多（即“稠密图”）的场景非常有利。比如，一个完全图（所有顶点之间都有边）用邻接矩阵表示就非常高效。但如果图是“稀疏图”，即顶点很多但边很少，那么大量的矩阵单元会是空的（值为0），这就造成了存储空间的浪费。一个1000个顶点的图，邻接矩阵就需要1000×1000个单元格，即100万个整数（或布尔值），这可能占用几MB的内存。对于更大规模的图，比如百万级顶点，邻接矩阵就不太现实了，因为它会需要TB级别的内存。

所以，选择

int[][]

还是

boolean[][]

，以及是否使用邻接矩阵本身，都取决于你的图的特性：是稠密还是稀疏，边是否带权，以及对内存和访问速度的具体要求。

Java图结构中如何处理节点（顶点）的表示和映射？

在Java中处理图的节点（顶点），最基础且常用的方法就是使用整数作为顶点的唯一标识符。就像上面代码里那样，顶点0、顶点1、顶点2…这样。这种方式的好处是直接、简单，可以直接作为数组的索引来访问邻接矩阵。

然而，在实际应用中，顶点往往代表着更复杂的实体，比如城市、用户、网页、文件等等。这些实体通常有自己的名称、属性。直接用整数0、1、2来表示它们，显然不够直观，也不方便操作。这时，就需要一个映射机制：

1. 整数索引与实际对象/名称的映射： 最常见的方法是使用

   HashMap<String, Integer>

   来将实际的顶点名称（如城市名“北京”）映射到一个唯一的整数ID（如0），同时使用一个

   ArrayList<String>

   或

   String[]

   来根据整数ID反向查找名称。

   import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;  public class GraphWithNamedVertices {     private int numVertices;     private int[][] adjMatrix;     private Map<String, Integer> vertexNameToId; // 名字到ID的映射     private List<String> vertexIdToName;       // ID到名字的映射      public GraphWithNamedVertices(int maxVertices) {         this.numVertices = 0; // 初始顶点数为0         this.adjMatrix = new int[maxVertices][maxVertices]; // 预设最大容量         this.vertexNameToId = new HashMap<>();         this.vertexIdToName = new ArrayList<>();     }      // 添加一个新顶点     public int addVertex(String name) {         if (vertexNameToId.containsKey(name)) {             return vertexNameToId.get(name); // 顶点已存在，返回其ID         }         int id = numVertices++;         vertexNameToId.put(name, id);         vertexIdToName.add(name); // 保持顺序与ID一致         return id;     }      // 添加边 (使用名称)     public void addEdge(String name1, String name2) {         int u = addVertex(name1); // 确保顶点存在并获取ID         int v = addVertex(name2);         adjMatrix[u][v] = 1;         adjMatrix[v][u] = 1; // 无向图     }      // 获取顶点名称     public String getVertexName(int id) {         if (id >= 0 && id < vertexIdToName.size()) {             return vertexIdToName.get(id);         }         return null;     }      // ... 其他操作，如hasEdge(String name1, String name2) }

   这种方式在处理实际业务逻辑时非常方便，你可以直接用“上海”和“北京”来添加边，而底层仍然是高效的整数索引操作。

2. 创建

   Vertex

   类： 对于更复杂的场景，如果每个顶点除了名称还有很多其他属性（例如：一个用户顶点可能有年龄、性别、注册时间等），那么可以创建一个

   Vertex

   类来封装这些属性。

   public class Vertex {     private int id;     private String name;     private Map<String, Object> properties; // 存储额外属性      public Vertex(int id, String name) {         this.id = id;         this.name = name;         this.properties = new HashMap<>();     }      // Getter/Setter for id, name, properties     public void addProperty(String key, Object value) {         this.properties.put(key, value);     }     // ... }

   在这种情况下，你的图结构可能需要维护一个

   List<Vertex>

   来存储所有顶点对象，同时仍然使用

   HashMap<String, Integer>

   （或

   HashMap<Vertex, Integer>

   ，但通常用字符串或某个唯一ID作为键更方便）来将

   Vertex

   对象或其唯一标识映射到邻接矩阵的整数索引。这使得图的表示既能处理复杂数据，又能保持底层数组操作的效率。

除了邻接矩阵，Java中还有哪些常见的图表示方法及其优劣？

除了邻接矩阵，Java中另一种非常常见且重要的图表示方法是邻接表（Adjacency List）。这两种方法各有优劣，适用于不同的场景。

邻接表（Adjacency List）

邻接表通常用一个数组或

ArrayList

来表示，其中每个元素又是一个链表（

LinkedList

）或另一个

ArrayList

，存储与该顶点直接相连的所有邻居顶点。

例如，

adjList[i]

会存储一个列表，里面包含了所有与顶点

i

有边的顶点。

import java.util.ArrayList; import java.util.LinkedList; import java.util.List;  public class GraphAdjacencyList {     private int numVertices;     private List<List<Integer>> adjList; // 邻接表      public GraphAdjacencyList(int numVertices) {         this.numVertices = numVertices;         adjList = new ArrayList<>(numVertices);         for (int i = 0; i < numVertices; i++) {             adjList.add(new LinkedList<>()); // 或者 new ArrayList<>()         }     }      // 添加边     public void addEdge(int u, int v) {         if (u >= 0 && u < numVertices && v >= 0 && v < numVertices) {             adjList.get(u).add(v);             adjList.get(v).add(u); // 无向图         }     }      // 打印邻接表     public void printGraph() {         System.out.println("图的邻接表表示:");         for (int i = 0; i < numVertices; i++) {             System.out.print("顶点 " + i + ": ");             for (Integer neighbor : adjList.get(i)) {                 System.out.print(neighbor + " ");             }             System.out.println();         }     }     // ... 其他方法如hasEdge, getNeighbors等 }

邻接矩阵 vs. 邻接表：优劣比较

1. 空间复杂度：

   • 邻接矩阵： O(V²)。不管图有多少条边，空间都是固定的，V是顶点数。对于稀疏图（边很少），会有大量空间浪费。
   • 邻接表： O(V + E)，V是顶点数，E是边数。每个顶点存储一个列表头，每条边存储两次（无向图），所以空间效率更高，尤其是在稀疏图上，可以节省大量内存。

2. 时间复杂度：

   • 检查两点间是否有边（

     hasEdge(u, v)

     ）：

     • 邻接矩阵： O(1)。直接访问

       adjMatrix[u][v]

       。

     • 邻接表： O(deg(u))，其中

       deg(u)

       是顶点

       u

       的度（邻居数量）。需要遍历

       u

       的邻居列表。最坏情况下，如果

       u

       连接所有其他顶点，则为O(V)。

   • 查找一个顶点的所有邻居（

     getNeighbors(u)

     ）：

     • 邻接矩阵： O(V)。需要遍历

       adjMatrix[u]

       的整行。

     • 邻接表： O(deg(u))。直接遍历

       adjList.get(u)

       。这通常比邻接矩阵快，特别是对于稀疏图。

   • 添加/删除边：
     • 邻接矩阵： O(1)。直接修改矩阵单元。
     • 邻接表： O(1)（添加）或O(deg(u))（删除，如果需要查找并移除特定边）。

3. 适用场景：

   • 邻接矩阵： 适用于稠密图（边数接近V²），或者需要频繁进行快速的“是否存在边”查询的场景。它的实现相对简单，代码结构直观。
   • 邻接表： 适用于稀疏图（边数远小于V²），或者需要频繁遍历一个顶点的所有邻居的场景（例如图的深度优先搜索DFS或广度优先搜索BFS）。它在空间效率上通常更优。

我的看法是，在实际开发中，邻接表的使用频率要高于邻接矩阵。 毕竟，大多数真实世界的图，比如社交网络、网页链接图，都是非常稀疏的。如果不是在算法竞赛或特定需要O(1)边查询的场景，邻接表往往是更平衡的选择。当然，如果图的顶点数量很小，比如几十个或几百个，那邻接矩阵的简洁性也很有吸引力，内存消耗也不至于成为问题。选择哪种表示方法，真的是要根据具体的应用场景和图的特性来权衡。