小工具知识网

当前位置: 首页 > 行业知识 > 【数据结构与算法】图论及其相关算法

行业知识

【数据结构与算法】图论及其相关算法

2026-11-19 18:13:43 来源:互联网转载

文章目录

  • 图的基本介绍
  • 图的表示方式
    • 邻接矩阵
    • 邻接表
    • 图的深度优先遍历(DFS)
      • 概述
      • 实现步骤
      • 代码实现
      • 图的广度优先遍历(BFS)
        • 概述
        • 实现步骤
        • 代码实现
        • 图的常用代码汇总
        • 最小生成树算法
          • 普里姆(Prim)算法
            • 算法实践
            • 克鲁斯卡尔(Kruskal)算法
              • 并查集
              • 算法实践
              • 最短路径算法
                • 迪杰斯特拉(Dijkstra)算法
                  • 算法实践
                  • 弗洛伊德(Floyd)算法
                    • ���法实践

                      图的基本介绍

                      线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。

                      图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图:

                      简单来说,图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为:G(V,E),其中,G 表示一个图,V 表示顶点的集合,E 表示边的集合。

                      然后我们说说图中的一些常见概念:

                      1. 节点(Vertex):图中的基本元素,用于表示某个实体。

                      2. 边(Edge):连接两个节点的线段,用于表示节点之间的关系。

                      3. 度(Degree):度表示一个顶点包含多少条边,在有向图中,还分为出度和入度,出度表示从该顶点出去的边的条数,入度表示进入该顶点的边的条数。

                      4. 有向图和无向图:边是否有方向决定图是有向图还是无向图。有向边指明了边的起点和终点,无向边的两个节点没有起点和终点之分。

                      5. 带权图和无权图:边是否有权值决定图是带权图还是无权图。带权边有一个数值,表示边的权重,无权边的权重视为1。

                      6. 路径:图中一系列顶点之间的边的序列叫做路径。

                      7. 连通性:如果任何两个节点之间都存在路径,那么该图是连通的。否则是非连通图。

                      8. 海量图:节点和边的数量巨大,远远超出计算机内存大小,需要特殊的算法和存储结构才能处理的图。

                      图的表示方式

                      图的表示方式有两种:

                      • 二维数组表示(邻接矩阵)
                      • 链表表示(邻接表)

                        邻接矩阵

                        邻接矩阵是图的一种存储结构,它使用一个二维数组来表示图中节点之间的边。

                        具体来说:

                        1. 邻接矩阵的行数和列数都是图中的节点数n。
                        2. 矩阵中的每个元素都代表一条边。如果节点i和节点j之间有边,则矩阵的第i行第j列元素为1,否则为0。
                        3. 对于带权图,矩阵的元素为对应的权值,而不是1。
                        4. 矩阵的主对角线上的元素都是0,因为节点不会和自身相连。
                        5. 邻接矩阵适用于表示稠密图,空间复杂度为O(n2)。如果图是稀疏的,空间利用率比较低。

                        邻接矩阵的优点是:

                        1. 可以在O(1)时间内判断任意两节点之间是否有边。
                        2. 方便实现一些算法,如广度优先搜索、深度优先搜索等。

                        邻接矩阵的缺点是:

                        1. 空间复杂度高,如果图是稀疏的会造成空间浪费。
                        2. 难以表示动态图,如果频繁添加和删除边,需要频繁重建邻接矩阵。

                        邻接表

                        邻接表是图的另一种存储结构,它使用链表来存储每个节点的相邻节点。

                        具体来说:

                        1. 邻接表由数组和链表组成。数组的每个元素都是一个链表,表示对应节点的相邻节点列表。
                        2. 数组的索引就是节点的序号,数组大小为节点数n。
                        3. 如果节点i和节点j有边,则将j添加到i对应的链表中。
                        4. 对于带权图,每个节点在链表中的元素不再只存储相邻节点的序号,而是存储一个结构体,包含相邻节点序号和对应的权值。
                        5. 邻接表适用于稀疏图,空间复杂度为O(n+e),e是边数。对于稠密图,空间利用率会比较高。

                        邻接表的优点是:

                        6. 空间复杂度较低,适用于表示稀疏图。

                        7. 易于实现动态图的增加和删除操作。

                        邻接表的缺点是:

                        8. 难以在O(1)时间内判断任意两节点之间是否有边,需要遍历链表。

                        9. 不太方便实现一些算法,如广度优先搜索和深度优先搜索。

                        图的深度优先遍历(DFS)

                        所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:

                        • 深度优先遍历(DFS)
                        • 广度优先遍历(BFS)

                          概述

                          深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点。

                          可以这样理解: 每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。显然,深度优先搜索是一个递归的过程

                          总的来说:深度优先搜索(Depth-First Search)是一种图的遍历算法。它从某个节点出发,尽可能深地搜索下去,直到遍历完当前路径上所有节点。然后回溯,继续尽可能深地搜索下一条路径。

                          深度优先搜索的主要应用是图的连通性检查,拓扑排序,求解切分数以及求解二分图的最大匹配数等。

                          实现步骤

                          深度优先搜索的过程可以用递归实现。主要步骤如下:

                          1. 从目标图的某个节点v出发,访问该节点。
                          2. 如果v的相邻节点w未被访问,则递归访问w。
                          3. 如果w已被访问,则回到v节点,转而访问v的另一个未访问相邻节点。
                          4. 如果v的所有相邻节点都已被访问,则回溯到v的上一个节点。
                          5. 重复步骤3和4,直到所有节点被访问。

                          既然是使用递归,那么我们肯定也可以使用栈的思路去理解:

                          代码实现

                          public class Graph {//存储顶点集合private ArrayList vertexList; //存储图对应的邻结矩阵private int[][] edges;  //表示边的数目private int numOfEdges;//定义给数组 boolean[], 记录某个结点是否被访问private boolean[] isVisited;    //dfs部分    public void dfs(){        //初始化访问数组        isVisited = new boolean[vertexList.size()];        for (int i = 0;i  ");        //设置当前节点已被访问        isVisited[index] = true;        //找出该节点的第一个邻接点        int firstNeighbor = getFirstNeighbor(index);        //说明存在第一个临界点        if (firstNeighbor != -1) {            dfs(firstNeighbor);        }    }    /**     * 找到index节点的第一个临界点,如果没有返回-1     * @param index     * @return     */    public int getFirstNeighbor(int index) {        for (int i = 0; i "A" 1->"B" 2->"C"public String getValueByIndex(int i) {return vertexList.get(i);}}

                          注意:

                          • 我们getFirstNeighbor方法中,这里的j一定是从0开始的,有的人容易弄成index+1开始,这是没有考虑到不从A开始遍历的情况。
                          • 之所以要遍历我们的节点列表,是因为可能是非连通图,从一个节点开始遍历可能不会把整个图的节点都遍历到

                            图的广度优先遍历(BFS)

                            概述

                            广度优先搜索(Breadth-First Search)是一种图的遍历算法。它从某个节点出发,首先访问该节点相邻的所有节点,然后访问相邻节点的相邻节点,以此类推,直到遍历完所有节点为止。

                            广度优先搜索就像水面上的波纹一样一层一层向外扩展:

                            与深度优先搜索相比,广度优先搜索的特点是:

                            1. 会先访问离起点节点更近的节点。深度优先搜索会尽可能深的搜索,可能离起点更远。
                            2. 使用队列实现,空间复杂度较高。深度优先搜索使用递归栈,空间复杂度较低。

                            广度优先搜索主要用于图的最短路径问题,拓扑排序等。

                            实现步骤

                            广度优先搜索的过程可以用队列实现。主要步骤如下:

                            1. 从图的某个节点v出发,访问该节点并将其入队。
                            2. 取出队首节点,访问该节点的所有未访问相邻节点,并将相邻节点入队。
                            3. 重复步骤2,直到队列为空。
                            4. 如果图中还有未访问节点,则以其中一个未访问节点为起点,重复步骤1~3。

                            代码实现

                            public class Graph {//存储顶点集合private ArrayList vertexList; //存储图对应的邻结矩阵private int[][] edges;  //表示边的数目private int numOfEdges;//定义给数组 boolean[], 记录某个结点是否被访问private boolean[] isVisited;    /**     * 在bfs中负责找到指定节点的所有未遍历节点     * @param index     */    public void getNeighbors(int index, Queue queue){        for (int i = 0; i  ");        }    }//返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"public String getValueByIndex(int i) {return vertexList.get(i);}//返回结点的个数public int getNumOfVertex() {return vertexList.size();}}

                            图的常用代码汇总

                            public class Graph {private ArrayList vertexList; //存储顶点集合private int[][] edges; //存储图对应的邻结矩阵private int numOfEdges; //表示边的数目private boolean[] isVisited; //记录某个结点是否被访问public static void main(String[] args) {//测试一把图是否创建okint n = 8;  //结点的个数//String Vertexs[] = {"A", "B", "C", "D", "E"};String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};//创建图对象Graph graph = new Graph(n);//循环的添加顶点for(String vertex: Vertexs) {graph.insertVertex(vertex);}//添加边//A-B A-C B-C B-D B-E //graph.insertEdge(0, 1, 1); // A-B//graph.insertEdge(0, 2, 1); // //graph.insertEdge(1, 2, 1); // //graph.insertEdge(1, 3, 1); // //graph.insertEdge(1, 4, 1); // //更新边的关系graph.insertEdge(0, 1, 1);graph.insertEdge(0, 2, 1);graph.insertEdge(1, 3, 1);graph.insertEdge(1, 4, 1);graph.insertEdge(3, 7, 1);graph.insertEdge(4, 7, 1);graph.insertEdge(2, 5, 1);graph.insertEdge(2, 6, 1);graph.insertEdge(5, 6, 1);//显示一把邻结矩阵graph.showGraph();//测试一把,我们的dfs遍历是否okSystem.out.println("深度遍历");graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]//System.out.println();System.out.println("广度优先!");graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]}//构造器public Graph(int n) {//初始化矩阵和vertexListedges = new int[n][n];vertexList = new ArrayList(n);numOfEdges = 0;}//得到第一个邻接结点的下标 w /** *  * @param index  * @return 如果存在就返回对应的下标,否则返回-1 */public int getFirstNeighbor(int index) {for(int j = 0; j  0) {return j;}}return -1;}//根据前一个邻接结点的下标来获取下一个邻接结点public int getNextNeighbor(int v1, int v2) {for(int j = v2 + 1; j  0) {return j;}}return -1;}//深度优先遍历算法//i 第一次就是 0private void dfs(boolean[] isVisited, int i) {//首先我们访问该结点,输出System.out.print(getValueByIndex(i) + "->");//将结点设置为已经访问isVisited[i] = true;//查找结点i的第一个邻接结点wint w = getFirstNeighbor(i);while(w != -1) {//说明有if(!isVisited[w]) {dfs(isVisited, w);}//如果w结点已经被访问过w = getNextNeighbor(i, w);}}//对dfs 进行一个重载, 遍历我们所有的结点,并进行 dfspublic void dfs() {isVisited = new boolean[vertexList.size()];//遍历所有的结点,进行dfs[回溯]for(int i = 0; i ");//标记为已访问isVisited[i] = true;//将结点加入队列queue.addLast(i);while( !queue.isEmpty()) {//取出队列的头结点下标u = (Integer)queue.removeFirst();//得到第一个邻接结点的下标 w w = getFirstNeighbor(u);while(w != -1) {//找到//是否访问过if(!isVisited[w]) {System.out.print(getValueByIndex(w) + "=>");//标记已经访问isVisited[w] = true;//入队queue.addLast(w);}//以u为前驱点,找w后面的下一个邻结点w = getNextNeighbor(u, w); //体现出我们的广度优先}}} //遍历所有的结点,都进行广度优先搜索public void bfs() {isVisited = new boolean[vertexList.size()];for(int i = 0; i "A" 1->"B" 2->"C"public String getValueByIndex(int i) {return vertexList.get(i);}//返回v1和v2的权值public int getWeight(int v1, int v2) {return edges[v1][v2];}//插入结点public void insertVertex(String vertex) {vertexList.add(vertex);}//添加边/** *  * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1 * @param v2 第二个顶点对应的下标 * @param weight 表示  */public void insertEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}}

                            最小生成树算法

                            最小生成树是图论中的一个很重要的概念。它指的是连接图中所有节点的一棵树,且这棵树上的所有边的权值之和最小。

                            最小生成树有几个重要的性质:

                            1. 它包含图中所有节点,没有孤立点。
                            2. 它是一个树,没有环。
                            3. 它的权值之和最小。

                            常见的最小生成树算法有:

                            4. Prim算法:从一个节点开始,不断向生成树中添加新的节点和边,直到包含所有的节点。每次添加的新边是到树中节点的最短边。

                            5. Kruskal算法:按照边的权值从小到大选择边,只要这条边不形成环,就添加到最小生成树中。

                            6. Dijkstra算法:用Dijkstra最短路径算法求出每个节点到其它所有节点的最短路径,最小生成树由这些最短路径形成。

                            最小生成树有许多实际应用,比如网络的连通性、电路布线等。它为这些实际问题提供了一种效率较高的解决方案。

                            总之,最小生成树是图论中一个非常经典和重要的概念,相关算法也比较重要,值得好好理解和掌握。

                            最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示

                            普里姆(Prim)算法

                            Prim算法是最小生成树的经典算法之一。它的基本思想是:

                            • 从图中的任意一个节点开始,逐步添加边和节点,形成最小生成树。每次添加的新边必须连接的树中的节点和不在树中的节点,并且这条新边必须是所有候选边中权值最小的一条。

                              Prim算法的步骤如下:

                              1. 选择图中的任意一个节点作为起始节点,标记该节点已经被访问。
                              2. 找出所有已访问节点连通的还未访问的节点中,权值最小的一条边。该边连接的未访问节点标记为已访问。
                              3. 重复步骤2,直到所有节点都被访问为止。
                              4. 形成的边集合即为最小生成树。

                              或者可以参考,下面这个视频讲得非常的清楚:

                              算法图解:

                              Prim算法的时间复杂度为O(n2),如果使用优先队列实现,可以降低到O(nlogn)。

                              Prim算法仅适用于带权无向连通图,如果图是有向图或非连通图,Prim算法无法得到最小生成树。

                              算法实践

                              代码实现:

                              import java.util.*;public class PrimAlgorithm {    private static final int INF = Integer.MAX_VALUE;    public static int prim(int[][] graph) {        int n = graph.length;        //创建距离表,代表索引对应节点距离最小生成树的距离        int[] dist = new int[n];        //记录每个节点是否被添加,未添加记为false        boolean[] visited = new boolean[n];        //先将距离表都初始化为最大值        Arrays.fill(dist, INF);        //从0节点开始遍历,将距离更新一下        dist[0] = 0;        //记录要返回的最小权值        int res = 0;        for (int i = 0; i  

                              在这个实现中,我们首先初始化了距离数组dist和访问标记数组visited,并将距离数组的所有元素初始化为无穷大(表示尚未访问到的节点)。

                              然后,我们从节点0开始遍历所有节点,每次选取距离数组中最小的值作为下一个要访问的节点。然后,我们将这个节点标记为已访问,并将其与尚未访问的节点的距离更新到距离数组中。最后,我们将所有边的权值之和作为最小生成树的权值返回。

                              这个实现的时间复杂度为O(n^2),其中n是节点数。

                              克鲁斯卡尔(Kruskal)算法

                              Kruskal算法是最小生成树的另一种经典算法。它的基本思想是:

                              将图中的所有边按权值从小到大排序。选取权值最小的边,只要该边不形成环,就将其添加到最小生成树中。重复该步骤,直到最小生成树包含了图中所有节点。

                              Kruskal算法的步骤如下:

                              1. 对图中的所有边按权值从小到大进行排序。
                              2. 选取权值最小的边,判断是否形成环。如果不形成环,就添加到最小生成树中。
                              3. 重复步骤2,直到最小生成树包含了图中的所有顶点。
                              4. 输出最小生成树。

                              Kruskal算法的时间复杂度为O(ElogE),其中E是图中的边数。

                              Kruskal算法的实现需要使用到并查集,来判断选取的边是否会形成环。并查集可以在O(1)时间内判断两个元素是否属于同一集合,这是实现Kruskal算法的关键。

                              与Prim算法相比,Kruskal算法适用于边数较多的稀疏图,因为其时间复杂度不依赖于节点数,仅与边数相关。但Kruskal算法需要提前对所有边进行排序,增加了空间复杂度。

                              图解:

                              并查集

                              并查集是一种树型的数据结构,用于处理一些不交集合的合并及查询问题。

                              它支持三种操作:

                              1. 初始化init
                              2. union(x, y):合并元素x和元素y所在的集合。
                              3. find(x):找到元素x所在的集合代表,该集合代表是该集合中最早加入的元素。

                              并查集实现了一种动态连通性,在初始时,每个元素自成一个集合,通过union操作不断合并集合,最后形成几个不相交的大集合。

                              并查集的典型应用是解决图论中的离线查询问题,比如在一个无向图中查询两个节点是否处于同一个连通图中。

                              并查集实现有两种常见方式:

                              1. 快速查找:使用树结构,find操作需要遍历到根节点,时间复杂度为O(n)。
                              2. 带路径压缩的快速合并:在find操作的遍历过程中,将节点直接指向根节点,实现路径压缩,降低树的深度。平衡之后,时间复杂度可以达到O(1)。

                              算法实践

                              import java.util.*;public class KruskalAlgorithm {    private static class Edge implements Comparable {        int u, v, w;        public Edge(int u, int v, int w) {            this.u = u;            this.v = v;            this.w = w;        }        @Override        public int compareTo(Edge o) {            return Integer.compare(this.w, o.w);        }    }    public static int kruskal(int[][] graph) {        int n = graph.length;        List edges = new ArrayList();        for (int u = 0; u  

                              在这个实现中,我们首先将图中所有边存储在一个列表中,并按照权值从小到大进行排序。然后,我们初始化一个并查集,将每个节点的父节点初始化为它本身。

                              接下来,我们遍历排序后的边列表,对于每条边,如果它的两个端点不在同一个连通块中,就将它们合并到同一个连通块中,并将这条边的权值加入最小生成树的权值中。

                              这个实现的时间复杂度为O(m log m),其中m是边数。

                              最短路径算法

                              图论最短距离(Shortest Path)算法动画演示-Dijkstra(迪杰斯特拉)和Floyd(弗洛伊德)

                              迪杰斯特拉(Dijkstra)算法

                              迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

                              Dijkstra算法是一种求解单源最短路径的算法。它的基本思想是:

                              1. 选定一个节点作为起始节点,计算从起始节点到其它节点的最短路径。
                              2. 遍历起始节点可达的所有节点,更新最短路径。选择下一节点继续遍历,直到遍历完所有节点。
                              3. 循环以上步骤,直到最后获得从起始节点到所有节点的最短路径。

                              Dijkstra算法的步骤如下:

                              1. 选定起始节点source,并将其距离设为0,其它节点距离设为无穷大。
                              2. 找出不在S集合且距离最小的节点u,其距离为dist[u]。
                              3. 将u加入S集合,表示u已经被访问。
                              4. 以u为中间节点,更新与其相邻的节点v的距离。dist[v] = min(dist[v], dist[u] + weight(u, v))。
                              5. 重复步骤2、3和4,直到S包含全部节点。
                              6. 输出各节点最短路径和距离。

                              Dijkstra算法使用一个数组dist记录各节点最短路径长度,使用小根堆优先队列找出距离最小的节点。时空复杂度分别为O(nlogn)和O(n)。

                              算法实践

                              import java.util.*;public class DijkstraAlgorithm {    private static final int INF = Integer.MAX_VALUE;    public static int[] dijkstra(int[][] graph, int start) {        int n = graph.length;        int[] dist = new int[n];        boolean[] visited = new boolean[n];        Arrays.fill(dist, INF);        dist[start] = 0;        for (int i = 0; i  

                              在这个实现中,我们首先初始化距离数组dist和访问标记数组visited,并将距离数组的所有元素初始化为无穷大(表示尚未访问到的节点)。然后,我们从起点开始遍历所有节点,每次选取距离数组中最小的值作为下一个要访问的节点。然后,我们将这个节点标记为已访问,并将其与尚未访问的节点的距离更新到距离数组中。最后,我们返回距离数组。

                              这个实现的时间复杂度为O(n^2),其中n是节点数。如果使用优先队列来优化,时间复杂度可以降为O(m log n),其中m是边数。

                              弗洛伊德(Floyd)算法

                              Floyd算法是一种求解所有节点对之间最短路径的算法。它的基本思想是:

                              通过递推的方式,求出从各个节点到其它所有节点的最短路径。

                              Floyd算法的步骤如下:

                              1. 初始化dist数组,dist[i][j]表示节点i到节点j的最短路径长度。当i==j时,dist[i][j] = 0;当节点i和节点j之间有直接路径时,dist[i][j]为该路径长度;否则 dist[i][j] = ∞。
                              2. 遍历每个中间节点k,更新dist数组:

                                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

                                这意味着节点i到节点j的最短路径可能通过节点k。

                              3. 重复步骤2,直到遍历完所有的中间节点。
                              4. dist数组最后的结果即为各个节点对之间的最短路径长度。

                              Floyd算法的时间复杂度和空间复杂度均为O(n3),n为节点个数。

                              Floyd算法适用于求解任意两个节点之间的最短路径,可以解决有向图和带权图最短路径问题。

                              Dijkstra算法和Floyd算法都是用于求解最短路径问题的经典算法,但二者有以下几个主要区别:

                              1. 适用图的类型:
                                • Dijkstra算法只能用于求有向图或无向图的单源最短路径,不能求任意两点之间的最短路径。
                                • Floyd算法可以用于求有向图或无向图任意两点之间的最短路径。
                                • 最短路径类型:
                                  • Dijkstra算法求出一棵最短路径树,只能得到单源点到其他点的最短路径。
                                  • Floyd算法一次求出全部节点之间的最短路径,得到一个最短路径矩阵。
                                  • 时间复杂度:
                                    • Dijkstra算法使用优先队列实现,时间复杂度为O(nlogn)。
                                    • Floyd算法的时间复杂度为O(n3)。
                                    • 当图的节点数很多但边数较少时,Dijkstra算法效率更高。当图的节点数和边数都很大时,Floyd算法更高效。
                                    • 空间复杂度:
                                      • Dijkstra算法只需要O(n)的空间。
                                      • Floyd算法需要O(n2)的空间来存储最短路径矩阵。
                                      • 是否需要中间节点:
                                        • Dijkstra算法在更新最短路径时只考虑起点到终点的最短路径,不需要中间节点信息。
                                        • Floyd算法在更新最短路径时需要中间节点信息,通过中间节点跳转才能更新最短路径。

                              算法实践

                              import java.util.*;public class FloydAlgorithm {    private static final int INF = Integer.MAX_VALUE;    public static int[][] floyd(int[][] graph) {        int n = graph.length;        int[][] dist = new int[n][n];        for (int i = 0; i  

                              在这个实现中,我们首先将图中的邻接矩阵复制到距离矩阵中。然后,我们遍历所有节点对(i,j),尝试通过节点k来缩短(i,j)之间的距离。如果经过节点k可以缩短距离,则更新距离矩阵中的(i,j)元素。

                              这个实现的时间复杂度为O(n^3),其中n是节点数。

上一篇:海通证券怎么连接服务器?

下一篇:防火墙配置详解,安全设置一步到位,保障网络安全!