图的邻接矩阵表示法(Java)

一、基础知识理解

(本人部分口语化解释+百度学科解释,专业解释请自行查阅文献,本人是通过屈婉玲、耿素云、张立昂编著《离散数学》(第五版)入门图论,这本书是入门计算机专业不可多得的好书。)

图(Graph):描述一组对象(元素)的结构(由二元组三元组进行定义)。

顶点(Vertex):图中的每一个对象(元素)被称为顶点。

边(Edge):用于两个顶点之间的关系。(弧(Arc):有方向的边;弧尾(Tail):初始点;弧头(Head):终端点)

二元组(V,E):V称为顶集(Vertices Set),E称为边集(Edges set),V(G)和E(G)。

三元组(V,E,I):I称为关联函数,I将E中的每一个元素映射到V×V(类似于邻接矩阵的表现形式)。

有向图:图中每一条边都有方向。

无向图:略。

简单图:无向图如果任意两顶点之间只有一条边(在有向图中为两顶点之间每个方向只有一条边);边集中不含环。

权(Weight):图中的边携带权值。

度(Degree):一个顶点的度是指与该顶点相关联的边的条数,顶点v的度记作d(v)。

自环(Loop):若一条边的两个顶点为同一顶点,则此边称作自环。

路径(Path):从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk,其中ei的顶点为vi及vi - 1,k称作路径的长度。如果它的起止顶点相同,该路径是“闭”的,反之,则称为“开”的。一条路径称为一简单路径(simple path),如果路径中除起始与终止顶点可以重合外,所有顶点两两不等。

入度(In-degree)出度(Out-degree):对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数;出度则是相对的概念,指以该顶点为起点的边数。

轨道(Track):如果路径P(u,v)中的顶点各不相同,则该路径称为u到v的一条轨道。

闭的行迹称作回路(Circuit)闭的轨称作圈/环(Cycle)

连通分量:无向图 G的一个极大连通子图称为 G的一个连通分量(或连通分支)。连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。

强连通图:有向图 G=(V,E) 中,若对于V中任意两个不同的顶点 x和 y,都存在从x到 y以及从 y到 x的路径,则称 G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连分量。

单向连通图:设G=是有向图,如果u->v意味着图G至多包含一条从u到v的简单路径,则图G为单连通图。

弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

初级通路:通路中所有的顶点互不相同。初级通路必为简单通路,但反之不真。

。。。

(还有桥、自环边,割点等其他术语,本文实验没有涉及故不再介绍,后期补更)

二、图的存储结构

数组(邻接矩阵)存储表示(有向或无向)(本文将使用邻接矩阵来实现图结构)

邻接表存储表示

有向图的十字链表存储表示

无向图的邻接多重表存储表示

三、Java代码实现

完成现状:

  1. 使用邻接矩阵表示法,但并非是传统的二维数组,而是二维的List,方便图中元素增加、删除等操作;
  2. 一套代码实现四种类型的图:有向无权/有权图和无向无权/有权图,但不同类型之间不能相互转换(也不是不可以,只是没有任何转换的理论依据,意义不大);
  3. 包含深度/广度优先遍历,找环算法等等(但不包含与权值有关的任何算法,原因是因为权值的计算需要比较器,我暂时还没有系统的融合方案);
  4. 出色的算法效率(算法人为时空复杂度操碎了心,如果有人愿意细品我的写的算法,可能会明白我的苦心,呜呜呜~~~);
  5. 整套代码细节满满,可以说每一个较复杂的方法,都是被我仔细优化过的;
  6. 本人的算法风格——“天下武功,唯快不破!”,为了追求高效的时间效率,本人从来不会考虑空间的浪费,硬件能解决的问题关我们软件什么事!
  7. 后期会不断完善和更新;
  8. 可以白嫖,但希望白嫖的同学有时间可以多品品,学无止境!
  9. 多说无益,千行代码,带领大家入门图论世界,大家来一起学习一起进步!

代码实现:

Vertex.java

package graph;

/**
 * 该类未启用(为具有平行边的多重图做准备)
 *
 * @param <E> 顶点携带信息的类型
 */
public class Vertex<E> {

    private E value;

    public Vertex(E value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "graph.Vertex{" +
                "value=" + value +
                '}';
    }
}

Edge.java

package graph;

import com.sun.istack.internal.NotNull;

/**
 * 弧(Arc)/边(Edge)
 * 边:表示两个顶点之间的关系
 * 弧:有方向的边
 *
 * @param <T> 权值类型
 * @param <V> 信息类型
 */
public class Edge<T, V> {
    /**
     * 弧尾(Tail)/初始点
     * (在有向图中用于区分边的方向并用于记录顶点所对应的边在邻接矩阵中的坐标;在无向图中则没有方向可言)
     */
    @NotNull
    private final int tailIndex;

    /**
     * 弧头(Head)/终端点
     * (在有向图中用于区分边的方向并用于记录顶点所对应的边在邻接矩阵中的坐标;在无向图中则没有方向可言)
     */
    @NotNull
    private final int headIndex;

    /**
     * 对无权图,用true或false表示相邻否;
     * 对带权图,则为权值。
     */
    private Object weight;

    /**
     * info表示该弧/边携带的信息
     */
    private V info;

    public Edge(@NotNull int tailIndex, @NotNull int headIndex, Object weight, V info) {
        this.tailIndex = tailIndex;
        this.headIndex = headIndex;
        this.weight = weight;
        this.info = info;
    }

    public int getTailIndex() {
        return tailIndex;
    }

    public int getHeadIndex() {
        return headIndex;
    }

    @SuppressWarnings("unchecked")
    public T getWeight() {
        return (T) weight;
    }

    public void setWeight(Object weight) {
        this.weight = weight;
    }

    public V getInfo() {
        return info;
    }

    public void setInfo(V info) {
        this.info = info;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "tailIndex=" + tailIndex +
                ", headIndex=" + headIndex +
                ", weight=" + weight +
                ", info=" + info +
                '}';
    }
}

GraphKind.java

package graph;

/**
 * 图的种类
 * (带权重的图通常称为网)
 */
public enum GraphKind {
    /**
     * 有向图
     */
    DG,
    /**
     * 有向网
     */
    DN,
    /**
     * 无向图
     */
    UDG,
    /**
     * 无向网
     */
    UDN
}

Graph.java

package graph;

import java.util.List;
import java.util.Set;

/**
 * 数据结构-图
 *
 * @param <E> 顶点类型
 * @param <T> 弧/边权值类型
 * @param <V> 弧/边信息类型
 */
public interface Graph<E, T, V> {

    int getVertexNum();

    int getEdgeNum();

    GraphKind getKind();

    int findVertex(E vertex);

    int findLastVertex(E vertex);

    Set<Integer> findVertexIndexes(E vertex);

    E getVertex(int index);

    E setVertex(int index, E vertex);

    boolean addVertex(E vertex);

    boolean addVertexes(List<E> vertexes);

    void addVertex(int index, E vertex);

    E deleteVertex(int index);

    int deleteFirstVertex(E vertex);

    List<E> deleteVertexes(int[] vertexIndexes);

    Edge<T, V> addEdgeByIndex(int index1, int index2);

    Edge<T, V> addEdgeByIndex(int index1, int index2, T weight, V info);

    Set<Edge<T, V>> addEdgesByIndexes(Set<int[]> indexes);

    Edge<T, V> deleteEdge(int index1, int index2);

    Edge<T, V> updateEdge(int index1, int index2, T weight, V info);

    Edge<T, V> updateEdgeWeight(int index1, int index2, T weight);

    Edge<T, V> updateEdgeInfo(int index1, int index2, V info);

    boolean hasEdge(int index1, int index2);

    Edge<T, V> getEdge(int index1, int index2);

    Edge<T, V> getFirstAdjacentEdge(int index);

    Set<Edge<T, V>> getAdjacentEdges(int index);

    Set<Edge<T, V>> getInEdges(int index);

    Edge<T, V> getFirstInEdge(int index);

    Set<Edge<T, V>> getOutEdges(int index);

    Edge<T, V> getFirstOutEdge(int index);

    int getInDegree(int index);

    int getOutDegree(int index);

    int getDegree(int index);

    E getFirstInAdjacentVertex(int index);

    int getFirstInAdjacentVertexIndex(int index);

    List<E> getInAdjacentVertexes(int index);

    Set<Integer> getInAdjacentVertexIndexes(int index);

    E getFirstOutAdjacentVertex(int index);

    int getFirstOutAdjacentVertexIndex(int index);

    List<E> getOutAdjacentVertexes(int index);

    Set<Integer> getOutAdjacentVertexIndexes(int index);

    E getFirstAdjacentVertex(int index);

    int getFirstAdjacentVertexIndex(int index);

    List<E> getAdjacentVertexes(int index);

    Set<Integer> getAdjacentVertexIndexes(int index);

    List<List<Integer>> DFSTraverse();

    List<List<Integer>> BFSTraverse();

    boolean isDirectedGraph();

    boolean isCompletedGraph();

    boolean isConnectedGraph();

    boolean isEmptyGraph();

    boolean isNetwork();

    Object[] getVertexes();

    Set<Edge<T, V>> getEdges();

    List<Integer> getFirstPath(int index1, int index2);

    List<List<Integer>> getPaths(int index1, int index2);

    boolean hasPath(int index1, int index2);

    List<Integer> getFirstCycle(int index);

    List<List<Integer>> getCycles(int index);

    boolean hasCycle(int index);

    boolean hasCycle();

    List<List<Integer>> getCycles();

    Edge<T, V> getLoop(int index);

    boolean hasLoop(int index);

    boolean hasLoop();

    boolean isConnected(int index1, int index2);

}

GraphByAdjacentMatrix.java

package graph.graphImpl;


import com.sun.istack.internal.NotNull;
import graph.Edge;
import graph.Graph;
import graph.GraphKind;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * 千行代码,带你入门图论世界
 * 图-实现类
 * 特性:
 * 1、具有自环边,不具备平行边;
 * 2、有权值;
 * 3、有方向;
 * 4、所有算法均考虑了有向图的方向性,但不涉及与权值有关的任何算法(权值需要比较,邻接矩阵可能并不适合一些拓扑算法的实现)
 *
 * 算法人为时空复杂度操碎了心,如果有人愿意细品我的写的算法,可能会明白我的苦心,呜呜呜~~~
 *
 */
public class GraphByAdjacentMatrix<E, T, V> implements Graph<E, T, V> {
    /**
     * 邻接矩阵
     */
    private final List<List<Edge<T, V>>> adjacencyMatrix;
    /**
     * 图的种类标志
     */
    private final GraphKind graphKind;
    /**
     * 顶点向量
     */
    private final List<E> vertexes;
    /**
     * 图的当前顶点数和弧数
     */
    private int vertexNum, edgeNum;
    /**
     * 辅助遍历的空间
     */
    private boolean[] visited;
    private Queue<Integer> queue;
    private int traversableNum;
    private List<List<Integer>> cycles;
    private List<List<Integer>> paths;

    public GraphByAdjacentMatrix(@NotNull List<E> vertexes, @NotNull List<Edge<T, V>> edges, @NotNull GraphKind graphKind) {
        this.vertexes = vertexes;
        this.vertexNum = vertexes.size();
        this.adjacencyMatrix = createAdjacentMatrix(edges, vertexes.size(), graphKind);
        this.graphKind = graphKind;
    }

    public GraphByAdjacentMatrix(@NotNull GraphKind graphKind) {
        vertexes = new ArrayList<>();
        this.adjacencyMatrix = createAdjacentMatrix(null, 0, graphKind);
        this.graphKind = graphKind;
    }

    public GraphByAdjacentMatrix(@NotNull List<E> vertexes, @NotNull GraphKind graphKind) {
        this.vertexes = vertexes;
        this.vertexNum = vertexes.size();
        this.adjacencyMatrix = createAdjacentMatrix(null, 0, graphKind);
        this.graphKind = graphKind;
    }

    @Override
    public String toString() {
        return "GraphByAdjacentMatrix{\n" +
                "vertexes=" + vertexes +
                ",\nAdjacentMatrix=" + adjacentMatrixToString(adjacencyMatrix) +
                ",\nVertexNum=" + vertexNum +
                ",\nEdgeNum=" + edgeNum +
                ",\ngraphKind=" + graphKind +
                '}';
    }

    /**
     * 实现邻接矩阵的打印方法以辅助Graph类实现toString方法
     *
     * @param AdjacentMatrix 邻接矩阵
     * @return 邻接矩阵的toString()
     */
    private String adjacentMatrixToString(List<List<Edge<T, V>>> AdjacentMatrix) {
        StringBuilder stringBuilder = new StringBuilder().append("[\n");
        for (List<Edge<T, V>> edges : AdjacentMatrix)
            stringBuilder.append(edges).append("\n");
        return stringBuilder.append("]").toString();
    }

    /**
     * 稳定的自增弧/边的数量
     *
     * @param tailIndex 弧/边的起始点
     * @param headIndex 弧/边的终端点
     */
    private void growEdgeNum(int tailIndex, int headIndex) {
        rangeCheck(tailIndex);
        rangeCheck(headIndex);
        if (adjacencyMatrix.get(tailIndex).get(headIndex) == null)
            ++edgeNum;
    }

    /**
     * 根据传入指定的图类型graphKind、顶点数量order和弧/边集合来生成邻接矩阵
     *
     * @param edges     弧/边集
     * @param order     顶点数量
     * @param graphKind 生成的图类型
     * @return 邻接矩阵
     */
    private List<List<Edge<T, V>>> createAdjacentMatrix(List<Edge<T, V>> edges, int order, GraphKind graphKind) {
        /*
          根据传入的顶点数量order来初始化邻接矩阵
         */
        List<List<Edge<T, V>>> adjacencyMatrix = new ArrayList<>();
        for (int i = 0; i < order; i++) {
            List<Edge<T, V>> vector = new ArrayList<>();
            for (int j = 0; j < order; j++)
                vector.add(null);
            adjacencyMatrix.add(vector);
        }
        /*
         生成邻接矩阵
         */
        if (edges != null)
            switch (graphKind) {
                case DG:
                    edges.forEach(edge -> {
                        int tailIndex = edge.getTailIndex();
                        int headIndex = edge.getHeadIndex();
                        edge.setWeight(true);
                        growEdgeNum(tailIndex, headIndex);
                        adjacencyMatrix.get(tailIndex).set(headIndex, edge);
                    });
                    break;
                case DN:
                    edges.forEach(edge -> {
                        int tailIndex = edge.getTailIndex();
                        int headIndex = edge.getHeadIndex();
                        growEdgeNum(tailIndex, headIndex);
                        adjacencyMatrix.get(tailIndex).set(headIndex, edge);
                    });
                    break;
                case UDG:
                    edges.forEach(edge -> {
                        int tailIndex = edge.getTailIndex();
                        int headIndex = edge.getHeadIndex();
                        edge.setWeight(true);
                        growEdgeNum(tailIndex, headIndex);
                        adjacencyMatrix.get(tailIndex).set(headIndex, edge);
                        adjacencyMatrix.get(headIndex).set(tailIndex, edge);
                    });
                    break;
                case UDN:
                    edges.forEach(edge -> {
                        int tailIndex = edge.getTailIndex();
                        int headIndex = edge.getHeadIndex();
                        growEdgeNum(tailIndex, headIndex);
                        adjacencyMatrix.get(tailIndex).set(headIndex, edge);
                        adjacencyMatrix.get(headIndex).set(tailIndex, edge);
                    });
                    break;
                default:
                    throw new RuntimeException("未知的图类型!");
            }
        return adjacencyMatrix;
    }

    /**
     * 判断顶点索引值是否越界;
     * 越界抛出运行时异常
     *
     * @param index 顶点索引值
     */
    private void rangeCheck(int index) {
        if (index < 0 || index > vertexNum - 1)
            throw new IndexOutOfBoundsException("顶点下标必须<" + (vertexNum - 1) + "并且>=0!");
    }

    @Override
    public int getVertexNum() {
        return vertexNum;
    }

    @Override
    public int getEdgeNum() {
        return edgeNum;
    }

    @Override
    public GraphKind getKind() {
        return graphKind;
    }

    /**
     * 获取第一个顶点是vertex的索引值
     *
     * @param vertex 顶点
     * @return 索引值
     */
    @Override
    public int findVertex(E vertex) {
        return vertexes.indexOf(vertex);
    }

    /**
     * 获取最后一个顶点是vertex的索引值
     *
     * @param vertex 顶点
     * @return 索引值
     */
    @Override
    public int findLastVertex(E vertex) {
        return vertexes.lastIndexOf(vertex);
    }

    @Override
    public Set<Integer> findVertexIndexes(E vertex) {
        Set<Integer> indexes = new HashSet<>();
        for (int i = 0; i < vertexes.size(); i++)
            if (vertexes.get(i).equals(vertex))
                indexes.add(i);
        return indexes;
    }

    @Override
    public E getVertex(int index) {
        return vertexes.get(index);
    }

    @Override
    public E setVertex(int index, E vertex) {
        return vertexes.set(index, vertex);
    }

    @Override
    public boolean addVertex(E vertex) {
        vertexes.add(vertex);
        List<Edge<T, V>> vector = new ArrayList<>();
        //循环旧的VertexNum次
        adjacencyMatrix.forEach(edges -> {
            edges.add(null);
            //复用循环,降低时间复杂度
            vector.add(null);
        });
        vector.add(null);
        adjacencyMatrix.add(vector);
        ++vertexNum;
        return true;
    }

    @Override
    public boolean addVertexes(List<E> vertexes) {
        if (vertexes != null) {
            vertexes.forEach(this::addVertex);
            return true;
        }
        return false;
    }

    /**
     * 该方法时间复杂度超高,极其费时,不建议使用;
     * 事实上没有必要指定位置插入顶点,这对图数据结构可能是毫无意义的
     *
     * @param index  指定插入位置的索引值
     * @param vertex 待插入顶点
     */
    @Override
    public void addVertex(int index, E vertex) {
        vertexes.add(vertex);
        List<Edge<T, V>> vector = new ArrayList<>();
        //循环旧的VertexNum次
        adjacencyMatrix.forEach(edges -> {
            edges.add(index, null);
            //复用循环,降低时间复杂度
            vector.add(null);
        });
        vector.add(null);
        adjacencyMatrix.add(index, vector);
        ++vertexNum;
    }

    /**
     * 删除指定索引值对应位置的顶点
     *
     * @param index 删除index索引值对应的顶点
     * @return 被删除的顶点
     */
    @Override
    public E deleteVertex(int index) {
        rangeCheck(index);
        E vertex = vertexes.remove(index);
        --vertexNum;
        int ReducedEdgeNum = 0;
        for (int i = 0; i < vertexNum; i++) {
            if (adjacencyMatrix.get(i).remove(index) != null)
                ++ReducedEdgeNum;
            if (adjacencyMatrix.get(index).get(i) != null)
                ++ReducedEdgeNum;
        }
        adjacencyMatrix.remove(index);
        edgeNum -= ReducedEdgeNum;
        return vertex;
    }

    @Override
    public int deleteFirstVertex(E vertex) {
        int index = findVertex(vertex);
        if (index != -1)
            deleteVertex(index);
        return index;
    }

    @Override
    public List<E> deleteVertexes(int[] vertexIndexes) {
        List<E> vertexes = new ArrayList<>();
        if (vertexIndexes == null)
            return vertexes;
        for (int vertexIndex : vertexIndexes)
            vertexes.add(deleteVertex(vertexIndex));
        return vertexes;
    }

    /**
     * 通过索引值添加一条边
     *
     * @return 旧的边
     */
    @Override
    public Edge<T, V> addEdgeByIndex(int index1, int index2) {
        return addEdgeByIndex(index1, index2, null, null);
    }

    /**
     * 通过索引值添加一条边
     *
     * @return 旧的边
     */
    @Override
    public Edge<T, V> addEdgeByIndex(int index1, int index2, T weight, V info) {
        growEdgeNum(index1, index2);
        Edge<T, V> edge;
        if (isNetwork())
            edge = new Edge<>(index1, index2, weight, info);
        else
            edge = new Edge<>(index1, index2, true, info);
        if (!isDirectedGraph())
            adjacencyMatrix.get(index2).set(index1, edge);
        return adjacencyMatrix.get(index1).set(index2, edge);
    }

    @Override
    public Set<Edge<T, V>> addEdgesByIndexes(Set<int[]> indexes) {
        Set<Edge<T, V>> edges = new HashSet<>();
        if (isNetwork() && isDirectedGraph())
            indexes.forEach(e -> {
                if (e == null || e.length != 2)
                    throw new RuntimeException("生成弧/边有且仅有两个顶点的索引值");
                else {
                    growEdgeNum(e[0], e[1]);
                    edges.add(adjacencyMatrix.get(e[0]).set(e[1], new Edge<>(e[0], e[1], null, null)));
                }
            });
        else if (!isNetwork() && isDirectedGraph())
            indexes.forEach(e -> {
                if (e == null || e.length != 2)
                    throw new RuntimeException("生成弧/边有且仅有两个顶点的索引值");
                else {
                    growEdgeNum(e[0], e[1]);
                    edges.add(adjacencyMatrix.get(e[0]).set(e[1], new Edge<>(e[0], e[1], true, null)));
                }
            });
        else if (isNetwork() && !isDirectedGraph())
            indexes.forEach(e -> {
                if (e == null || e.length != 2)
                    throw new RuntimeException("生成弧/边有且仅有两个顶点的索引值");
                else {
                    growEdgeNum(e[0], e[1]);
                    Edge<T, V> edge = new Edge<>(e[0], e[1], null, null);
                    edges.add(adjacencyMatrix.get(e[0]).set(e[1], edge));
                    adjacencyMatrix.get(e[1]).set(e[0], edge);
                }
            });
        else
            indexes.forEach(e -> {
                if (e == null || e.length != 2)
                    throw new RuntimeException("生成弧/边有且仅有两个顶点的索引值");
                else {
                    growEdgeNum(e[0], e[1]);
                    Edge<T, V> edge = new Edge<>(e[0], e[1], true, null);
                    edges.add(adjacencyMatrix.get(e[0]).set(e[1], edge));
                    adjacencyMatrix.get(e[1]).set(e[0], edge);
                }
            });
        return edges;
    }

    @Override
    public Edge<T, V> deleteEdge(int index1, int index2) {
        if (hasEdge(index1, index2)) {
            if (!isDirectedGraph())
                adjacencyMatrix.get(index2).set(index1, null);
            --vertexNum;
            return adjacencyMatrix.get(index1).set(index2, null);
        }
        return null;
    }

    @Override
    public Edge<T, V> updateEdge(int index1, int index2, T weight, V info) {
        Edge<T, V> edge = getEdge(index1, index2);
        if (edge != null) {
            if (isNetwork())
                edge.setWeight(weight);
            edge.setInfo(info);
            return edge;
        } else
            throw new RuntimeException("<" + index1 + "," + index2 + ">" + "不是弧/边!");
    }

    @Override
    public Edge<T, V> updateEdgeWeight(int index1, int index2, T weight) {
        Edge<T, V> edge = getEdge(index1, index2);
        if (edge != null) {
            if (isNetwork())
                edge.setWeight(weight);
            return edge;
        } else
            throw new RuntimeException("<" + index1 + "," + index2 + ">" + "不是弧/边!");
    }

    @Override
    public Edge<T, V> updateEdgeInfo(int index1, int index2, V info) {
        Edge<T, V> edge = getEdge(index1, index2);
        if (edge != null) {
            edge.setInfo(info);
            return edge;
        } else
            throw new RuntimeException("<" + index1 + "," + index2 + ">" + "不是弧/边!");
    }

    @Override
    public boolean hasEdge(int index1, int index2) {
        return getEdge(index1, index2) != null;
    }

    @Override
    public Edge<T, V> getEdge(int index1, int index2) {
        rangeCheck(index1);
        rangeCheck(index2);
        return adjacencyMatrix.get(index1).get(index2);
    }

    @Override
    public Set<Edge<T, V>> getInEdges(int index) {
        rangeCheck(index);
        Set<Edge<T, V>> edges = new HashSet<>();
        adjacencyMatrix.forEach(vector -> {
            Edge<T, V> edge = vector.get(index);
            if (edge != null)
                edges.add(edge);
        });
        return edges;
    }

    @Override
    public Edge<T, V> getFirstInEdge(int index) {
        rangeCheck(index);
        for (List<Edge<T, V>> vector : adjacencyMatrix) {
            Edge<T, V> edge = vector.get(index);
            if (edge != null)
                return edge;
        }
        return null;
    }

    @Override
    public Set<Edge<T, V>> getOutEdges(int index) {
        rangeCheck(index);
        Set<Edge<T, V>> edges = new HashSet<>();
        adjacencyMatrix.get(index).forEach(edge -> {
            if (edge != null)
                edges.add(edge);
        });
        return edges;
    }

    @Override
    public Edge<T, V> getFirstOutEdge(int index) {
        rangeCheck(index);
        for (Edge<T, V> edge : adjacencyMatrix.get(index))
            if (edge != null)
                return edge;
        return null;
    }

    @Override
    public Edge<T, V> getFirstAdjacentEdge(int index) {
        Edge<T, V> firstOutEdge = getFirstOutEdge(index);
        if (firstOutEdge != null)
            return firstOutEdge;
        return getFirstInEdge(index);
    }

    @Override
    public Set<Edge<T, V>> getAdjacentEdges(int index) {
        Set<Edge<T, V>> edges = getInEdges(index);
        /*
          优化时间复杂度
         */
        if (isDirectedGraph())
            adjacencyMatrix.get(index).forEach(edge -> {
                if (edge != null)
                    edges.add(edge);
            });
        return edges;
    }

    @Override
    public int getInDegree(int index) {
        rangeCheck(index);
        return (int) adjacencyMatrix.stream().filter(vector -> vector.get(index) != null).count();
    }

    @Override
    public int getOutDegree(int index) {
        rangeCheck(index);
        return (int) adjacencyMatrix.get(index).stream().filter(Objects::nonNull).count();
    }

    @Override
    public int getDegree(int index) {
        int degree = getOutDegree(index);
        if (isDirectedGraph()) {
            degree += (int) adjacencyMatrix.stream().filter(vector -> vector.get(index) != null).count();
            if (hasEdge(index, index))
                return degree - 1;
            return degree;
        }
        return degree;
    }

    @Override
    public int getFirstInAdjacentVertexIndex(int index) {
        Edge<T, V> firstInEdge = getFirstInEdge(index);
        if (firstInEdge == null)
            return -1;
        return firstInEdge.getTailIndex();
    }

    /**
     * 不能用返回值来作为衡量顶点存在的依据,因为顶点可以存入null
     */
    @Override
    public E getFirstInAdjacentVertex(int index) {
        int firstInAdjacentVertexIndex = getFirstInAdjacentVertexIndex(index);
        if (firstInAdjacentVertexIndex == -1)
            return null;
        return vertexes.get(firstInAdjacentVertexIndex);
    }

    @Override
    public List<E> getInAdjacentVertexes(int index) {
        if (isDirectedGraph()) {
            rangeCheck(index);
            List<E> vertexes = new ArrayList<>();
            for (int i = 0; i < this.vertexes.size(); i++)
                if (index != i && adjacencyMatrix.get(i).get(index) != null)
                    vertexes.add(this.vertexes.get(i));
            return vertexes;
        }
        return getAdjacentVertexes(index);
    }

    @Override
    public Set<Integer> getInAdjacentVertexIndexes(int index) {
        if (isDirectedGraph()) {
            rangeCheck(index);
            Set<Integer> vertexIndexes = new HashSet<>();
            for (int i = 0; i < this.vertexes.size(); i++)
                if (index != i && adjacencyMatrix.get(i).get(index) != null)
                    vertexIndexes.add(i);
            return vertexIndexes;
        }
        return getAdjacentVertexIndexes(index);
    }

    @Override
    public int getFirstOutAdjacentVertexIndex(int index) {
        Edge<T, V> firstOutEdge = getFirstOutEdge(index);
        if (firstOutEdge == null)
            return -1;
        return firstOutEdge.getHeadIndex();
    }

    @Override
    public E getFirstOutAdjacentVertex(int index) {
        int firstOutAdjacentVertexIndex = getFirstOutAdjacentVertexIndex(index);
        if (firstOutAdjacentVertexIndex == -1)
            return null;
        return vertexes.get(firstOutAdjacentVertexIndex);
    }

    @Override
    public List<E> getOutAdjacentVertexes(int index) {
        if (isDirectedGraph()) {
            rangeCheck(index);
            List<E> vertexes = new ArrayList<>();
            for (int i = 0; i < this.vertexes.size(); i++)
                if (index != i && adjacencyMatrix.get(index).get(i) != null)
                    vertexes.add(this.vertexes.get(i));
            return vertexes;
        }
        return getAdjacentVertexes(index);
    }

    @Override
    public Set<Integer> getOutAdjacentVertexIndexes(int index) {
        if (isDirectedGraph()) {
            rangeCheck(index);
            Set<Integer> vertexIndexes = new HashSet<>();
            for (int i = 0; i < this.vertexes.size(); i++)
                if (index != i && adjacencyMatrix.get(index).get(i) != null)
                    vertexIndexes.add(i);
            return vertexIndexes;
        }
        return getAdjacentVertexIndexes(index);
    }

    @Override
    public E getFirstAdjacentVertex(int index) {
        return getFirstOutAdjacentVertex(index);
    }

    @Override
    public int getFirstAdjacentVertexIndex(int index) {
        return getFirstOutAdjacentVertexIndex(index);
    }

    @Override
    public List<E> getAdjacentVertexes(int index) {
        rangeCheck(index);
        List<E> vertexes = new ArrayList<>();
        for (int i = 0; i < this.vertexes.size(); i++) {
            if (index == i)
                continue;
            if (adjacencyMatrix.get(index).get(i) != null)
                vertexes.add(this.vertexes.get(i));
            if (isDirectedGraph() && adjacencyMatrix.get(i).get(index) != null)
                vertexes.add(this.vertexes.get(i));
        }
        return vertexes;
    }

    @Override
    public Set<Integer> getAdjacentVertexIndexes(int index) {
        rangeCheck(index);
        Set<Integer> vertexIndexes = new HashSet<>();
        for (int i = 0; i < this.vertexes.size(); i++) {
            if (index == i)
                continue;
            if (adjacencyMatrix.get(index).get(i) != null)
                vertexIndexes.add(i);
            if (isDirectedGraph() && adjacencyMatrix.get(i).get(index) != null)
                vertexIndexes.add(i);
        }
        return vertexIndexes;
    }

    /**
     * 在有向图中具有方向性,对没有入边的顶点,遍历不在同一个连通分量中
     */
    @Override
    public List<List<Integer>> DFSTraverse() {
        List<List<Integer>> oneTraversal = new ArrayList<>();
        if (vertexNum == 0)
            return oneTraversal;
        visited = new boolean[vertexNum];
        for (int i = 0; i < vertexNum; i++)
            if (!visited[i])
                oneTraversal.add(DFS(new ArrayList<>(), i));

        return oneTraversal;
    }

    private List<Integer> DFS(List<Integer> path, int v) {
        visited[v] = true;
        path.add(v);
        getOutAdjacentVertexIndexes(v).forEach(index -> {
            if (!visited[index])
                DFS(path, index);
        });
        return path;
    }

    /**
     * 在有向图中具有方向性,对没有入边的顶点,遍历不在同一个连通分量中
     */
    @Override
    public List<List<Integer>> BFSTraverse() {
        List<List<Integer>> oneTraversal = new ArrayList<>();
        if (vertexNum == 0)
            return oneTraversal;
        visited = new boolean[vertexNum];
        queue = new LinkedList<>();
        for (int i = 0; i < vertexNum; i++)
            if (!visited[i])
                oneTraversal.add(BFS(new ArrayList<>(), i));

        return oneTraversal;
    }

    private List<Integer> BFS(List<Integer> path, int v) {
        visited[v] = true;
        path.add(v);
        queue.offer(v);
        while (!queue.isEmpty()) {
            getOutAdjacentVertexIndexes(queue.poll()).forEach(index -> {
                if (!visited[index]) {
                    visited[index] = true;
                    path.add(index);
                    queue.offer(index);
                }
            });
        }
        return path;
    }

    @Override
    public boolean isDirectedGraph() {
        return graphKind == GraphKind.DG || graphKind == GraphKind.DN;
    }

    @Override
    public boolean isCompletedGraph() {
        if ((isDirectedGraph() && edgeNum == vertexNum * (vertexNum - 1)) || (edgeNum == vertexNum * (vertexNum - 1) / 2)) {
            for (int i = 0; i < vertexNum; i++)
                if (adjacencyMatrix.get(i).get(i) != null)
                    return false;
            return true;
        }
        return false;
    }

    /**
     * 无向图中所有顶点之间均可达;
     * 有向图中所有顶点之间都有路径
     * (该图只有一个联通分量)
     *
     * @return true表示该图是连通图
     */
    @Override
    public boolean isConnectedGraph() {
        if (edgeNum == 0) {
            return false;
        }
        visited = new boolean[vertexNum];
        traversableNum = 0;
        return isConnectedGraphByDFS(0) == vertexNum;
    }

    @Override
    public boolean isEmptyGraph() {
        return vertexNum == 0;
    }

    private int isConnectedGraphByDFS(int v) {
        visited[v] = true;
        ++traversableNum;
        getOutAdjacentVertexIndexes(v).forEach(index -> {
            if (!visited[index])
                isConnectedGraphByDFS(index);
        });
        return traversableNum;
    }

    @Override
    public boolean isNetwork() {
        return graphKind == GraphKind.DN || graphKind == GraphKind.UDN;
    }

    @Override
    public Object[] getVertexes() {
        return vertexes.toArray();
    }

    @Override
    public Set<Edge<T, V>> getEdges() {
        Set<Edge<T, V>> edges = new HashSet<>();
        for (int i = 0; i < vertexNum; i++)
            for (int j = i; j < vertexNum; j++) {
                Edge<T, V> edge = adjacencyMatrix.get(i).get(j);
                if (edge != null)
                    edges.add(edge);
            }
        if (isDirectedGraph()) {
            for (int i = 0; i < vertexNum; i++)
                for (int j = 0; j < i; j++) {
                    Edge<T, V> edge = adjacencyMatrix.get(i).get(j);
                    if (edge != null)
                        edges.add(edge);
                }

        }
        return edges;
    }

    /**
     * 单源路径问题,在有向图中具有有方向性,
     *
     * @param index1 顶点1索引值
     * @param index2 顶点2索引值
     * @return 路径经过的顶点索引值的集合
     */
    @Override
    public List<Integer> getFirstPath(int index1, int index2) {
        rangeCheck(index1);
        rangeCheck(index2);
        LinkedList<Integer> path = new LinkedList<>();
        if (edgeNum == 0)
            return path;
        if (index1 == index2) {
            if (adjacencyMatrix.get(index1).get(index2) != null) {
                path.add(index1);
                path.add(index2);
            }
            return path;
        }
        visited = new boolean[vertexNum];
        getFirstPathByDFS(path, index1, index2);
        return path;
    }

    private boolean getFirstPathByDFS(LinkedList<Integer> path, int v, int index2) {
        visited[v] = true;
        path.offerLast(v);
        if (v == index2)
            return true;
        for (Integer index : getOutAdjacentVertexIndexes(v)) {
            if (!visited[index]) {
                if (getFirstPathByDFS(path, index, index2))
                    return true;
            }
        }
        path.pollLast();
        return false;
    }

    @Override
    public List<List<Integer>> getPaths(int index1, int index2) {
        rangeCheck(index1);
        rangeCheck(index2);
        paths = new ArrayList<>();
        if (edgeNum == 0)
            return paths;
        if (index1 == index2)
            if (adjacencyMatrix.get(index1).get(index2) != null)
                paths.add(Stream.of(index1, index2).collect(Collectors.toList()));
        visited = new boolean[vertexNum];
        getPathsByDFS(new LinkedList<>(), index2, index1, index1);
        return paths;
    }


    @SuppressWarnings("unchecked")
    private void getPathsByDFS(LinkedList<Integer> path, int index2, int v, int pre) {
        visited[v] = true;
        path.offerLast(v);
        if (v == index2 && pre != index2)
            paths.add((List<Integer>) path.clone());
        for (Integer index : getOutAdjacentVertexIndexes(v)) {
            if (index == pre)
                continue;
            if (!visited[index])
                getPathsByDFS(path, index2, index, v);
        }
        path.pollLast();
        visited[v] = false;
    }


    private boolean hasPathByDFS(int v, int index2) {
        visited[v] = true;
        if (v == index2)
            return true;
        for (Integer index : getOutAdjacentVertexIndexes(v))
            if (!visited[index]) {
                if (hasPathByDFS(index, index2))
                    return true;
            }

        return false;
    }

    /**
     * 在有向图中该方法具有方向性
     *
     * @param index1 索引值1
     * @param index2 索引值2
     * @return true表示两点之间存在路径
     */
    @Override
    public boolean hasPath(int index1, int index2) {
        rangeCheck(index1);
        rangeCheck(index2);
        if (index1 == index2)
            if (adjacencyMatrix.get(index1).get(index2) != null)
                return true;
        visited = new boolean[vertexNum];
        return hasPathByDFS(index1, index2);
    }

    /**
     * 这是我写的最后一个方法,不想优化了,写吐了,就这样吧。。。
     */
    @Override
    public List<Integer> getFirstCycle(int index) {
        List<List<Integer>> cycles = getCycles(index);
        if (cycles.size() > 0) {
            return cycles.get(0);
        }
        return new ArrayList<>();
    }

    /**
     * 在有向图中具有方向性
     *
     * @param index 顶点索引值
     * @return true表示该顶点存在回路/环
     */
    @Override
    public boolean hasCycle(int index) {
        if (edgeNum == 0)
            return false;
        if (hasLoop(index))
            return true;
        visited = new boolean[vertexNum];
        return hasCycleByDFS(index, index, index);
    }

    private boolean hasCycleByDFS(int v, int pre) {
        visited[v] = true;
        for (Integer index : getOutAdjacentVertexIndexes(v)) {
            if (index == pre)
                continue;
            if (visited[index] || adjacencyMatrix.get(index).get(index) != null)
                return true;
            if (hasCycleByDFS(index, v))
                return true;
        }
        return false;
    }

    private boolean hasCycleByDFS(int root, int v, int pre) {
        visited[v] = true;
        for (Integer index : getOutAdjacentVertexIndexes(v)) {
            if (index == pre)
                continue;
            if (visited[index] && index == root)
                return true;
            if (hasCycleByDFS(root, index, v))
                return true;
        }
        return false;
    }

    /**
     * 在有向图中具有方向性
     *
     * @return true表示该图存在环
     */
    @Override
    public boolean hasCycle() {
        if (edgeNum == 0)
            return false;
        visited = new boolean[vertexNum];
        return hasCycleByDFS(0, 0);
    }

    @Override
    public List<List<Integer>> getCycles(int index) {
        rangeCheck(index);
        cycles = new ArrayList<>();
        if (edgeNum == 0)
            return cycles;
        visited = new boolean[vertexNum];
        getCyclesByDFS(new LinkedList<>(), index, index, index);
        Edge<T, V> edge = adjacencyMatrix.get(index).get(index);
        if (edge != null)
            cycles.add(Stream.of(index).collect(Collectors.toList()));
        return cycles;
    }

    @Override
    public List<List<Integer>> getCycles() {
        cycles = new ArrayList<>();
        if (edgeNum == 0)
            return cycles;
        visited = new boolean[vertexNum];
        for (int i = 0; i < vertexNum; i++) {
            getCyclesByDFS(new LinkedList<>(), i, i, i);
            Edge<T, V> edge = adjacencyMatrix.get(i).get(i);
            if (edge != null)
                cycles.add(Stream.of(i).collect(Collectors.toList()));
        }
        return cycles;
    }


    @SuppressWarnings("unchecked")
    private void getCyclesByDFS(LinkedList<Integer> cycle, int root, int v, int pre) {
        visited[v] = true;
        cycle.offerLast(v);
        for (Integer index : getOutAdjacentVertexIndexes(v)) {
            if (index == pre)
                continue;
            if (visited[index]) {
                if (index == root)
                    cycles.add((List<Integer>) cycle.clone());
                continue;
            }
            getCyclesByDFS(cycle, root, index, v);
        }
        cycle.pollLast();
        visited[v] = false;
    }

    @Override
    public Edge<T, V> getLoop(int index) {
        rangeCheck(index);
        return adjacencyMatrix.get(index).get(index);
    }

    @Override
    public boolean hasLoop(int index) {
        return getLoop(index) != null;
    }

    @Override
    public boolean hasLoop() {
        for (int i = 0; i < vertexNum; i++)
            if (adjacencyMatrix.get(i).get(i) != null)
                return true;
        return false;
    }

    private void isConnectedByDFS(int[] visited, int v, int flag) {
        visited[v] = flag;
        getOutAdjacentVertexIndexes(v).forEach(index -> {
            if (visited[index] == 0)
                isConnectedByDFS(visited, index, flag);
        });
    }


    /**
     * 判断索引值对应的顶点是否连通
     * index1==index2:检查索引值是否有自环边
     * 无环图中无方向性
     * 有环图中具有方向性
     *
     * @param index1 索引值1
     * @param index2 索引值2
     * @return true表示两点连通
     */
    @Override
    public boolean isConnected(int index1, int index2) {
        rangeCheck(index1);
        rangeCheck(index2);
        if (index1 == index2)
            return adjacencyMatrix.get(index1).get(index1) != null;
        int[] visited = new int[vertexNum];
        for (int i = index1, flag = 1; i < vertexNum; i++)
            if (visited[i] == 0) {
                isConnectedByDFS(visited, i, flag);
                flag++;
            }
        return visited[index1] == visited[index2];
    }
}

测试demo:

package graph.graphImpl;

import graph.GraphKind;

import java.util.stream.Collectors;


public class test {
    public static void main(String[] args) {
        GraphByAdjacentMatrix<String, String, String> graph = new GraphByAdjacentMatrix<>(GraphKind.DG);
        for (int i = 1; i < 10; i++) {
            graph.addVertex("V" + i);
        }
        graph.addEdgeByIndex(0, 1);
        graph.addEdgeByIndex(0, 2);
        graph.addEdgeByIndex(1, 3);
        graph.addEdgeByIndex(1, 4);
        graph.addEdgeByIndex(1, 8);
        graph.addEdgeByIndex(2, 7);
        graph.addEdgeByIndex(5, 2);
        graph.addEdgeByIndex(5, 7);
        graph.addEdgeByIndex(6, 3);
        graph.addEdgeByIndex(6, 8);
        System.out.println(graph);
        graph.BFSTraverse().forEach(path -> {
            System.out.println(path.stream().map(graph::getVertex).collect(Collectors.toList()));
        });

    }
}

测试结果:

热门文章

暂无图片
编程学习 ·

那些年让我们目瞪口呆的bug

程序员一生与bug奋战&#xff0c;可谓是杀敌无数&#xff0c;见怪不怪了&#xff01;在某知识社交平台中&#xff0c;一个“有哪些让程序员目瞪口呆的bug”的话题引来了6700多万的阅读&#xff0c;可见程序员们对一个话题的敏感度有多高。 1、麻省理工“只能发500英里的邮件” …
暂无图片
编程学习 ·

redis的下载与安装

下载redis wget http://download.redis.io/releases/redis-5.0.0.tar.gz解压redis tar -zxvf redis-5.0.0.tar.gz编译 make安装 make install快链方便进入redis ln -s redis-5.0.0 redis
暂无图片
编程学习 ·

《大话数据结构》第三章学习笔记--线性表(一)

线性表的定义 线性表&#xff1a;零个或多个数据元素的有限序列。 线性表元素的个数n定义为线性表的长度。n为0时&#xff0c;为空表。 在比较复杂的线性表中&#xff0c;一个数据元素可以由若干个数据项组成。 线性表的存储结构 顺序存储结构 可以用C语言中的一维数组来…
暂无图片
编程学习 ·

对象的扩展

文章目录对象的扩展属性的简洁表示法属性名表达式方法的name属性属性的可枚举性和遍历可枚举性属性的遍历super关键字对象的扩展运算符解构赋值扩展运算符AggregateError错误对象对象的扩展 属性的简洁表示法 const foo bar; const baz {foo}; baz // {foo: "bar"…
暂无图片
编程学习 ·

让程序员最头疼的5种编程语言

世界上的编程语言&#xff0c;按照其应用领域&#xff0c;可以粗略地分成三类。 有的语言是多面手&#xff0c;在很多不同的领域都能派上用场。大家学过的编程语言很多都属于这一类&#xff0c;比如说 C&#xff0c;Java&#xff0c; Python。 有的语言专注于某一特定的领域&…
暂无图片
编程学习 ·

写论文注意事项

参考链接 给研究生修改了一篇论文后&#xff0c;该985博导几近崩溃…… 重点分析 摘要与结论几乎重合 这一条是我见过研究生论文中最常出现的事情&#xff0c;很多情况下&#xff0c;他们论文中摘要部分与结论部分重复率超过70%。对于摘要而言&#xff0c;首先要用一小句话引…
暂无图片
编程学习 ·

安卓 串口开发

上图&#xff1a; 上码&#xff1a; 在APP grable添加 // 串口 需要配合在项目build.gradle中的repositories添加 maven {url "https://jitpack.io" }implementation com.github.licheedev.Android-SerialPort-API:serialport:1.0.1implementation com.jakewhart…
暂无图片
编程学习 ·

2021-2027年中国铪市场调研与发展趋势分析报告

2021-2027年中国铪市场调研与发展趋势分析报告 本报告研究中国市场铪的生产、消费及进出口情况&#xff0c;重点关注在中国市场扮演重要角色的全球及本土铪生产商&#xff0c;呈现这些厂商在中国市场的铪销量、收入、价格、毛利率、市场份额等关键指标。此外&#xff0c;针对…
暂无图片
编程学习 ·

Aggressive cows题目翻译

描述&#xff1a; Farmer John has built a new long barn, with N (2 < N < 100,000) stalls.&#xff08;John农民已经新建了一个长畜棚带有N&#xff08;2<N<100000&#xff09;个牛棚&#xff09; The stalls are located along a straight line at positions…
暂无图片
编程学习 ·

剖析组建PMO的6个大坑︱PMO深度实践

随着事业环境因素的不断纷繁演进&#xff0c;项目时代正在悄悄来临。设立项目经理转岗、要求PMP等项目管理证书已是基操&#xff0c;越来越多的组织开始组建PMO团队&#xff0c;大有曾经公司纷纷建造中台的气质&#xff08;当然两者的本质并不相同&#xff0c;只是说明这个趋势…
暂无图片
编程学习 ·

Flowable入门系列文章118 - 进程实例 07

1、获取流程实例的变量 GET运行时/进程实例/ {processInstanceId} /变量/ {变量名} 表1.获取流程实例的变量 - URL参数 参数需要值描述processInstanceId是串将流程实例的id添加到变量中。变量名是串要获取的变量的名称。 表2.获取流程实例的变量 - 响应代码 响应码描述200指…
暂无图片
编程学习 ·

微信每天自动给女[男]朋友发早安和土味情话

微信通知&#xff0c;每天给女朋友发早安、情话、诗句、天气信息等~ 前言 之前逛GitHub的时候发现了一个自动签到的小工具&#xff0c;b站、掘金等都可以&#xff0c;我看了下源码发现也是很简洁&#xff0c;也尝试用了一下&#xff0c;配置也都很简单&#xff0c;主要是他有一…
暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

项目经理,你有什么优势吗?

大侠被一个问题问住了&#xff1a;你和别人比&#xff0c;你的优势是什么呢? 大侠听到这个问题后&#xff0c;脱口而出道&#xff1a;“项目管理能力和经验啊。” 听者抬头看了一下大侠&#xff0c;显然听者对大侠的这个回答不是很满意&#xff0c;但也没有继续追问。 大侠回家…
暂无图片
编程学习 ·

nginx的负载均衡和故障转移

#注&#xff1a;proxy_temp_path和proxy_cache_path指定的路径必须在同一分区 proxy_temp_path /data0/proxy_temp_dir; #设置Web缓存区名称为cache_one&#xff0c;内存缓存空间大小为200MB&#xff0c;1天没有被访问的内容自动清除&#xff0c;硬盘缓存空间大小为30GB。 pro…
暂无图片
编程学习 ·

业务逻辑漏洞

身份认证安全 绕过身份认证的几种方法 暴力破解 测试方法∶在没有验证码限制或者一次验证码可以多次使用的地方&#xff0c;可以分为以下几种情况︰ (1)爆破用户名。当输入的用户名不存在时&#xff0c;会显示请输入正确用户名&#xff0c;或者用户名不存在 (2)已知用户名。…