java如何存储图数据结构

Java如何存储图数据结构

在计算机科学中，图（Graph）是由节点（Node）和边（Edge）组成的一种数据结构。节点表示图中的实体，边表示节点之间的关系。图常用于表示现实世界中的各种问题，如社交网络、路网、组织结构等。在Java中，我们可以使用不同的数据结构来存储图，包括邻接矩阵、邻接表和关联矩阵等。

邻接矩阵

邻接矩阵是一种二维数组，用于表示节点之间的连接关系。对于有N个节点的图，邻接矩阵的大小为N×N。如果节点i和节点j之间存在边，则邻接矩阵的第i行第j列元素为1；否则为0。邻接矩阵的存储效率较低，但它可以快速判断两个节点之间是否有边。

下面是使用邻接矩阵存储图的示例代码：

public class AdjacencyMatrixGraph {
    private int[][] adjacencyMatrix;
    private int numNodes;

    public AdjacencyMatrixGraph(int numNodes) {
        this.numNodes = numNodes;
        this.adjacencyMatrix = new int[numNodes][numNodes];
    }

    public void addEdge(int i, int j) {
        adjacencyMatrix[i][j] = 1;
        adjacencyMatrix[j][i] = 1;
    }

    public void removeEdge(int i, int j) {
        adjacencyMatrix[i][j] = 0;
        adjacencyMatrix[j][i] = 0;
    }

    public boolean hasEdge(int i, int j) {
        return adjacencyMatrix[i][j] == 1;
    }
}

邻接表

邻接表是一种链表数组，用于表示节点之间的连接关系。对于有N个节点的图，邻接表的大小为N。每个节点对应一个链表，链表中存储与该节点相邻的节点。邻接表的存储效率较高，但判断两个节点之间是否有边的效率较低。

下面是使用邻接表存储图的示例代码：

import java.util.ArrayList;
import java.util.List;

public class AdjacencyListGraph {
    private List<List<Integer>> adjacencyList;
    private int numNodes;

    public AdjacencyListGraph(int numNodes) {
        this.numNodes = numNodes;
        this.adjacencyList = new ArrayList<>(numNodes);
        for (int i = 0; i < numNodes; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public void addEdge(int i, int j) {
        adjacencyList.get(i).add(j);
        adjacencyList.get(j).add(i);
    }

    public void removeEdge(int i, int j) {
        adjacencyList.get(i).remove(Integer.valueOf(j));
        adjacencyList.get(j).remove(Integer.valueOf(i));
    }

    public boolean hasEdge(int i, int j) {
        return adjacencyList.get(i).contains(j);
    }
}

关联矩阵

关联矩阵是一种二维数组，用于表示节点和边之间的关系。对于有N个节点和M条边的图，关联矩阵的大小为N×M。如果节点i和边j之间有关联，则关联矩阵的第i行第j列元素为1；否则为0。关联矩阵可以用于表示带权重的图。

下面是使用关联矩阵存储图的示例代码：

public class IncidenceMatrixGraph {
    private int[][] incidenceMatrix;
    private int numNodes;
    private int numEdges;

    public IncidenceMatrixGraph(int numNodes, int numEdges) {
        this.numNodes = numNodes;
        this.numEdges = numEdges;
        this.incidenceMatrix = new int[numNodes][numEdges];
    }

    public void addEdge(int i, int j) {
        incidenceMatrix[i][j] = 1;
        incidenceMatrix[j][i] = 1;
    }

    public void removeEdge(int i, int j) {
        incidenceMatrix[i][j] = 0;
        incidenceMatrix[j][i] = 0;
    }

    public boolean hasEdge(int i, int j) {
        for (int k = 0; k < numEdges; k++) {
            if (incidenceMatrix[i][k] == 1 &&

【文章原创作者：cc防御 http://www.558idc.com/gfip.html提供，感恩】