java graph结构_数据结构—图(Graph)的入门概念、存储结构、遍历方式以及Java代码的实现...

Graph(图)是一种非常重要的数据结构，它可以用来表示许多实际问题，比如社交网络、路线规划等。在这里，我将为你介绍图(Graph)的入门概念、存储结构、遍历方式以及Java代码的实现。

1. 入门概念

Graph(图)由节点(vertex)和边(edge)组成，节点表示图中的一个实体，边表示节点之间的关系。图可以分为有向图和无向图，有向图中每条边有一个方向，而无向图中每条边没有方向。图中的路径(path)是一系列节点，这些节点通过边相互连接。

2. 存储结构

图的存储结构一般有两种方式：邻接矩阵和邻接表。

邻接矩阵：将图中的节点用一个数组来表示，用一个二维数组来表示边的关系，当两个节点之间有边时，对应的二维数组中的元素为1，否则为0。

邻接表：将图中的节点用一个链表来表示，每个节点的链表中存储与其相连的节点。

3. 遍历方式

对于图的遍历，一般有两种方式：深度优先遍历(DFS)和广度优先遍历(BFS)。

深度优先遍历：从一个节点开始，一直沿着当前路径遍历到底，直到不能再遍历为止，然后回退到上一个节点，继续遍历其他路径。这种遍历方式一般用递归实现。

广度优先遍历：从一个节点开始，依次遍历与其相邻的节点，再遍历与这些节点相邻的节点，依次类推。这种遍历方式一般用队列实现。

4. Java代码的实现

以下是Java代码实现图(Graph)的基本操作：

import java.util.*;

public class Graph {
    int[][] adjacencyMatrix; // 邻接矩阵存储图
    LinkedList<Integer>[] adjacencyList; // 邻接表存储图
    int numVertices; // 节点个数

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
        adjacencyList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; ++i) {
            adjacencyList[i] = new LinkedList<Integer>();
        }
    }

    // 添加边
    public void addEdge(int i, int j) {
        adjacencyMatrix[i][j] = 1;
        adjacencyList[i].add(j);
    }

    // 深度优先遍历
    public void DFS(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        DFSUtil(startVertex, visited);
    }

    private void DFSUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");
        Iterator<Integer> i = adjacencyList[vertex].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // 广度优先遍历
    public void BFS(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        LinkedList<Integer> queue = new LinkedList<Integer>();
        visited[startVertex] = true;
        queue.add(startVertex);
        while (queue.size() != 0) {
            startVertex = queue.poll();
            System.out.print(startVertex + " ");
            Iterator<Integer> i = adjacencyList[startVertex].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

以上就是图(Graph)的入门概念、存储结构、遍历方式以及Java代码的实现。希望对你有所帮助！