Java数据结构—图（Graph）_java graph

图（Graph）是由节点（Vertex）和边（Edge）构成的一种数据结构。节点表示图中的元素，边表示节点之间的关系。图可以用于描述许多现实世界中的问题，例如社交网络、路线规划等。

在Java中，可以使用邻接矩阵和邻接表两种方式来创建和表示图。邻接矩阵是一个二维数组，其中每个元素表示两个节点之间是否有边。邻接表则是一个链表数组，其中每个链表表示一个节点连接的其他节点。

下面是使用邻接矩阵创建一个简单的无向图的Java代码示例：

public class Graph {
    private final int numVertices;
    private final boolean[][] adjMatrix;
 
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new boolean[numVertices][numVertices];
    }
 
    public void addEdge(int i, int j) {
        adjMatrix[i][j] = true;
        adjMatrix[j][i] = true;
    }
}

这里我们定义了一个`Graph`类，其中`numVertices`表示节点数，`adjMatrix`表示邻接矩阵。`addEdge`方法用于在节点`i`和`j`之间添加一条边。

一个使用图的示例是路径查找。假设我们有一个城市地图，其中每个节点代表一个地点，每条边代表两个地点之间的道路。我们可以使用图来表示这个地图，然后使用广度优先搜索或深度优先搜索来查找两个地点之间的最短路径。

以下是一个使用邻接表创建无向图并进行深度优先搜索的Java代码示例：

import java.util.LinkedList;
 
public class Graph {
    private final int numVertices;
    private final LinkedList<Integer>[] adjList;
 
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }
 
    public void addEdge(int i, int j) {
        adjList[i].add(j);
        adjList[j].add(i);
    }
 
    public void DFS(int start) {
        boolean[] visited = new boolean[numVertices];
        DFSUtil(start, visited);
    }
 
    private void DFSUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");
        for (int adj : adjList[vertex]) {
            if (!visited[adj]) {
                DFSUtil(adj, visited);
            }
        }
    }
}

这里我们定义了一个`Graph`类，其中`numVertices`表示节点数，`adjList`表示邻接表。`addEdge`方法用于在节点`i`和`j`之间添加一条边。`DFS`方法用于进行深度优先搜索，`DFSUtil`是递归的实现方式。

总结：图是由节点和边构成的数据结构，可以用于描述许多现实世界中的问题。在Java中，可以使用邻接矩阵和邻接表两种方式来创建和表示图。使用图的一个示例是路径查找，可以使用广度优先搜索或深度优先搜索来实现。