【Java】图的初识

文章目录

【Java】图的初识
- 图是什么
- - 图的基本组成部分
  - 图的类型
  - 图的表示方法
  - 图的常见操作
- Java中图的表示方法
- - 邻接矩阵
  - 邻接表
- 常见操作
- - 图的遍历
  - - 深度优先搜索（DFS）
    - 广度优先搜索（BFS)
- 结论

【Java】图的初识

图是什么

图是一种数学概念，用于表示对象及其相互关系。图由顶点（Vertex）和边（Edge）组成，广泛应用于计算机科学、网络分析、物流优化、社交网络等领域。图可以表示各种实际问题，如城市中的交通线路、社交网络中的人际关系等。

图的基本组成部分

顶点（Vertex）：
- 顶点是图中的一个节点，表示一个对象或实体。
- 在图中，顶点通常用圆圈或点表示。
- 顶点可以有名字或编号，用于区分不同的顶点。
边（Edge）：
- 边是连接两个顶点的线段，表示顶点之间的关系或连接。
- 边可以是有向的（箭头表示方向）或无向的（无箭头表示无方向）。

图的类型

根据边的性质和连接方式，图可以分为以下几种类型：

无向图（Undirected Graph）：
- 在无向图中，边没有方向，表示两个顶点之间的关系是双向的。
- 无向图的边通常用线段表示，不带箭头。
有向图（Directed Graph）：
- 在有向图中，边有方向，表示从一个顶点指向另一个顶点。
- 有向图的边通常用带箭头的线段表示，箭头指示方向。
加权图（Weighted Graph）：
- 在加权图中，边带有权重，表示顶点之间的关系具有某种度量（如距离、成本等）。
- 加权图可以是有向图也可以是无向图，边的权重通常用数值表示。

图的表示方法

在计算机科学中，图的表示方法主要有以下几种：

邻接矩阵（Adjacency Matrix）：
- 邻接矩阵是一种二维数组，用于表示顶点之间的连接关系。
- 如果顶点i和顶点j之间有边，则matrix[i][j]为1（或权重值），否则为0。
- 邻接矩阵适用于稠密图（边数接近顶点数的平方），但对于稀疏图（边数远小于顶点数的平方）来说，存储效率较低。
邻接表（Adjacency List）：
- 邻接表是一种数组加链表的结构，每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。
- 邻接表适用于稀疏图，存储效率较高，因为只存储实际存在的边。

图的常见操作

在使用图时，有许多常见的操作，包括：

添加边：在图中添加一条边，以表示两个顶点之间的新关系。
删除边：从图中删除一条边，以表示两个顶点之间的关系不再存在。
遍历图：访问图中的所有顶点和边，常用的遍历方法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

Java中图的表示方法

在Java中，图的表示方法主要有两种：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。

邻接矩阵

邻接矩阵是一种二维数组，用于表示顶点之间的连接关系。如果顶点i和顶点j之间有边，则matrix[i][j]为1（或权重值），否则为0。

public class Graph {
    private int[][] adjacencyMatrix;
    private int numVertices;

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
    }

    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 void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

邻接表

邻接表是一种数组加链表的结构，每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。

import java.util.LinkedList;

public class Graph {
    private LinkedList<Integer>[] adjacencyList;
    private int numVertices;

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

    public void addEdge(int i, int j) {
        adjacencyList[i].add(j);
        adjacencyList[j].add(i); // 对于无向图
    }

    public void removeEdge(int i, int j) {
        adjacencyList[i].remove((Integer) j);
        adjacencyList[j].remove((Integer) i); // 对于无向图
    }

    public void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print("Vertex " + i + ":");
            for (Integer edge : adjacencyList[i]) {
                System.out.print(" -> " + edge);
            }
            System.out.println();
        }
    }
}

常见操作

图的遍历

图的遍历主要有深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索是一种遍历图的方法，从一个起始顶点出发，沿着一条路径尽可能深入，然后回溯继续搜索未访问的顶点。

import java.util.Stack;

public void depthFirstSearch(int startVertex) {
    boolean[] visited = new boolean[numVertices];
    Stack<Integer> stack = new Stack<>();

    stack.push(startVertex);
    while (!stack.isEmpty()) {
        int vertex = stack.pop();
        if (!visited[vertex]) {
            visited[vertex] = true;
            System.out.print(vertex + " ");
            for (int i : adjacencyList[vertex]) {
                if (!visited[i]) {
                    stack.push(i);
                }
            }
        }
    }
}

广度优先搜索（BFS)

广度优先搜索是一种遍历图的方法，从一个起始顶点出发，逐层访问相邻的顶点。

import java.util.LinkedList;
import java.util.Queue;

public void breadthFirstSearch(int startVertex) {
    boolean[] visited = new boolean[numVertices];
    Queue<Integer> queue = new LinkedList<>();

    queue.add(startVertex);
    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        if (!visited[vertex]) {
            visited[vertex] = true;
            System.out.print(vertex + " ");
            for (int i : adjacencyList[vertex]) {
                if (!visited[i]) {
                    queue.add(i);
                }
            }
        }
    }
}