java代码如何实现图结构及邻接矩阵表示 java代码图结构的基础编写技巧-java教程-PHP中文网

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

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

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

matrix[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免费学习笔记（深入）”；

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

登录后复制

和

登录后复制

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

adjMatrix[u][v]

登录后复制

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

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

所以，选择

int[][]

登录后复制

还是

boolean[][]

登录后复制

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

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

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

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

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

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)
}

登录后复制

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

代码小浣熊

代码小浣熊是基于商汤大语言模型的软件智能研发助手，覆盖软件需求分析、架构设计、代码编写、软件测试等环节

查看详情

创建
```
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]

登录后复制

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

登录后复制

有边的顶点。

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. 邻接表：优劣比较

空间复杂度：
- 邻接矩阵： O(V²)。不管图有多少条边，空间都是固定的，V是顶点数。对于稀疏图（边很少），会有大量空间浪费。
- 邻接表： O(V + E)，V是顶点数，E是边数。每个顶点存储一个列表头，每条边存储两次（无向图），所以空间效率更高，尤其是在稀疏图上，可以节省大量内存。
时间复杂度：
- 检查两点间是否有边（
  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))（删除，如果需要查找并移除特定边）。
适用场景：
- 邻接矩阵： 适用于稠密图（边数接近V²），或者需要频繁进行快速的“是否存在边”查询的场景。它的实现相对简单，代码结构直观。
- 邻接表： 适用于稀疏图（边数远小于V²），或者需要频繁遍历一个顶点的所有邻居的场景（例如图的深度优先搜索DFS或广度优先搜索BFS）。它在空间效率上通常更优。

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

以上就是java代码如何实现图结构及邻接矩阵表示 java代码图结构的基础编写技巧的详细内容，更多请关注php中文网其它相关文章！