Code Monkey home page Code Monkey logo

1's People

Contributors

caaaa-a avatar

Watchers

 avatar

1's Issues

Floyd

全局最短路

一篇解释很好的文章:https://www.cnblogs.com/wangyuliang/p/9216365.html

  1. 全局最短路
    用一句话概括就是:从 i 号顶点到 j 号顶点只经过前 k 号点的最短路程。
    核心代码:
    for(k=1;k<=n;k++)  
    for(i=1;i<=n;i++)  
    for(j=1;j<=n;j++)  
    if(e[i][j]>e[i][k]+e[k][j])  
          e[i][j]=e[i][k]+e[k][j];
  1. 最小环问题
    都比较容易得到从 u 到 v 经过中间某一些结点的最短路,但是我们得确保回来的时候,不能经过那些结点,这样我们就需要改一下 floyd 算法了。
    核心代码:
int mincircle = infinity;
Dist = Graph;

for(int k=0;k<nVertex;++k){
    //新增部分:
    for(int i=0;i<k;++i)
        for(int j=0;j<i;++j)
            mincircle = min(mincircle,Dist[i][j]+Graph[j][k]+Graph[k][i]);
    //通常的 floyd 部分:
    for(int i=0;i<nVertex;++i)
        for(int j=0;j<i;++j){
            int temp = Dist[i][k] + Disk[k][j];
            if(temp < Dist[i][j])
                Dist[i][j] = Dist[j][i] = temp;
        }
}
  • Floyd 算法保证了最外层循环到 k 时所有顶点间已求得以 0…k-1 为中间点的最短路径。
  • 新增部分在前面:因为在之前的最短路径更新过程中, k 没有参与更新,所以dist[i][j]所表示的路径中不会有点 k ,即一定为一个环;

一个环至少有3个顶点,设某环编号最大的顶点为 L ,在环中直接与之相连的两个顶点编号分别为 M 和 N (M,N < L),则最大编号为 L 的最小环长度:
              Graph(M,L) + Graph(N,L) + Dist(M,N)
  其中 Dist(M,N) 表示以 0…L-1 号顶点为中间点时的最短路径,刚好符合 Floyd 算法最外层循环到 k=L 时的情况,则此时对 M 和 N 循环所有编号小于 L 的顶点组合即可找到最大编号为 L 的最小环。再经过最外层 k 的循环,即可找到整个图的最小环。

#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 150;
int n,m,a,b,c;
int mp[maxn][maxn];//表示的正常从u到v经过k的最短路
int A[maxn][maxn];//表示的是不经过k的时候回来的时候的最短路
int floyd()
{
   int retmin = INF;
   for(int k = 1;k <= n;k++)
   {
       for(int i = 1;i < k;i++)//假设k为最大的结点,进行遍历优化,并且最后也不会包含最大的结点n
       {
           for(int j = i + 1;j < k;j++)
           {
               //为什么不更新优化mp数组呢,是因为这是一个暴力的循环,总能够找到最小值!
               int tmp = A[i][j] + mp[i][k] + mp[k][j];
               //这个时候A[i][j]还没有更新k结点!!因为下一层才开始更新……
               if(tmp < retmin)retmin = tmp;
           }
       }
       for(int i = 1;i <= n;i++)
       {
           for(int j = 1;j <= n;j++)
           {
               if(A[i][j] > A[i][k] + A[k][j])
                   A[i][j] = A[i][k] + A[k][j];
           }
       }
   }
   return retmin;
}
int main()
{
   int i,j;
   while(~scanf("%d%d",&n,&m))
   {
       //初始化
       for(int i = 1;i <= n;i++)
       {
           for(int j = 1;j <= n;j++)
           {
               mp[i][j] = A[i][j] = INF;
           }
       }
       //输入距离进行更新,防止重边的影响,自动定义为双向边
       for(int i = 1;i <= m;i++)
       {
           scanf("%d%d%d",&a,&b,&c);
           mp[a][b] = mp[b][a] = A[a][b] = A[b][a] = min(mp[a][b],c);
       }
       //进行floyd算法,寻找最小环
       int s = floyd();
       if(s == INF)
           printf("It's impossible.\n");
       else
           printf("%d\n",s);
   }
   return 0;

Bellman-ford

适用条件&范围:

  • 单源最短路径(从源点s到其它所有顶点v);
  • 有向图&无向图(无向图可以看作$(u,v),(v,u)$同属于边集E的有向图);
  • 边权可正可负(如有负权回路输出错误提示);
  • 差分约束系统;

Bellman-Ford算法的流程如下:

  1. 给定图$G(V, E)$(其中$V、E$分别为图$G$的顶点集与边集),源点$s$,数组$Distant[i]$记录从源点s到顶点i的路径长度,初始化数组$Distant[s]$为0;

  2. 以下操作循环执行至多$n-1$次,$n$为顶点数:

    • 对于每一条边$e(u, v)$,
      如果$Distant[u] + w(u, v) < Distant[v]$,
        则  $Distant[v] = Distant[u]+w(u, v)$。
      其中$w(u, v)$为边$e(u,v)$的权值;
    • 若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环。否则执行下次循环;
  3. 对于每一条边$e(u, v)$,如果存在$Distant[u] + w(u, v) < Distant[v]$的边,则图中存在负环路,即是说改图无法求出单源最短路径。否则数组$Distant[n]$中记录的就是源点$s$到各顶点的最短路径长度。

可知,Bellman-Ford算法寻找单源最短路径的时间复杂度为$O(V*E)$.

Bellman-Ford算法可以大致分为三个部分

  • 第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为 0,其它的点的值设为无穷大(表示不可达)。
  • 第二,进行循环,循环下标为从1到$n-1$(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。
  • 第三,遍历途中所有的边$edge(u,v)$,判断是否存在这样情况:
    $d(v) &gt; d (u) + w(u,v)$
    则返回false,表示途中存在从源点可达的权为负的回路。

之所以需要第三部分的原因,是因为,如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。

与dij的比较

在更新路径的操作上,和迪杰斯特拉算法大同小异,但是不同于迪杰斯特拉算法,他不是选取最小的边进行选择,而是根据每一条边,依次对Distence数组进行更新,所以会访问很多访问过的点,借此重复不遗漏的更新距离数组,也就是规划起点到当前访问的相邻点的问题。

核心代码:

struct Node{
    int v,dis;
};
vector<Node> Adj[MAXV];
int n;
int d[MAXV];
 
bool Bellman(int s){
    fill(d,d+MAXV,INF);
    d[s]=0;
    for(int i=0;i<n-1;i++){
        for(int u=0;u<n;u++){
            for(int j=0;j<Adj[u].size();j++){
                int v=Adj[u][j].v;
                int dis=Adj[u][j].dis;
                if(d[u]+dis<d[v]){
                    d[v]=d[u]+dis;
                }
            }
        }
    }
    for(int u=0;u<n;u++){
            for(int j=0;j<Adj[u].size();j++){
                int v=Adj[u][j].v;
                int dis=Adj[u][j].dis;
                if(d[u]+dis<d[v]){
                    return false;
            }
        }
    }
    return true;
}

Dij及堆优化

分析

Dij算法是基于广搜,松弛的时候有点贪心和动态规划的**。

使用邻接矩阵实现的dijkstra算法的复杂度是O(V²)。
使用邻接表,更新最短距离只需要访问每条边一次,因此这部分的复杂度是O(E)。但是每次要枚举所有的顶点来查找下一个使用的顶点,因此最终复杂度还是O(V²)。
综上:在|E|比较小时,大部分的时间都花在了查找下一个使用的顶点上,因此需要使用合适的数据结构进行优化。

优先队列+dijkstra算法:
总时间复杂度=找最短距离 u 的时间复杂度 + 更新距离 dist[v] 的时间复杂度


对于无向图G(V,E):
   找最短距离的时间复杂度为O($|V|^2$)(共循环V次,每次V个点),考虑到Q每次递减1,实际复杂度为$O(|V|^2/2)$;
   由于图共有E条边,每条边最多被更新2次(1条边2个端点),因此更新距离的时间复杂度为$O(2*|E|)$。
因此,总时间复杂度$=O(2|E|+|V|^2/2)$*

  实际情况中经常会遇到 $|V|^2&gt;&gt;|E|$ 的稀疏图,即$O(2*|E|+|V|^2/2)=O(|V|^2/2)$
   因此,如果我们能够优化 findMIN部分,即可大大优化稀疏图下的dijkstra算法,findMIN的部分优化方法很多,最简单的就是用二分搜索$O(logN)$代替线性搜索 $O(N)$
   这里我们将集合Q转化成一个优先队列(priority queue),这样findMIN的时间复杂度变成了O(1),而每次更新priority queue需要花费$O(log|V|)$
综上,采用优先队列之后,总时间复杂度=$O(2|E|+|V|log|V|)$,这样的优化对于稀疏图(|V|^2>>|E|)来说,尤为有效

用邻接矩阵的Dijkstra算法的代码:

int dis[maxn];
bool visit[maxn];
int n,m;   //V,E
    void Dijkstra( int s )
    {
        int i,v,u;
        for( i=1; i<=n; ++i )
        {
            visit[i]=false;
            dis[i]=mp[1][i];
        }
        dis[s]=0;
    while( true )
    {
        v=-1;
        for( u=1; u<=n; ++u )
            if( !visit[u] && ( v==-1 || dis[u]<dis[v]) )
                v=u;
        if( v==-1 ) break;
        visit[v]=true;
 
 
        for( u=1; u<=n; u++ )
            dis[u]= min( dis[u],dis[v]+mp[v][u] );
    }
}

使用STL的priority_queue实现。在每次更新时往堆里插入当前最短距离和顶点的值对。

#include <iostream>  
#include <cstdio>  
#include <queue>  
#include <vector>  
using namespace std;  
const int Ni = 10000;  
const int INF = 1<<27;  
struct node{  
    int x,d;  
    node(){}  
    node(int a,int b){x=a;d=b;}  
    bool operator < (const node & a) const  
    {  
        if(d==a.d) return x<a.x;  
        else return d > a.d;  
    }  
};  
vector<node> eg[Ni];  
int dis[Ni],n;  
void Dijkstra(int s)  
{  
    int i;  
    for(i=0;i<=n;i++) dis[i]=INF;  
    dis[s]=0;  
    //用优先队列优化  
    priority_queue<node> q;  
    q.push(node(s,dis[s]));  
    while(!q.empty())  
    {  
        node x=q.top();q.pop();  
        for(i=0;i<eg[x.x].size();i++)  
        {  
            node y=eg[x.x][i];  
            if(dis[y.x]>x.d+y.d)  
            {  
                dis[y.x]=x.d+y.d;  
                q.push(node(y.x,dis[y.x]));  
            }  
        }  
    }  
}  
int main()  
{  
    int a,b,d,m;  
    while(scanf("%d%d",&n,&m),n+m)  
    {  
        for(int i=0;i<=n;i++) eg[i].clear();  
        while(m--)  
        {  
            scanf("%d%d%d",&a,&b,&d);  
            eg[a].push_back(node(b,d));  
            eg[b].push_back(node(a,d));  
        }  
        Dijkstra(1);  
        printf("%d\n",dis[n]);  
    }  
    return 0;  
}  
/* 
6 6 
1 2 2 
3 2 4 
1 4 5 
2 5 2 
3 6 3 
5 6 3 
*/  

原网址:https://blog.csdn.net/major_zhang/article/details/72519233

Dij和Floyd比较

Dij和Floyd的比较

    • Dij不适用于负权边
    • Floyd不适用于负权环
    • Dij适用于单源路径问题(简单来说就是确定一个源点s 求s到1,2,3……)
    • Floyd适用于多源点路径问题 就是说在n个点中任选两个点 求这两个点之间的最短路径
    • Dij的**是“插边”
      dp方程式:dis[u]=min(dis[u],e[v][u]+dis[v])
      v是离源点最近且没被标记的那个点
    • Floyd的**是“插点”
      强行插入一个点k 注意在循环的时候k要放在最外面(因为floyd的**便是令 k 循环n次 强行插入到(i,j)中去)
      dp方程式: e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
      e[i][j]就是指从i到j的距离
    • dij的时间复杂度是O(n^2),经过堆的优化可以达到O((m+n)log(n));
    • floyd的时间复杂度是O(n^3)

原文链接:https://blog.csdn.net/XXXTANTACION/article/details/100099854


核心代码比较:
Floyd:是最简单的最短路径算法,可以计算图中任意两点间的最短路径 folyd算法的时间复杂度是O(N3),如果是一个没有边权的图,把相连的两点 间的距离设为dist[i][j] = 1,不相连的两点设为无穷大,用 floyd算法可以判断i,j两点是否有路径相连。

void floyd()
{
    for(int k = 0; k < n; k ++){ //作为循环中间点的k必须放在最外一层循环 
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                if(dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];    //dist[i][j]得出的是i到j的最短路径 
                }     
            }    
        }    
    }    
}

Dij:用来计算从一个点到其他所有点的最短路径的算法,复杂度O(N2)。

void dijkstra(int s)   //s是起点
{
    memset(visit, false, sizeof(visit));    
    visit[s] = true;
    for(int i = 0; i < n; i ++){
        dist[i] = graph[s][i];
    }
     
    int index;
    for(int i = 1; i < n; i ++){
        int mincost = INF;
        for(int j = 0; j < n; j ++){
            if(!visit[j] && dist[j] < mincost){
                mincost = dist[j];
                index = j;    
            }    
        }
        visit[index] = true;
        for(int j = 0; j < n; j ++){
            if(!visit[j] && dist[j] > dist[index] + graph[index][j]){
                dist[j] = dist[index] + graph[index][j];
            }    
        }    
    }
}

原文链接:https://www.cnblogs.com/aiyelinglong/archive/2012/03/26/2418707.html

图论基础

一、基本术语

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

无向边(Edge):若顶点V1到V2之间的边没有方向,则称这条边为无向边。

无向图(Undirected graphs):图中任意两个顶点之间的边都是无向边。(A,D)=(D,A)对于无向图G来说,G1=(V1,{E1}),其中顶点集合V1={A,B,C,D};边集和E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

有向边:若从顶点V1到V2的边有方向,则称这条边为有向边,也称弧(Arc)。用<V1,V2>表示,V1为狐尾(Tail),V2为弧头(Head)。(V1,V2)≠(V2,V1)。

有向图(Directed graphs):图中任意两个顶点之间的边都是有向边。

注意:无向边用“()”,而有向边用“< >”表示。

简单图:图中不存在顶点到其自身的边,且同一条边不重复出现。

无向完全图:无向图中,任意两个顶点之间都存在边。

有向完全图:有向图中,任意两个顶点之间都存在方向互为相反的两条弧。

稀疏图:有很少条边。

稠密图:有很多条边。

权(Weight):与图的边或弧相关的数。

网(Network):带权的图。

路径的长度:一条路径上边或弧的数量。

二、图的存储结构

  • 1.邻接矩阵:用两个数组,一个数组保存顶点集,一个数组保存边集。

图的邻接矩阵存储的结构:

    #define maxvex 100
    typedef struct
    {
    char vexs[maxvex];
    int arc[maxvex][maxvex];
    int vertex,edges;
    }MGraph;

无向图的创建代码:

    #define maxvexs 100
    #define infinity 65535//用65535来表示∞
    typedef struct
    {
        char vexs[maxvexs];
        int arc[maxvexs][maxvexs];
        int vertexes,edges;
    }mgraph;

    void creatgraph(mgraph *g)
    {
        int i,j,k,w;
        printf("输入顶点数和边数:\n");
        scanf("%d,%d",&g->vertexes,&g->edges);
        for(i=0;i<g->vertexes;i++)//读入顶点信息,建立顶点表
            scanf("%c",&g->vexs[i]);
        for(i=0;i<g->vertexes;i++)
            for(j=0;j<g->vertexes;j++)
                g->arc[i][j]=infinity;//初始化邻接矩阵
        for(k=0;k<g->vertexes;k++)//读入edges条边,建立邻接矩阵
        {
            printf("输入边(Vi,vj)上的下标i,下标j,和权w:\n");
            scanf("%d%d%d",&i,&j,&w);
            g->arc[i][j]=w;
            g->arc[j][i]=w;//无向图,矩阵对称
        }
    }
  • 2.邻接表:数组与链表相结合的存储方法。

对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。

邻接表结点定义

    typedef struct EdgeNode
    {
        int adjvex; //邻接点域,存储该顶点对应的下标
        int weight; //用于存储权值,对于非网图可以不需要
        struct EdgeNode *next;  //链域,指向下一个邻接点
    }EdgeNode;//边表结点

    typedef struct VertexNode //顶点表结点
    {
        char data; //顶点域,存储顶点信息
        EdgeNode *firstedge; //边表头指针
    }VertexNode,AdjList[MAXVEX];

    typedef struct
    {
        AdjList adjList;
        int numVertexes,numEdges;//图中当前顶点数和边数
    }GraphAdjList;
  • 3.边集数组

img

(1)边集数组定义

边集数组是利用一维数组存储图中所有边的一种图的表示方法。该数组中所含元边的个数要等于图中的边的条数,每个元素用来存储一条边的起点、终点和权(若含有权的话)。每个元素包含三个属性,因此建议先定义为结构体,再定义结构体数组。对于无向图,可选定变得任一端为起点或终点。各边在数组中的次序可以任意安排,也可以根据具体要求而定。

    struct Edge{
        int s;
        int e;
        int length;
    }Edge[100];

(2)边集数组的特征

在边集数组中查找一条边或一个顶点的都需要扫描整个数组,所以其时间复杂度为O(e)。边集数组适合那些对边依次进行处理的运算,不适合对顶点的运算和对任一条边的运算。边集数组的表示通常包括一个边集数组和一个顶点 数组,所以其空间复杂度为O(n+e)。从空间复杂度上讲,边集数组也适合表示稀疏图。

  • 4.前向星:前向星是一种通过储存边信息的方式储存图的结构。

读入每条边的信息(起点、终点、权值)
存放在数组里
按照起点排序
通常会有一个head数组,记录每个起点上的第一条边。

最小生成树

prime算法

1.清空生成树,任取一个顶点加入生成树

2.在那些一个端点在生成树里,另一个端点不在生成树里的边中,选取一条权最小的边,将它和另一个端点加进生成树

3.重复步骤2,直到所有的顶点都进入了生成树为止,此时的生成树就是最小生成树

核心代码:

int prime(int index)
{
    int index;
    int sum = 0;
    memset(visit, false, sizeof(visit));
    visit[cur] = true;
    for(int i = 0; i < m; i ++){
        dist[i] = graph[cur][i];    
    }

    for(int i = 1; i < m; i ++){

        int mincost = INF;
        for(int j = 0; j < m; j ++){
            if(!visit[j] && dist[j] < mincost){
                mincost = dist[j];
                index = j;    
            }    
        }

        visit[index] = true;
        sum += mincost;

        for(int j = 0; j < m; j ++){
            if(!visit[j] && dist[j] > graph[index][j]){
                dist[j] = graph[index][j];
            }    
        }    
    }
    return sum;    
}

堆优化的prime:

堆优化实际上就是对于每一次拓展的边加入到一个小根堆中,即找最小边的时候直接用堆来储存

核心代码:

void queue_prim()
{
    //以节点1为起点进行扩展安全边 生成最小树
    priority_queue<node>que;
    while(!que.empty())
        que.pop(); //初始化清空优先队列 维护一个小根堆
                  //这样每次找安全边的速度就提高了
    ans = 0;
    memset(vis, false, sizeof(vis));
    for(int i=0; i<q[1].size(); i++){
        que.push(q[1][i]); //将起点的所有连接边全部加入队列中来
    }
    vis[1]=true;
    int edge=n-1;//边数
    node cur;
    while(edge--)
    {
        cur = que.top();
        que.pop();//这个地方需要注意一下
                  //并不是每个从优先队列取出来的边都是可以加到生成树上去的
 
        if(vis[cur.v]==true){
            while(vis[cur.v]){
                cur=que.top(); que.pop();
            }
        }
        ans = ans+cur.w; //printf("%d--  ", cur.w );
        vis[cur.v]=true; //加入生成树的该点将被标记访问
        for(int i=0; i<q[cur.v].size(); i++){
            if(vis[ q[cur.v][i].v ]==false) //当前加入生成树的点可以扩充出的边指向的节点
                que.push(q[cur.v][i]);//如果没有被访问才会加入到队列当中来
        }
    }
}

kruskal算法

在剩下的所有未选取的边中,找最小边,如果和已选取的边构成回路,则放弃,选取次小边。

//把每条边成为一个结构体,包括起点、终点和权值
typedef struct node
{
    int val;
    int start;
    int end;    
}edge[SIZE * SIZE / 2];

//把每个元素初始化为一个集合
void make_set()
{
    for(int i = 0; i < n; i ++){
        father[i] = i;
        rank[i] = 1;    
    }    
    return ;
}

//查找一个元素所在的集合,即找到祖先
int find_set(int x)
{
    if(x != father[x]){
        father[x] = find_set(father[x]);    
    }    
    return father[x];
}

//合并x,y所在的两个集合:利用Find_Set找到其中两个
//集合的祖先,将一个集合的祖先指向另一个集合的祖先。
void Union(int x, int y)
{
    x = find_set(x);    
    y = find_set(y);
    if(x == y){
        return ;    
    }
    if(rank[x] < rank[y]){
        father[x] = find_set(y);    
    }
    else{
        if(rank[x] == rank[y]){
            rank[x] ++;    
        }    
        father[y] = find_set(x);
    }
    return ;
}

bool cmp(pnode a, pnode b)
{
    return a.val < b.val;    
}

int kruskal(int n) //n为边的数量
{
    int sum = 0;
    make_set();
    for(int i = 0; i < n; i ++){   //从权最小的边开始加进图中
        if(find_set(edge[i].start) != find_set(edge[i].end)){
            Union(edge[i].start, edge[i].end);
            sum += edge[i].val;    
        }    
    }
    return sum;    
}

Agri-Net的Kruskal算法+并查集实现

算法复杂度分析

    对所有的边进行排序,排序复杂度为$O(mlogm)$,随后对边进行合并,合并使用并查集,并查集使用link by size的方式实现,同时在find函数实现了路径压缩。

  • 每个元素第一次被执行find操作需要的复杂度为$O(logm)$,总共m个元素
  • 如果已经有n-1条边,那么可以停止循环,时间复杂度为$O(nlogm)$
  • 时间复杂度为$O(mlogm+nlogm)$

而存在最小生成树中的情况下,图至少有$n-1$条边,即$m>=n-1$,于是整体复杂度为$O(mlogn)$。即使对并查集做了路径压缩的优化,但是前面的排序过程仍然是算法的瓶颈,因此算法复杂度仍然是$O(mlogn)$。

核心代码

// 并查集
struct QuickUnion {
	vector<int> sz; // 表示集合大小的数组
	vector<int> parent; // 表示一个顶点的所在集合的根节点
	QuickUnion(const int n) {
		sz.assign(n,0);
		for (int i = 0; i < n; ++i)
			parent.push_back(i);
	}
	// 寻找一个节点的根节点
	int find(const int x) {
		if (x != parent[x])
			parent[x] = find(parent[x]);// 路径压缩
		return parent[x];
	}
	// 合并两个节点所在的集合
	bool unionNode(const int x, const int y) {
		int p1 = find(x);
		int p2 = find(y);
		if (p1 == p2)
			return false;
		if (sz[p1] >= sz[p2]){
			sz[p1] += sz[p2];
			parent[p2] = p1;
		}
		else{
			sz[p2] += sz[p1];
			parent[p1] = p2;
		}
		return true;
	}
};

int Kruskal(vector<Edge> graph, int nodeNum) {
	QuickUnion qu(nodeNum);
	sort(graph.begin(),graph.end());
	int MSTWeight = 0;
	int edgeCount = 0;
	for (auto&e : graph){
		if (qu.unionNode(e.from, e.to)){
			MSTWeight += e.weight;
			++edgeCount;
			if (edgeCount == nodeNum - 1)
				break;
		}
	}
	return MSTWeight;
}

原文链接:https://blog.csdn.net/t46414704152abc/article/details/83896339

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.