图的邻接矩阵表示法(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()));
        });

    }
}

测试结果:

热门文章

暂无图片
编程学习 ·

Java输出数组的内容

Java输出数组的内容_一万个小时-CSDN博客_java打印数组内容1. 输出内容最常见的方式// List<String>类型的列表List<String> list new ArrayList<String>();list.add("First");list.add("Second");list.add("Third");list.ad…
暂无图片
编程学习 ·

母螳螂的“魅惑之术”

在它们对大蝗虫发起进攻的时候&#xff0c;我认认真真地观察了一次&#xff0c;因为它们突然像触电一样浑身痉挛起来&#xff0c;警觉地面对限前这个大家伙&#xff0c;然后放下自己优雅的身段和祈祷的双手&#xff0c;摆出了一个可怕的姿势。我被眼前的一幕吓到了&#xff0c;…
暂无图片
编程学习 ·

疯狂填词 mad_libs 第9章9.9.2

#win7 python3.7.0 import os,reos.chdir(d:\documents\program_language) file1open(.\疯狂填词_d9z9d2_r.txt) file2open(.\疯狂填词_d9z9d2_w.txt,w) words[ADJECTIVE,NOUN,VERB,NOUN] str1file1.read()#方法1 for word in words :word_replaceinput(fEnter a {word} :)str1…
暂无图片
编程学习 ·

HBASE 高可用

为了保证HBASE是高可用的,所依赖的HDFS和zookeeper也要是高可用的. 通过参数hbase.rootdir指定了连接到Hadoop的地址,mycluster表示为Hadoop的集群. HBASE本身的高可用很简单,只要在一个健康的集群其他节点通过命令 hbase-daemon.sh start master启动一个Hmaster进程,这个Hmast…
暂无图片
编程学习 ·

js事件操作语法

一、事件的绑定语法 语法形式1 事件监听 标签对象.addEventListener(click,function(){}); 语法形式2 on语法绑定 标签对象.onclick function(){} on语法是通过 等于赋值绑定的事件处理函数 , 等于赋值本质上执行的是覆盖赋值,后赋值的数据会覆盖之前存储的数据,也就是on…
暂无图片
编程学习 ·

Photoshop插件--晕影动态--选区--脚本开发--PS插件

文章目录1.插件界面2.关键代码2.1 选区2.2 动态晕影3.作者寄语PS是一款栅格图像编辑软件&#xff0c;具有许多强大的功能&#xff0c;本文演示如何通过脚本实现晕影动态和选区相关功能&#xff0c;展示从互联网收集而来的一个小插件&#xff0c;供大家学习交流&#xff0c;请勿…
暂无图片
编程学习 ·

vs LNK1104 无法打开文件“xxx.obj”

写在前面&#xff1a; 向大家推荐两本新书&#xff0c;《深度学习计算机视觉实战》和《学习OpenCV4&#xff1a;基于Python的算法实战》。 《深度学习计算机视觉实战》讲了计算机视觉理论基础&#xff0c;讲了案例项目&#xff0c;讲了模型部署&#xff0c;这些项目学会之后可以…
暂无图片
编程学习 ·

工业元宇宙的定义与实施路线图

工业元宇宙的定义与实施路线图 李正海 1 工业元宇宙 给大家做一个关于工业元宇宙的定义。对于工业&#xff0c;从设计的角度来讲&#xff0c;现在的设计人员已经做到了普遍的三维设计&#xff0c;但是进入元宇宙时代&#xff0c;就不仅仅只是三维设计了&#xff0c;我们的目…
暂无图片
编程学习 ·

【leectode 2022.1.15】完成一半题目

有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目&#xff0c;整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。 若每位扣友选择不同的一题&#xff0c;请返回被选的 N 道题目至少包含多少种知识点类型。 示例 1&#xff1a…
暂无图片
编程学习 ·

js 面试题总结

一、js原型与原型链 1. prototype 每个函数都有一个prototype属性&#xff0c;被称为显示原型 2._ _proto_ _ 每个实例对象都会有_ _proto_ _属性,其被称为隐式原型 每一个实例对象的隐式原型_ _proto_ _属性指向自身构造函数的显式原型prototype 3. constructor 每个prot…
暂无图片
编程学习 ·

java练习代码

打印自定义行数的空心菱形练习代码如下 import java.util.Scanner; public class daYinLengXing{public static void main(String[] args) {System.out.println("请输入行数");Scanner myScanner new Scanner(System.in);int g myScanner.nextInt();int num g%2;//…
暂无图片
编程学习 ·

RocketMQ-什么是死信队列?怎么解决

目录 什么是死信队列 死信队列的特征 死信消息的处理 什么是死信队列 当一条消息初次消费失败&#xff0c;消息队列会自动进行消费重试&#xff1b;达到最大重试次数后&#xff0c;若消费依然失败&#xff0c;则表明消费者在正常情况下无法正确地消费该消息&#xff0c;此时…
暂无图片
编程学习 ·

项目 cg day04

第4章 lua、Canal实现广告缓存 学习目标 Lua介绍 Lua语法 输出、变量定义、数据类型、流程控制(if..)、循环操作、函数、表(数组)、模块OpenResty介绍(理解配置) 封装了Nginx&#xff0c;并且提供了Lua扩展&#xff0c;大大提升了Nginx对并发处理的能&#xff0c;10K-1000K Lu…
暂无图片
编程学习 ·

输出三角形

#include <stdio.h> int main() { int i,j; for(i0;i<5;i) { for(j0;j<i;j) { printf("*"); } printf("\n"); } }
暂无图片
编程学习 ·

stm32的BOOTLOADER学习1

序言 最近计划学习stm32的BOOTLOADER学习,把学习过程记录下来 因为现在网上STM32C8T6还是比较贵的,根据我的需求flash空间小一些也可以,所以我决定使用stm32c6t6.这个芯片的空间是32kb的。 #熟悉芯片内部的空间地址 1、flash ROM&#xff1a; 大小32KB&#xff0c;范围&#xf…
暂无图片
编程学习 ·

通过awk和shell来限制IP多次访问之学不会你打死我

学不会你打死我 今天我们用shell脚本&#xff0c;awk工具来分析日志来判断是否存在扫描器来进行破解网站密码——限制访问次数过多的IP地址&#xff0c;通过Iptables来进行限制。代码在末尾 首先我们要先查看日志的格式&#xff0c;分析出我们需要筛选的内容&#xff0c;日志…
暂无图片
编程学习 ·

Python - 如何像程序员一样思考

在为计算机编写程序之前&#xff0c;您必须学会如何像程序员一样思考。学习像程序员一样思考对任何学生都很有价值。以下步骤可帮助任何人学习编码并了解计算机科学的价值——即使他们不打算成为计算机科学家。 顾名思义&#xff0c;Python经常被想要学习编程的人用作第一语言…
暂无图片
编程学习 ·

蓝桥杯python-数字三角形

问题描述 虽然我前后用了三种做法&#xff0c;但是我发现只有“优化思路_1”可以通过蓝桥杯官网中的测评&#xff0c;但是如果用c/c的话&#xff0c;每个都通得过&#xff0c;足以可见python的效率之低&#xff08;但耐不住人家好用啊&#xff08;哭笑&#xff09;&#xff09…