第六章：图

第六章：图

概述

邻接矩阵

也就是说，邻接矩阵行列都表示顶点，第i行第j列表示i到j边的权值。

而关联矩阵的行表示顶点，列表示边，若某一列元素中有两个顶点值为1，则说明该边由这两行对应的顶点构成。

实现：

typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus; //顶点状态
typedef enum { UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD } EType; //边在遍历树中所属的类型

顶点的实现：

template <typename Tv> struct Vertex { //顶点对象（为简化起见，并未严格封装）
   Tv data; int inDegree, outDegree; VStatus status; //数据、出入度数、状态
   int dTime, fTime; //时间标签
   int parent; int priority; //在遍历树中的父节点、优先级数
   Vertex ( Tv const& d = ( Tv ) 0 ) : //构造新顶点
      data ( d ), inDegree ( 0 ), outDegree ( 0 ), status ( UNDISCOVERED ),
      dTime ( -1 ), fTime ( -1 ), parent ( -1 ), priority ( INT_MAX ) {} //暂不考虑权重溢出
};

边的实现：

template <typename Te> struct Edge { //边对象（为简化起见，并未严格封装）
   Te data; int weight; EType type; //数据、权重、类型
   Edge ( Te const& d, int w ) : data ( d ), weight ( w ), type ( UNDETERMINED ) {} //构造
};

邻接矩阵：

template <typename Tv, typename Te> //顶点类型、边类型
class GraphMatrix : public Graph<Tv, Te> { //基于向量，以邻接矩阵形式实现的图
private:
   Vector< Vertex< Tv > > V; //顶点集（向量）
   Vector< Vector< Edge< Te > * > > E; //边集（邻接矩阵）
public:
   GraphMatrix() { n = e = 0; } //构造
   ~GraphMatrix() { //析构
      for ( int j = 0; j < n; j++ ) //所有动态创建的
         for ( int k = 0; k < n; k++ ) //边记录
            delete E[j][k]; //逐条清除
   }
// 顶点的基本操作：查询第i个顶点（0 <= i < n）
   virtual Tv& vertex ( int i ) { return V[i].data; } //数据
   virtual int inDegree ( int i ) { return V[i].inDegree; } //入度
   virtual int outDegree ( int i ) { return V[i].outDegree; } //出度
   virtual int firstNbr ( int i ) { return nextNbr ( i, n ); } //首个邻接顶点
   virtual int nextNbr ( int i, int j ) //相对于顶点j的下一邻接顶点（改用邻接表可提高效率）
   { while ( ( -1 < j ) && ( !exists ( i, --j ) ) ); return j; } //逆向线性试探
   virtual VStatus& status ( int i ) { return V[i].status; } //状态
   virtual int& dTime ( int i ) { return V[i].dTime; } //时间标签dTime
   virtual int& fTime ( int i ) { return V[i].fTime; } //时间标签fTime
   virtual int& parent ( int i ) { return V[i].parent; } //在遍历树中的父亲
   virtual int& priority ( int i ) { return V[i].priority; } //在遍历树中的优先级数
// 顶点的动态操作
   virtual int insert ( Tv const& vertex ) { //插入顶点，返回编号
      for ( int j = 0; j < n; j++ ) E[j].insert ( NULL ); n++; //各顶点预留一条潜在的关联边
      E.insert ( Vector<Edge<Te>*> ( n, n, ( Edge<Te>* ) NULL ) ); //创建新顶点对应的边向量
      return V.insert ( Vertex<Tv> ( vertex ) ); //顶点向量增加一个顶点
   }
   virtual Tv remove ( int i ) { //删除第i个顶点及其关联边（0 <= i < n）
      for ( int j = 0; j < n; j++ ) //所有出边
         if ( exists ( i, j ) ) { delete E[i][j]; V[j].inDegree--; } //逐条删除
      E.remove ( i ); n--; //删除第i行
      Tv vBak = vertex ( i ); V.remove ( i ); //删除顶点i
      for ( int j = 0; j < n; j++ ) //所有入边
         if ( Edge<Te> * e = E[j].remove ( i ) ) { delete e; V[j].outDegree--; } //逐条删除
      return vBak; //返回被删除顶点的信息
   }
// 边的确认操作
   virtual bool exists ( int i, int j ) //边(i, j)是否存在
   { return ( 0 <= i ) && ( i < n ) && ( 0 <= j ) && ( j < n ) && E[i][j] != NULL; }
// 边的基本操作：查询顶点i与j之间的联边（0 <= i, j < n且exists(i, j)）
   virtual EType & type ( int i, int j ) { return E[i][j]->type; } //边(i, j)的类型
   virtual Te& edge ( int i, int j ) { return E[i][j]->data; } //边(i, j)的数据
   virtual int& weight ( int i, int j ) { return E[i][j]->weight; } //边(i, j)的权重
// 边的动态操作
   virtual void insert ( Te const& edge, int w, int i, int j ) { //插入权重为w的边e = (i, j)
      if ( exists ( i, j ) ) return; //确保该边尚不存在
      E[i][j] = new Edge<Te> ( edge, w ); //创建新边
      e++; V[i].outDegree++; V[j].inDegree++; //更新边计数与关联顶点的度数
   }
   virtual Te remove ( int i, int j ) { //删除顶点i和j之间的联边（exists(i, j)）
      Te eBak = edge ( i, j ); delete E[i][j]; E[i][j] = NULL; //备份后删除边记录
      e--; V[i].outDegree--; V[j].inDegree--; //更新边计数与关联顶点的度数
      return eBak; //返回被删除边的信息
   }
};

上面的类定义了私有成员顶点集（一维向量），边集（二维向量，即邻接矩阵）。

对于顶点的操作有：

顶点信息的获取

对于顶点信息的获取，比如出度、入度，在普通用二维数组实现的邻接矩阵中，均要O（n）的时间才能获得，而这里封装了邻接矩阵类，每当插入删除边均修改顶点信息，所以可以在O（1）的时间内获得入度出度等顶点信息。

邻点的枚举

这里首先在矩阵每一行的后面添加了一个假象哨兵E[i][n]表示i的第一个邻点，然后逆序的向前查找其它邻点。

边信息的读写如同顶点信息的读写一样，均可直接返回。下面总结下邻接矩阵的动态操作。

边的插入：创建新的边，更新边计数及受i顶点影响顶点的出入度。

边的删除：备份边的信息，直接删除边，更新边计数及出入度，返回被删除边的信息。

顶点的插入：在邻接矩阵末尾插入一列，在邻接矩阵最后插入一行，更新顶点集。

顶点的删除：删除所有出边，删除第i行，删除顶点i，删除入边及i列。

性能分析：

优点是适用于稠密图，可以在O（1）的时间内确定和修改一些信息。

缺点是不适用于稀疏图，平面图的空间利用率低。平面图-不相邻的边不能相交。

邻接表

如上图所示，存储稀疏图时，每个顶点后面接上一条链表，链表上有的顶点都是与该顶点存在边（弧）的顶点。

就空间复杂度而言，邻接表的空间复杂度为O（n + e），平面图的空间复杂度为O（n），较邻接矩阵平方级别的空间复杂度有着显著的提高（稀疏图中）。

既然邻接矩阵都封装了出度入度等信息，这里邻接表如果实现的话自然也要封装这类信息使得查找和更新出入度能在常数的时间内完成。

只是邻接表在判断两个顶点之间是否存在关联的操作复杂度提高到了O（e）。

比较：

广度优先搜索

BFS相当于树的层次遍历，或者说，以遍历起点为根，BFS一遍会生成一棵支撑树。

在介绍本节BFS的算法之前，先回忆下较为简单的BFS算法：

queue<int> q;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(int u){
    st[u]=true;
    d[u]=0;
    q.push(u);
    while(q.size()){
        int v=q.front();
        q.pop();
        for(int i=h[v];i!=-1;i=ne[i]){
            int w=e[i];
            if(!st[w]){
                st[w]=true;
                q.push(w);
                d[w]=d[v]+1;
                if(w==n)    return;
            }
        }
    }
}

这里的BFS的顶点有两种状态，已经被访问过（入过队）和未被访问过（未入队）。BFS的过程就是将队首元素出队，然后遍历其相邻的还未被访问过的节点，将其访问位置为true并且入队。

简而言之，之前常用的BFS顶点只涉及未被访问和已被访问两种状态。

先来看下这里要讲的BFS算法的框架：

在之前定义顶点的数据结构时，有这样一行语句：

typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus; //顶点状态

亦即所有顶点在遍历过程中可能会出现三种状态。

初始状态所有顶点都是undiscovered（未被发现）状态，某时刻顶点入队时，状态转化为discovered（已被发现），到最后出队了，其相邻的节点中未被发现的节点也均入队后，该顶点的状态也就变为最终的状态visited了。

看起来复杂，实质上只是在前面未访问和已访问两种状态后面加上了一种相邻节点已被访问完的状态而已。

除了顶点状态的变化，还有一点不容忽视的就是顶点在出队时，这一时刻被dTime所记录下来了。

循环内BFS的具体实现值得注意的有：

所有在顶点v出队并且遍历到其相邻顶点u时，若此前u的状态是undiscovered，则将u的状态置为discovered，随即入队，并且将v到u的这条边标记为树边tree（图的支撑树的边）。如果此前u的状态不是undiscovered（有两种可能），这里暂时都将v到u的边标记为跨边cross。

简单的说，tree：discovered的顶点到undiscovered的顶点构成的边；cross：discovered的顶点到discovered或visited顶点构成的边。

对于多连通图而言，从某个顶点s出发，只能遍历一个连通域，那么该如何遍历完所有的连通域呢？

首先分析下循环的终止条件，v初值为s，每次自增1同时对n取模，当s自增n次后再次回到s，此时循环终止。对于循环体内的BFS，只有当顶点未被发现时才会执行，所以有多少个连通域就会执行多少次BFS。

bfs总的代码如下：

template <typename Tv, typename Te> //广度优先搜索BFS算法（全图）
void Graph<Tv, Te>::bfs ( int s ) { //assert: 0 <= s < n
   reset(); int clock = 0; int v = s; //初始化
   do //逐一检查所有顶点
      if ( UNDISCOVERED == status ( v ) ) //一旦遇到尚未发现的顶点
         BFS ( v, clock ); //即从该顶点出发启动一次BFS
   while ( s != ( v = ( ++v % n ) ) ); //按序号检查，故不漏不重
}

template <typename Tv, typename Te> //广度优先搜索BFS算法（单个连通域）
void Graph<Tv, Te>::BFS ( int v, int& clock ) { //assert: 0 <= v < n
   Queue<int> Q; //引入辅助队列
   status ( v ) = DISCOVERED; Q.enqueue ( v ); //初始化起点
   while ( !Q.empty() ) { //在Q变空之前，不断
      int v = Q.dequeue(); dTime ( v ) = ++clock; //取出队首顶点v
      for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u
         if ( UNDISCOVERED == status ( u ) ) { //若u尚未被发现，则
            status ( u ) = DISCOVERED; Q.enqueue ( u ); //发现该顶点
            type ( v, u ) = TREE; parent ( u ) = v; //引入树边拓展支撑树
         } else { //若u已被发现，或者甚至已访问完毕，则
            type ( v, u ) = CROSS; //将(v, u)归类于跨边
         }
      status ( v ) = VISITED; //至此，当前顶点访问完毕
   }
}

复杂度分析：

BFS里当队列非空时循环会不断执行，而每次执行都会出队一个节点，故外层循环最多执行n次。对于内层循环遍历相邻节点的语句，若采用邻接矩阵存储，遍历一次需要O（n）的时间，而执行内层循环的语句只有当v与u存在边的情况下才会执行。故一共要O（n^2 + e）的时间，固然e可以忽略不计，得到O（n^2）的时间复杂度。但是由于内层的O（n）只是单纯的执行for循环判断，这在cache里面消耗的时间是特别短的，可以认为是常数的时间，故采用邻接矩阵更精确的说应该是O（n + e）的时间复杂度。当然，采用邻接表存储得到的便是严格意义上的O（n + e）的时间复杂度了。

关于边分类前面已经总结过了，这里要注意的是对于跨边而言，要详细分无向图和有向图讨论：

上面bfs的算法以教材中有向图为例更合适，而课件和邓公上课是以无向图举例，感觉略有不妥。在讲解BFS实例时，讲到s周围的acd都被标记为discovered，s被标记为visited，而当a出队访问其相邻节点时，邓公说到s作为支撑树中a的父结点可忽略，然而算法中没有忽略父结点的功能。更一般的理解，无向图中s到a和a到s在存储时当做两条边存储的，s到a为树边，a到s为跨边。

但是显然，无向图中s到a和a到s只是一条边，也只能是树边。所以这里又总结到：无向图的跨边只能是从discovered到discovered。对于无向图，v为discovered，如果u为visited，说明u相邻能到达的顶点（包括v）都已经访问过了，u到v已经是树边了，便不能被标记为跨边。所以无向图的bfs算法的确应该略作修改。

另外，BFS的典型应用就是求最短路问题，即当各边的权重相等时就可以采用BFS求最短路径了。

深度优先搜索

DFS是沿着某一条路径不断深入，直至不能再前进就开始回溯，最终遍历完所有的顶点，通常用递归实现。

主算法：

可以发现，顶点v在被访问之际被标记为discovered，同时记录下被发现的时间dTime。当v的所有邻居也均被访问了，最后将v标记为visited，同时记录下访问结束时间fTime。

同样，当v的某一邻居u的状态还是undiscovered时，v到u就可标记为树边了，同时继续沿着u节点继续dfs；若v的邻居u是discovered状态，说明此前u已被发现但未访问完毕，属于后代节点指向祖先节点，标记为backward；若u的状态是visited，说明所有u的邻居都被访问完毕了，此时v还能指向u，说明v到u是单向边，也只有在有向图中才会出现这种状况，这时需要比较v和u的dTime，若v先于u被发现，则标记该边为前向边forward，否则标记为跨越边cross。

无向图实例：

树边比较显然，a到b，b到c等都是树边，而遍历到e点时，a点的状态是discovered，所以e到a是forward回向边，同理，d到g，g到f也均是forward边。

有向图实例：

a到b这样的是树边，a访问到b再访问到c最后回溯到a，此时c的状态为visited，并且a的发现时间要小于c，故a到c的边是forward边；访问到g节点时，a的状态还是discovered，故g到a的边为forward边，c的状态是visited，并且c先于g发现，故g到c的边为cross边。

值得注意的是，当图中包含forward边时，一定有环，比如abca。

对于多连通图，与bfs一样，dfs也可以多次调用来遍历完全图。

dfs总的代码如下：

template <typename Tv, typename Te> //深度优先搜索DFS算法（全图）
void Graph<Tv, Te>::dfs ( int s ) { //assert: 0 <= s < n
   reset(); int clock = 0; int v = s; //初始化
   do //逐一检查所有顶点
      if ( UNDISCOVERED == status ( v ) ) //一旦遇到尚未发现的顶点
         DFS ( v, clock ); //即从该顶点出发启动一次DFS
   while ( s != ( v = ( ++v % n ) ) ); //按序号检查，故不漏不重
}

template <typename Tv, typename Te> //深度优先搜索DFS算法（单个连通域）
void Graph<Tv, Te>::DFS ( int v, int& clock ) { //assert: 0 <= v < n
   dTime ( v ) = ++clock; status ( v ) = DISCOVERED; //发现当前顶点v
   for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u
      switch ( status ( u ) ) { //并视其状态分别处理
         case UNDISCOVERED: //u尚未发现，意味着支撑树可在此拓展
            type ( v, u ) = TREE; parent ( u ) = v; DFS ( u, clock ); break;
         case DISCOVERED: //u已被发现但尚未访问完毕，应属被后代指向的祖先
            type ( v, u ) = BACKWARD; break;
         default: //u已访问完毕（VISITED，有向图），则视承袭关系分为前向边或跨边
            type ( v, u ) = ( dTime ( v ) < dTime ( u ) ) ? FORWARD : CROSS; break;
      }
   status ( v ) = VISITED; fTime ( v ) = ++clock; //至此，当前顶点v方告访问完毕
}

括号引理

在DFS过程中，某个顶点的活跃期从被发现的时刻dTime开始，到其所有相邻顶点均被访问完毕的时刻（全部被标记为visited）fTime结束。由于在dfs森林中，后代节点总是晚于祖先节点被发现并且要早于祖先节点访问结束，所以祖先的活跃期是包含后代节点的活跃期的，换而言之，只要顶点u的活跃期包含v的活跃期，就可以断定u是v的祖先节点。同样，如果两个节点无关，则活跃期的交集为空集。

拓扑排序

如果要顺序的输出零入度顶点，则只需将最开始的零入度顶点入栈，之后每次取栈顶元素并出栈，将与其相邻的顶点入度为1的均入栈，最后将相邻顶点的入度均减一，重复该过程直至栈空。

上面的算法是每次找入度为0的顶点入队，从而找到拓扑排序序列。反过来如果某顶点的出度为0，说明该结点不为任何顶点的前驱，也就是说可以放在最后完成，同样消去该结点后出度为0的结点也只需在该顶点前一刻被完成即可。由此得到另一种拓扑排序算法：

这里寻找出度为0的顶点直接借助了dfs，因为在dfs中，最先被访问完成成为visited的顶点必然没有可达顶点需要去访问了，此时其出度为0，所以只需按照dfs过程中结点被标记为visited的先后次序依次入栈，最后从栈顶到栈底的序列便是拓扑序列了。

当然，只有DAG才能有合法的拓扑序列，因此在DFS过程中一旦发现回向边，即存在环，便可立即退出算法。

优先级搜索

优先级搜索（PFS）是一种通用算法，因为不论是DFS还是BFS都是按照某种选取顶点进行访问策略来遍历的，如果我们为每个顶点维护一个优先级数，优先级数小的优先级高，率先被访问，这样便提供了一个通用的接口。

prim算法

首先考虑求MST的蛮力算法

由于一个完全图的支撑树可以有n^(n – 2)棵，故不可使用枚举法，因为2^n < n! < n^n。

枚举支撑树的复杂度比指数级别的复杂度还要高上两个等级。

非平凡子集-除了空集以及自身的子集，所以所谓的割，不过是将图分为两个不相交的点集U以及V\U，连接两个子集的边称为跨越边。

上图给出了一种MST算想的证明，即任一MST必然通过极短跨越边联结每一割。求MST的过程可以理解为向支撑树点集中不断添加顶点的过程，某时刻支撑树点集为V，图中剩下点的点集为U，则只需要找到从V到U的一条极短跨越边添加到支撑树中即可，这种算法也就是prim算法。

优先级更新器

Dijkstra算法

最短路问题分为单源最短路和多源最短路问题。

SPT并不等同于MST，其一是SPT只需要连接起点到终点，并不需要是支撑树；其二是优先级的判定也不同，SPT每次要加入的是离起点最近的顶点。

三角不等式

dijkstra算法与prim算法极为类似，不同之处在于前面提过的需要每次选取离起点最近的顶点加入点集，并且更新尝试松弛相邻顶点。并且dijkstra算法仅适用于求不含负权图的最短路径。

双连通分量

无向图的关节点-删除后连通分量数增加；双连通图-无关节点的图，即删去任意顶点原图的连通分量不至于增加；极大的双连通子图称为双连通分量（BCC）。

DFS树中的叶结点不可能是关节点，因为删掉它不会造成其它顶点的不连通，不至于增加连通分量。

根结点在含有两个及以上子树的情况下是关节点。（PS：课件上把if写在后面我还以为根结点都含有两个及以上子树，纠结了半天）

内节点是关节点仅当其某棵极大真子树中没有顶点经后向边连接到v的真祖先。

所以只需找到各个顶点后向边能够连接到的最高祖先节点即可。

找到每个节点的HCA是求双连通分量的关键，比如dfs树中树边为ab，bc，cd，还有一条d到a的后向边，那么a即是d的HCA，abcda也就构成了一个双连通分量。我们只需在dfs过程中，把abcd的HCA均标记为a的dTime即可。

任何节点在首次被发现时其hca均被设置为它的dTime值，为了保存双连通分量中的节点，这里在遍历v相邻节点前先用一个栈存下v节点。

这里当v的邻接顶点u dfs完成后，如果u的hca被更新得更小了，则v的hca同样需要更新；如果u的hca等于v的dtime，说明此时已经hca的值已经是v了，v即为关节点，此刻栈中完整的存储着v往u方向遍历下去的序列，即一个双连通分量，可以弹出栈中所有的元素保存下来，之后再将v重新入栈，朝着v的另一个方向继续遍历。

当u的状态为discovered时，回向边出现了，此时应该尝试更新v的hca。

求双连通分量总的代码如下：

template <typename Tv, typename Te> void Graph<Tv, Te>::bcc ( int s ) { //基于DFS的BCC分解算法
   reset(); int clock = 0; int v = s; Stack<int> S; //栈S用以记录已访问的顶点
   do
      if ( UNDISCOVERED == status ( v ) ) { //一旦发现未发现的顶点（新连通分量）
         BCC ( v, clock, S ); //即从该顶点出发启动一次BCC
         S.pop(); //遍历返回后，弹出栈中最后一个顶点——当前连通域的起点
      }
   while ( s != ( v = ( ++v % n ) ) );
}

#define hca(x) (fTime(x)) //利用此处闲置的fTime[]充当hca[]
template <typename Tv, typename Te> //顶点类型、边类型
void Graph<Tv, Te>::BCC ( int v, int& clock, Stack<int>& S ) { //assert: 0 <= v < n
   hca ( v ) = dTime ( v ) = ++clock; status ( v ) = DISCOVERED; S.push ( v ); //v被发现并入栈
   for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u
      switch ( status ( u ) ) { //并视u的状态分别处理
         case UNDISCOVERED:
            parent ( u ) = v; type ( v, u ) = TREE; BCC ( u, clock, S ); //从顶点u处深入
            if ( hca ( u ) < dTime ( v ) ) //遍历返回后，若发现u（通过后向边）可指向v的真祖先
               hca ( v ) = min ( hca ( v ), hca ( u ) ); //则v亦必如此
            else { //否则，以v为关节点（u以下即是一个BCC，且其中顶点此时正集中于栈S的顶部）
               /*DSA*/printf ( "BCC rooted at %c:", vertex ( v ) );
               /*DSA*/Stack<int> temp; do { temp.push ( S.pop() ); print ( vertex ( temp.top() ) ); } while ( v != temp.top() ); while ( !temp.empty() ) S.push ( temp.pop() );
               while ( v != S.pop() ); //依次弹出当前BCC中的节点，亦可根据实际需求转存至其它结构
               S.push ( v ); //最后一个顶点（关节点）重新入栈——分摊不足一次
               /*DSA*/printf ( "\n" );
            }
            break;
         case DISCOVERED:
            type ( v, u ) = BACKWARD; //标记(v, u)，并按照“越小越高”的准则
            if ( u != parent ( v ) ) hca ( v ) = min ( hca ( v ), dTime ( u ) ); //更新hca[v]
            break;
         default: //VISITED (digraphs only)
            type ( v, u ) = ( dTime ( v ) < dTime ( u ) ) ? FORWARD : CROSS;
            break;
      }
   status ( v ) = VISITED; //对v的访问结束
}
#undef hca

不妨用上图体会下该算法的执行流程。

Kruskal算法

正确性证明：

实现：

采用并查集实现，每次选取最短的边加入到MST集合中，如果该边的两个顶点已经处在同一个集合中，则跳过。

int fa[100005];
struct Edge{
    int x,y,w;
    bool operator < (const Edge &e)const{
        return w < e.w;
    }
}edge[maxn];
int get(int x){
    if(x != fa[x])  return fa[x] = get(fa[x]);
    return fa[x];
}
int kruskal(){
    sort(edge,edge + m);
    for(int i = 1;i <= n;i++)   fa[i] = i;
    int res = 0,cnt = 0;
    for(int i = 0;i < m;i++){
        int w = edge[i].w,x = edge[i].x,y = edge[i].y;
        int u = get(x),v = get(y);
        if(u != v){
            fa[u] = v;
            res += w;
            cnt++;
        }
    }
    if(cnt < n - 1) return INF;
    return res;
}

Floyd算法

Floyd算法使用动态规划的思想来解决多源最短路问题。

即每趟循环通过k结点尝试更新u到v的最短距离，时间复杂度为立方级别。