（JAVA）图的基本原理和API实现

1. 图

在现实生活中，有许多应用常见会包含很多点以及点点之间的连接，而这些应用场景可以用图这种数据结构来解决。

1.1 图的概述

图的典型例子有地图：

如果把城市看做是一个个的点，把道路看作是一条条的的连接，那么地图就是**“图”**这种数据结构

电路图：

集成电路板其实就是由一个个触电组成的，并把触点与触点间通过线进行连接，这也是“图” 数据结构

1.2 图的定义以及分类

**定义：**图是由一组顶点和一组能够将两个顶点相连的边组成的。

特殊的图：

1. 自环：即一条连接一个顶点和其自身的边
2. 平行边，连接同一对顶点的两条边

图的分类：

按照连接两个顶点的边不同，可以把图分为以下两种：

• **无向图：**边仅仅连接两个顶点，没有其他含义
• **有向图：**边不仅连接两个顶点，并且具有方向

1.3 无向图

1.3.1 图的相关术语

相邻顶点：

• 当两个顶点通过一条边距相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点

度：

• 某个顶点的度就是依附于该顶点的边的个数

子图：

• 是一幅图的所有边的子集（包含这些边依附的顶点）组成的图

路径：

• 是由边顺序连接的一系列顶点组成

环：

• 是一条至少含有一条边且终点和起点相同的路径

连通图：

• 如果图中任意一个顶点都存在一条路径到达另一个顶点，那么这幅图就称为连通图

连通子图：

• 一个非连通图由若干连通的部分组成，每个连通的部分都可以称作该图的连通子图

1.3.2 图的存储结构

要表示一幅图，只需要表示清楚以下两部分内容即可：

1. 图中所有顶点
2. 所有连接顶点的边

常见的图的存储结构有两种：邻接矩阵和邻接表

1.3.2.1 邻接矩阵

1. 使用N*N的二维数组int[N][N] adj，把索引的值看作是顶点
2. 如果顶点v和顶点w相连，我们只需要将adj[v][w]和adj[w][v]的值设置为1，否则设置为0即可

1.3.2.2 邻接表

1. 使用一个大小为v的数组 Queue[v] adj，把索引看作是顶点
2. 每个索引处ajd[v]存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点

• 邻接矩阵的实现更加容易且易懂，但是临邻接矩阵所消耗的内存要比邻接表要多。
  • 邻接表由于使用Queue来存储顶点，所以可以无限随时拓展
  • 而临界矩阵是一个二维数组，规定了指定的大小，因此邻接矩阵只能在某些时间要求大过空间要求时才会使用

1.4 无向图的实现

1.4.1 图的API 设计

public class Graph {
    private final int V;
    private int E;
    private Queue<Integer>[] adj;

    public Graph(int V){
        this.V = V;
        this.E = 0;
        this.adj = new Queue[V];

        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<Integer>();
        }
    }

    public int V(){
        return V;
    }
    public int E(){
        return E;
    }

    // 添加边
    public void addEdge(int v,int w){
        // 在无向图中，边是没有方向的
        adj[v].enqueue(w);
        adj[w].enqueue(v);
        E++;
    }
    // 获取和顶点v相邻的所有顶点
    public Queue<Integer> adj(int v){
        return adj[v];
    }

    // ####################### 深度优先搜索 ################## //
}

1.5 图的搜索

在很多情况下，我们需要遍历图， 得到图的一些信息，例如找出图中与指定的顶点相连的所有顶点，或者判定某个顶点与指定顶点是否相同，是非常常见的需求

有关图的搜索，最经典的算法有深度优先搜索和广度优先搜索。

1.5.1 深度优先搜索

所谓的深度优先搜索，指的是在搜索时，如果遇到一个节点既有子节点，又有兄弟节点，那么先找子节点，任何找兄弟节点

API设计：

public class DepthFirstSearch {
    private boolean[] marked;// 索引代表顶点，指表示当前顶点是否已经被搜索
    public int count;// 记录有多少顶点与s顶点相通

    /**
     * 初始化构造
     * @param G 图的对象
     * @param s 顶点内容
     */
    public DepthFirstSearch(Graph G,int s) {
        this.marked = new boolean[G.V()];
        this.count = 0;

        // 使用深度优先搜索
        dfs(G,s);
    }

    /**
     * 使用深度优先搜索
     * @param G
     * @param v
     */
    private void dfs(Graph G,int v){
        // 把v顶点表示为已搜索
        marked[v] = true;

        // 查找每个顶点里的队列（相连节点）
        for (Integer w: G.adj(v)) {
            // 判断w顶点有没有被搜索过，如果没有被搜索过，则递归调用dfs方法
            if (!marked[w]){
                dfs(G,w);
            }
        };
        // 相通数量+1；
        count++;
    }
    public boolean marked(int w){
        return marked[w];
    }
    public int count(){
        return count;
    }
}

1.5.2 广度优先搜索

所谓广度优先搜索指的是在搜索时，如果遇到一个节点既有子节点又有兄弟节点，那么先找兄弟节点，然后找子节点

1.5.2.1 API设计

public class BreadthFirstSearch {
    private boolean[] marked;// 索引代表顶点，指表示当前顶点是否已经被搜索
    public int count;// 记录有多少顶点与s顶点相通
    private Queue<Integer> waitSeach;// 用于存储搜索邻接表的点

    /**
     * 初始化构造
     * @param G 图的对象
     * @param s 顶点内容
     */
    public BreadthFirstSearch(Graph G, int s) {
        this.marked = new boolean[G.V()];
        this.count = 0;
        this.waitSeach = new Queue<Integer>();

        bfs(G,s);
    }

    /**
     * 使用广度优先搜索
     * @param G
     * @param v
     */
    private void bfs(Graph G,int v){
        // 把v顶点表示为已搜索
        marked[v] = true;

        waitSeach.enqueue(v);

        /**
         * 非真正意义上的广度优先搜索！
         * 由于在31行添加元素，下方while进行循环，
         * 找出弹出queue队列的最后顶点的邻接表，找到邻接表后，
         * 直接递归了，第一次递归，找的是【最后顶点】的邻接表的第一个元素的再【邻接表】
         * 所以从这方面来说还是深度优先搜索
        */
        while (!waitSeach.isEmpty()){
            // 弹出带搜索的顶点
            Integer wait = waitSeach.dequeue();

            // 遍历wait顶点的邻接表
            for (Integer w : G.adj(wait)) {
                // 判断邻接表中的顶点是否已经被搜索，没有被搜索，那么将继续进行递归调用搜索
                if (!marked[w]){
                    bfs(G,w);
                }
            }
        }

        // 相通数量+1；
        count++;
    }
    public boolean marked(int w){
        return marked[w];
    }
    public int count(){
        return count;
    }
}

1.6 路径查找

在生活中，地图是经常使用的工具，通常我们会用它进行导航，输入一个触发城市，输入一个目的地城市，就可以把路线规划好，而在规划好的这个路线上，会路过很多中间的城市。这类问题翻译成专业问题就是：从s顶点到v顶点是否存在一条路径

录入在上图上查找顶点0到顶点4的路径用红色标识处理啊，那么我们可以把该路径标识为 0-2-3-4

1.6.1 路径查找API设计

1.6.2 路径查找实现

实现路径查找，最基本的操作还是得遍历并搜索图，所以，实现暂且基于深度优先搜索来完成。

public class DepthFirstPaths {
    private boolean[] marked;// 所有代表顶点，指标识当前顶点是否已经被搜索
    private int[] edgeTo; // 索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
    private int s;// 起点

    //构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径
    public DepthFirstPaths(Graph G,int s) {
        this.marked = new boolean[G.V()];
        this.s = s;
        this.edgeTo = new int[G.V()];

        // 使用深度优先搜索
        dfs(G,s);
    }

    /**
     * 使用深度优先搜索找出G图中v顶点的所有相通顶点
     * @param G
     * @param v
     */
    private void dfs(Graph G,int v){
        marked[v] = true;

        // 遍历v的邻接表
        for (Integer w : G.adj(v)) {
            // 判断【邻接表顶点】是否已经被搜索，没有则递归
            if (!marked[w]){
                // 记录当前邻接表顶点可以通过哪个顶点到达
                edgeTo[w] = v;
                // 递归
                dfs(G,w);
            }
        }
    }

    /**
     * 判断v顶点与s顶点是否存在路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return marked[v];
    }

    /**
     * 找出从起点s到顶点v的路径
     * @param v 从起点s所要到达的顶点
     */
    public Stack<Integer> pathTo(int v){
        // 判断v顶点是否可达，不可达直接返回null
        if (!hasPathTo(v))
        {
            return null;
        }

        // 创建栈对象，保存路径中的所有顶点
        Stack<Integer> path = new Stack<>();

        // 通过循环，从顶点v开始，一直往前找，找到v对应可到达的顶点为止
        for (int i =v;i != s;i = edgeTo[i]){
            path.push(i);
        }
        // 存入起点
        path.push(s);

        return path;
    }

}

2. 前置文章

1. 浅入数据结构 “堆” - 实现和理论
2. 开始熟悉 “二叉树” 的数据结构
3. 队列 和 符号表 两种数据结构的实现
4. 队列的进阶结构-优先队列
5. 2-3树思想与红黑树的实现与基本原理
6. B树和B+树的实现原理阐述

3. ES8 如何使用?

快来看看这篇好文章吧~~！！
😊👉（全篇详细讲解）ElasticSearch8.7 搭配 SpringDataElasticSearch5.1 的使用