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内部通常还是会用字节来存储，所以实际节省可能没有理论上那么大。

访问效率上，邻接矩阵的优势非常明显。要检查任意两个顶点u和v之间是否存在边，你只需要直接访问adjMatrix[u][v]。这是一个O(1)的操作，非常快，这在需要频繁查询特定边是否存在时显得尤为高效。相比之下，如果用邻接表，可能需要遍历一个列表才能找到。

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

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

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

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

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

1. 整数索引与实际对象/名称的映射： 最常见的方法是使用HashMap来将实际的顶点名称（如城市名“北京”）映射到一个唯一的整数ID（如0），同时使用一个ArrayList或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 vertexNameToId; // 名字到ID的映射
       private List 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 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来存储所有顶点对象，同时仍然使用HashMap（或HashMap，但通常用字符串或某个唯一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> 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)边查询的场景，邻接表往往是更平衡的选择。当然，如果图的顶点数量很小，比如几十个或几百个，那邻接矩阵的简洁性也很有吸引力，内存消耗也不至于成为问题。选择哪种表示方法，真的是要根据具体的应用场景和图的特性来权衡。