精华内容
下载资源
问答
  • 最小生成树:一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n ...一、Prim算法Prim算法通常以邻接矩阵作为储存结构。算法思路:以顶点为主导地位,从起始顶点出发,通过选择当前可用的...

    最小生成树:

    一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。简单来说就是有且仅有n个点n-1条边的连通图。

    而最小生成树就是最小权重生成树的简称,即所有边的权值之和最小的生成树。

    最小生成树问题一般有以下两种求解方式。

    一、Prim算法

    Prim算法通常以邻接矩阵作为储存结构。

    算法思路:以顶点为主导地位,从起始顶点出发,通过选择当前可用的最小权值边把顶点加入到生成树当中来:

    1.从连通网络N={V,E}中的某一顶点U0出发,选择与它关联的具有最小权值的边(U0,V),将其顶点加入到生成树的顶点集合U中。

    2.以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(U,V),把它的顶点加入到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。

    朴素版时间复杂度O(n²)算法模板:

    06d4b29ec6bdc793ee516b5728676d00.gif

    #include

    #include

    #include

    #include

    using namespace std;

    const int N = 500+10;

    int n,m;

    int g[N][N],dis[N],vis[N];

    void prim()

    {

    memset(dis,0x1f,sizeof dis);

    dis[1]=0;

    for(int j=1;j<=n;j++)

    {

    int min_len=2e+9,k;

    for(int i=1;i<=n;i++)

    {

    if(!vis[i]&&dis[i]

    {

    min_len=dis[i];

    k=i;

    }

    }

    vis[k]=1;

    for(int i=1;i<=n;i++)

    {

    if(!vis[i]&&dis[i]>g[k][i])

    dis[i]=g[k][i];

    }

    }

    }

    int main()

    {

    scanf("%d%d",&n,&m);

    memset(g,0x1f,sizeof g);

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

    {

    int u,v,w;scanf("%d%d%d",&u,&v,&w);

    g[u][v]=g[v][u]=min(g[u][v],w); //因为有重边,所以取min

    }

    prim();

    int ans=0;

    for(int i=1;i<=n;i++)ans+=dis[i];

    if(ans>1e7)printf("impossible\n");

    else printf("%d\n",ans);

    return 0;

    }

    b7fed736d440a473e21910f12e7cbe34.gif

    与Dijkstra类似,Prim算法也可以用堆优化,优先队列代替堆,优化的Prim算法时间复杂度O(mlogn)模板(图的存储方式为前向星):

    bc6aac9b1e41b5a864079197e30a12a6.gif

    void Prim_heap(int point)

    {

    memset(dis,0x1f,sizeof(dis));

    priority_queue > q;

    dis[point]=0;

    q.push(make_pair(0,1));

    while(!q.empty())

    {

    int k=q.top().second;

    q.pop();

    v[k]=1;

    for(int i=h[k];i!=-1;i=edge[i].next)

    {

    int to=edge[i].to,w=edge[i].w;

    if(!v[to]&&dis[to]>w)

    {

    dis[to]=w;

    q.push(make_pair(-dis[to],to)); //优先队列大根堆变小根堆小骚操作:只需一个‘-’号;

    }

    }

    }

    for(int i=1;i<=n;i++)if(dis[i]==0x1f1f1f1f)flag=false; //判断是否不存在最小生成树

    return ;

    }

    3c92ac50eb520dce8680e402be7e6c57.gif

    二、Kruskal算法

    相比于Prim算法,更常用的还是Kruskal,其原因在于Kruskal算法模板的代码量小而且思路易理解。

    算法思路:先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止。

    步骤:

    新建图G,G中拥有原图中相同的节点,但没有边;

    将原图中所有的边按权值从小到大排序;

    从权值最小的边开始,如果这条边连接的两个节点于图G中不在同一个连通分量中,则添加这条边到图G中;

    重复3,直至图G中所有的节点都在同一个连通分量中。

    简单来说就是以边为主导地位,每次选择权值最小的边,判断该边连接的两点是否连通,若不连通,则合并两点(合并操作以并查集实现)。记录合并的次数,当次数等于n-1时结束。

    代码如下:时间复杂度O(mlogm)

    4cf229b5d6ed93a117fc5b26da35337b.gif

    #include

    #include

    #include

    #include

    using namespace std;

    const int N = 100000+10, M = 200000+10;

    struct Edge{

    int u,v,w;

    bool operator < (const Edge &E)const

    {

    return w

    }

    }edge[M];

    int fa[N];

    int n,m,cnt,ans;

    int find(int x)

    {

    if(fa[x]==x)return x;

    else return fa[x]=find(fa[x]);

    }

    int main()

    {

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)fa[i]=i;

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

    {

    int a,b,c;scanf("%d%d%d",&a,&b,&c);

    edge[i].u=a;edge[i].v=b;edge[i].w=c;

    }

    sort(edge+1,edge+m+1);

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

    {

    int u=find(edge[i].u),v=find(edge[i].v),w=edge[i].w;

    if(u!=v)

    {

    cnt++;

    fa[u]=v;

    ans+=w;

    }

    }

    if(cnt==n-1)printf("%d\n",ans);

    else printf("impossible\n");

    return 0;

    }

    062e9039c309f27e76b419767d113bba.gif

    三、Prim,Prim_heap,Kruskal算法时间复杂度比较

    参考了G机器猫的博客

    7d32e09c56b60618d3bcfdd011fdd5d1.png

    e8644bdfe59a6085f63834d93bc179f2.png

    abeb507c66af87417b3bfd817d1ac9ae.png

    dc67226491597d1a9207fc4187811052.png

    bf0b73c2ffa27272a26f84944da9c717.png

    结论:

    1.Prim在稠密图中比Kruskal优,在稀疏图中比Kruskal劣。

    2.Prim_heap在任何时候都有令人满意的的时间复杂度,但是代价是空间消耗极大。(以及代码很复杂>_

    但值得说一下的是,时间复杂度并不能反映出一个算法的实际优劣。

    竞赛题一般给的都是稀疏图,选择Prim_heap即可;如果觉得代码量太大,想要在Prim与Kruskal算法中选一个,那就选择Kruskal算法。

    展开全文
  • 这里写目录标题算法时间复杂度数据的存储结构 算法时间复杂度 1<log2n<n<n2 数据的存储结构 数据的存储结构一般有四种方式: 1、顺序存储方式 2、链式存储方式 3、索引存储方式 4、散列存储方式 计算机...

    Hello,你好呀,我是大白(●—●)

    算法时间复杂度

    1<log2n<n<n2

    数据的存储结构

    数据的存储结构一般有四种方式:
    1、顺序存储方式
    2、链式存储方式
    3、索引存储方式
    4、散列存储方式

    计算机图灵奖获得者N.Wirth曾提出一个著名公式:算法+数据结构=程序
    算法是解决程序问题和流程步骤(顺序结构/分之结构/循环结构),数据结构:将数据按照某种特定结构保存

    数据结构主要研究的是:数据的逻辑结构,即数据关系之间的逻辑关系;
    数据的存储结构,即数据的逻辑结构在计算机中的表示;
    操作算法,即数据的插入、删除、修改、查询和排序等。

    数据元素时组成数据的基本单位,其下属还可分为若干个数据项,数据项是数据具有意义的最小单位;
    在数据库中,数据项又称为字段/域。它是数据的不可分割的最小标识单位。
    数据,数据元素,数据项构成了数据组织的三个层。其中,数据元素是数据中的一个"个体",是数据的基本单位,
    同时也是数据结构中讨论的基本单位,数据元素是数据项的集合。

    无论是双向循环链表还是单链表,节点的任何增删操作,都应该遵循"先连接,后断点"的原则,双向链表
    插入首先将新加入的节点的两个指针指向正确位置即q->prior=p;q->next=p->next;
    然后将原链表后面的那个节点前去指向新节点,p->next->prior=q;将原链表前面的节点指向新节点p->next=q;
    最重要的顺序是:在q与原链表后面那个节点建立双向连接之前不可以改变p->next否则原链表断掉无法找到后面那

    大白陪你共同进步!
    在这里插入图片描述

    展开全文
  • 文章和资源同步更新至微信公众号:算法工程师之路8月份会在公众号推出每日算法题,值得期待哦~上一篇文章,...这是图论中一个经典问题,可以使用Kruskal和Prim两种算法来进行实现!什么是最小生成树在给定一张无向图...

    0df1216e93c4848264c9bc3a33522b77.png
    文章和资源同步更新至微信公众号:算法工程师之路
    8月份会在公众号推出每日算法题,值得期待哦~

    上一篇文章,我们讲了图的创建和遍历,其中遍历的算法主要有BFS(广度优先算法)和DFS(深度优先算法)两种,并且DFS算法对很多问题都有很好的启示!而今天我们要说一个非常实用的算法——最小生成树的建立!这是图论中一个经典问题,可以使用Kruskal和Prim两种算法来进行实现!

    什么是最小生成树

    在给定一张无向图,如果在它的子图中,任意两个顶点都是互相连通,并且是一个树结构,那么这棵树叫做生成树。当连接顶点之间的图有权重时,权重之和最小的树结构为最小生成树!

    开启图结构的学习:图的创建和遍历​mp.weixin.qq.com
    5e7819bcc563e02bfa62b1a9fddb9cf4.png

    在实际中,这种算法的应用非常广泛,比如我们需要在n个城市铺设电缆,则需要n-1条通信线路,那么我们如何铺设可以使得电缆最短呢?最小生成树就是为了解决这个问题而诞生的!

    d92a5c6861464ebce3e0901a5f5da237.png
    最小生成树

    如上图所示,一幅两两相连的图中,找到一个子图,连接到所有的节点,并且连接边的权重最小(也就是说边的数量也是最小的,这也保证了其是树结构).

    Kruskal算法(克鲁斯卡算法)

    Kruskal算法是一种贪心算法,我们将图中的每个edge按照权重大小进行排序,每次从边集中取出权重最小且两个顶点都不在同一个集合的边加入生成树中!注意:如果这两个顶点都在同一集合内,说明已经通过其他边相连,因此如果将这个边添加到生成树中,那么就会形成环!这样反复做,直到所有的节点都连接成功!

    c76ac61be5f15bdf30a0ea3332202618.png

    在这个算法中,最重要的一环就是判断两个节点在不在同一个集合内,很多人想,那你直接用一个set来保存不就好了?这是思路显然不行,因为假设A和其他三个节点相连,同属一个集合,而B和另外三个节点相连,同属一个集合,那么我们将A和B取并集时,是将这两组数据合并一起的,如果使用set,那么当数据量大时还需要遍历,复杂度就会很高,因此使用并查集就会效率快很多了

    并查集详解和STL中的自定义哈希​mp.weixin.qq.com
    ff67987ddb99fe106f70b9b65c106700.png
    1. 对所有节点遍历建立并查集,按照边的权重建立最小堆
    2. 取出最小堆堆顶数据,并判断两端节点是否在同一集合
    3. 如不在,则将这两个节点添加到同一集合,接着将边加入生成边,如在,则不进行操作,为无效边
    4. 重复上面的操作,直到所有的边都检查完
    unordered_set

    Prim算法(普里姆算法)

    Prim算法是另一种贪心算法,和Kuskral算法的贪心策略不同,Kuskral算法主要对边进行操作,而Prim算法则是对节点进行操作,每次遍历添加一个点,这时候我们就不需要使用并查集了。具体步骤为:

    e6bfc9764bb872afe78cbbe2b1d3cb97.png
    1. 建立边set用来存放结果,建立节点set用来存放节点同时用于标记是否被访问过,建立边的最小堆
    2. 开始遍历所有节点,如果没有访问,则添加到节点set,然后将其相连的边入堆。
    3. 从堆中取最小的边,然后判断to节点是否被访问过,如果没有,将这个边加入生成树(我们想要的边),并标记该节点访问。
    4. 然后将to节点所相连的边添加到最小堆中,不然这个网络就不会向外扩展了(这个步骤是必须的)。
    5. 循环上面的操作,直到所有的节点遍历完。

    注意:对于单连通,从一个节点出发就可以直接找到完整的最小生成树,因此最外的for循环也可以为一个顺序结构,但多连通,就需要从不同的节点出发了!!!

    unordered_set<Edge, EdgeHash, EdgeEqual> primMST(Graph graph){
        // 装边的最小堆
        auto cmp = [](const Edge& e1, const Edge& e2){
            return e1.weight > e2.weight;
        };
        priority_queue<Edge, vector<Edge>, decltype(cmp)> smallQueue(cmp);
        // 判断节点是否访问过
        unordered_set<Node, NodeHash, NodeEqual> node_set;
        unordered_set<Edge, EdgeHash, EdgeEqual> result;
        for(auto ite: graph.nodes){
            if(node_set.find(*ite.second) == node_set.end()){
                // 如果没有访问,将其标记为访问过,并把它对应的边放入最小堆
                node_set.insert(*ite.second);
                for(Edge* edge: ite.second->edges){
                    smallQueue.push(*edge);
                }
                // 在当前这个图中寻找最小生成树
                while(!smallQueue.empty()){
                    // 从堆中取出一个最小权重边,并取出对应节点
                    Edge help_edge = smallQueue.top();
                    smallQueue.pop();
    
                    Node edge_to = *(help_edge.to);
                    // 然后判断这个节点是否被访问过,如果没有则将这个边加入边集
                    if(node_set.find(edge_to) == node_set.end()){
                        result.insert(help_edge);
                        node_set.insert(edge_to);   // 标记edge_to也已经访问过了
                        for(Edge *newEdge: edge_to.edges){
                            smallQueue.push(*newEdge);
                        }
                    }
                }
            }
        }
        return result;
    }
    

    那么对于这两种算法,我们应该用哪种呢?记得某个人说过这句话,算法没有优劣,每个算法都有它的使用场景,在对的场合使用对的算法,这才是算法工程师应该做的事情!

    由于Kruksal算法是对边进行操作,先取出边,然后判断边的两个节点,这样的话,如果一个图结构非常的稠密,那么Kruksal算法就比较慢了,而Prim算法只是对节点进行遍历,并使用set进行标记,因此会相对于Kruksal算法,在稠密图方面好很多,因此Kruksal算法常用于稀疏图,而Prim算法常用于稠密图!

    资源分享

    以上完整代码文件(C++版),文件名为:最小生成树(Kruskal算法和Prim算法),请关注我的个人公众号 (算法工程师之路),回复"左神算法基础CPP"即可获得,并实时更新!希望大家多多支持哦~

    公众号简介:分享算法工程师必备技能,谈谈那些有深度有意思的算法,主要范围:C++数据结构与算法/深度学习(CV),立志成为Offer收割机!坚持分享算法题目和解题思路(Day By Day)

    a4e68a0aa995288d4a76b3fdcc46e3ff.png
    算法工程师之路
    展开全文
  • 最小生成树之PRIM算法C++代码实现: #include <iostream> #include <vector> using namespace std; void prim(vector<vector<int>>& VGraph, vector<int>& lowcost, vector&...

    最小生成树之PRIM算法C++代码实现:

    #include <iostream>
    #include <vector>
    using namespace std;
    
    void prim(vector<vector<int>>& VGraph, vector<int>& lowcost, vector<int>& closest, vector<bool>& visited)  
    {
    	int size = lowcost.size(); //M
    	visited[0] = true;  //从顶点0出发构造最小生成树
    	for (int i = 1; i < size; i++)
    	{
    		lowcost[i] = VGraph[0][i];  //初始化为顶点0到其他顶点i的权
    		closest[i] = 0;  //i节点依附的节点
    		visited[i] = false;
    	}
    	int weight = 0; //最小生成树权值
    
    	cout << "输出生成树上各条边:" << endl;
    	//m-1条边,循环m-1次,每次找到一条边
    	for (int i = 0; i < size-1; i++)
    	{
    		int min = 99999;
    		int index = 1;
    		//寻找具有最小代价的边
    		for (int j = 0; j < size; j++)
    		{
    			//从刚并入U的顶点到其他点j (j必须未被访问过)的权中选出具有最小代价的边
    			if (lowcost[j] < min && !visited[j])
    			{
    				min = lowcost[j];
    				index = j;
    			}
    		}
    		weight += min;
    		//打印每次选择的边
    		cout << "(" << closest[index] << "," << index << ")" << endl;
    
    		visited[index] = true;
    		//因为新加入了index点,所以要查找新加入的index点到未在S中的点K中的权值是不是可以因此更小
    		for (int j = 1; j < size; j++)  
    		{
    			if ((VGraph[index][j] < lowcost[j]) && (!visited[j]))  //lowcost表示从已知树到某一点所需付出的最小权值
    			{
    				lowcost[j] = VGraph[index][j]; //更新刚加入的index点到其他j点的权值
    				closest[j] = index;  //将j节点依附的节点修改为index
    			}
    		}
    	}
    	cout << "\n最小生成树权值为:" << weight << endl;
    }
    int main()
    {
    	int M, N;   //M为顶点数  N为边数
    	cin >> M >> N;  
    	vector<vector<int>> VGraph(M,vector<int>(M)); //图的邻接矩阵
    	vector<int> lowcost(M);  //刚选中并入U的顶点到其他顶点的权,初始为顶点0到其他点的权,因为从0出发
    	vector<int> closest(M);  //记录每个节点依附的具有最小代价的节点,由此可得到最小生成树上的所有边
    	vector<bool> visited(M);  //标记节点是否已访问
    	//数组表示  邻接矩阵初始化
    	for (int i = 0; i < M; i++)
    	{
    		for (int j = 0; j < M; j++)
    		{
    			VGraph[i][j] = 99999;
    		}
    	}
    	for (int i = 0; i < N; i++)
    	{
    		int a, b;  //两个顶点
    		cin >> a >> b;
    		int length;  //权
    		cin >> length;
    		VGraph[a][b] = VGraph[b][a] = length; //初始化图各条边
    	}
    	prim(VGraph, lowcost, closest, visited);
    }
    //0 1 6 0 2 1 0 3 5 1 2 5 1 4 3 2 3 5 2 4 6 2 5 4 3 5 2 4 5 6 
    

    在这里插入图片描述
    复杂度分析:

    假设网中有m个顶点,则第一个初始话的循环语句频度为m; 第二个找m-1条边的循环语句频度为m-1, 其中有两个内循环:其一是求具有最小代价的边,其频度为m, 其二是重新选择具有最小代价的边,其频度为m。 因此,PRIM算法总的时间复杂度为O(m^2), 与网中的边数无关,因此适用于求边稠密的网的最小生成树。

    Kruskal算法

    并查集实现

    
    //并查集
    vector<int> father(100);
    vector<int> Rank(100);
    //初始化
    void init(int n){  //n个节点
        for(int i=0;i<n;++i){
            father[i] = i;
            Rank[i] = 1;
        }
    }
    //查询节点的根节点(路径压缩)
    // int find(int x){
    //     if(x==father[x]){
    //         return x;
    //     }
    //     father[x] = find(father[x]); //查询过程中把沿途的每个节点的父节点都设为根节点
    //     return father[x];
    // }
    
    //非递归
    int find(int x){
        int root = father[x];
        while(root != father[root]){  //找根节点
            root = father[root];
        }
        //将路径上的所有节点的父节点设为根节点
        while(x != root){
            int t = father[x];
            father[x] = root;
            x = t;
        }
        return root;
    }
    
    //合并
    void unit(int x,int y){
        int fx = find(x);
        int fy = find(y);   //先找到两个根节点
        if(Rank[fx]<=Rank[fy]){
            father[fx] = fy;
        }
        else{
            father[fy] = fx;
        }
        if(Rank[fx]==Rank[fy] && fx != fy){
            Rank[fy]++;
        }
    }
    
    struct edge{
        int start;
        int end;
        int weight;
        edge(){}
        edge(int s,int e,int w):start(s),end(e),weight(w){}
    };
    
    bool cmp(edge& a,edge& b){
        return a.weight<b.weight;
    }
    
    int main(){
    	int m,n;  //顶点,边
        cin>>m>>n;
        // vector<vector<int>> G(m,vector<int> (m,INT_MAX));
        vector<edge> G;
        //图初始化
        int a,b,w;
        for(int i=0;i<n;++i){
            cin>>a>>b>>w;
            // G[a][b] = G[b][a] = length;
            edge e(a,b,w);
            G.push_back(e);
        }
        //kruskal
        vector<int> res;  //存最小生成树的每条边的索引
        int res_weight = 0;
        sort(G.begin(),G.end(),cmp);  //边排序
        init(m);  //并查集初始化    
        int nEdge = 0;  //最小生成树中的边数:m-1条
        for(int i = 0; i < n && nEdge != m-1; ++i){
            if(find(G[i].start) != find(G[i].end)){
                unit(G[i].start,G[i].end);
                res.push_back(i);
                res_weight += G[i].weight;
                nEdge++;
            }
        }
        //如果加入边的数量小于m - 1,则表明该无向图不连通,等价于不存在最小生成树
        if(nEdge < m-1){
            cout<<"error!"<<endl;
            return 0;
        }
        for(int i=0;i<m-1;++i){
            cout<<G[res[i]].start<<" "<<G[res[i]].end<<ends;
        }
        cout<<endl;
        cout<<res_weight<<endl;
        return 0;
    }
    
    
    展开全文
  • 数据结构中算法复杂度总结

    千次阅读 2020-10-16 19:36:25
    采用邻接表存储方式时,每个顶点均需搜索一次(或入队一次),故时间复杂度为0(V),在搜索任一顶点时,顶点后边的链表都要访问一次,在搜索完V个顶点后,边表也就都访问了,故时间复杂度为O(E),算法总的时间复杂度为O(V+E)...
  • 评测环境:WindowsXP,FreePascal2.40,Pentium(R) Dual-Core CPU T4300@...2.Prim+Heap在任何时候都有令人满意的的时间复杂度,但是代价是空间消耗极大。【以及代码很复杂>_<】 3.时间复杂度并不能反映出...
  • prim算法 /* O(n^2)解法 */ #include&lt;bits/stdc++.h&gt; using namespace std; const int maxn = 100; int p[maxn][maxn]; int vis[maxn]; int d[maxn];//d[i]表示终点为i的最短距离 int n,m; int ...
  • 查了两个小时的prim堆优化,发现普通堆优化之后为O(ElgE),对于稠密图来说,较朴素prim复杂度还要高。 对于稀疏图,直接kruskal就可以了。 kruskal复杂度O(ElgV)。 朴素prim复杂度O(V^2)。 而斐波那契堆优化的prim,...
  • prim算法

    2020-12-24 17:57:46
    算法分析的一般步骤:1、文字描述:如果一个算法文字...(注意:prim算法适合稠密图,其时间复杂度为O(n^2),其时间复杂度与边得数目无关,而kruskal算法的时间复杂度为O(eloge)跟边的数目有关,适合稀疏图。)算法...
  • 考研中的算法时间复杂度求解

    千次阅读 2016-04-13 17:29:41
    考研中的算法时间复杂度求解今天刚刚开始复习了考研的数据结构,结果在第一篇绪论就遇到问题了,哈哈哈,就是求解算法时间复杂度问题,刚一开始有点蒙,不知道怎么做,相信很多考研的小伙伴一开始都会遇到这个问题...
  • prim算法也是一种贪心算法。开始时,最小生成树(MST)为空(不包含任何节点),然后维持两个集合,一个集合是包含已经进入MST中的节点,另一个集合时包含未被加入到MST中的节点。在算法的每个步骤中,从连接这两个...
  • 最小生成树算法,时间复杂度T(n)=O(V^2) V为顶点数目,受边的影响不大,适合于边比较多的图(稠密图),在稀疏图时,Kruscal复杂度更低,我们可以使用堆优化的prim算法达到与Kruscal一样的复杂度prim算法设计思路(O...
  • 优先权实现的prim 算法复杂度的分析  如果直接从代码来进行分析,我认为比较困难,所以直接从宏观上进行分析。 使用优先权队列,假设极端情下每条边都会进入队列以替代原来权值较大的边,进行建堆和调整,对m条边...
  • 最小生成树之Prim算法分析 最小生成树问题 设G=(V,E)是无向连通带权图,即一个网络。图中每一条边(u,v)的权是c[u][v],表示联通u与v的代价。 如果G的子图T是一棵包含G的所有顶点的树,则称T为G的生成树。生成树上各...
  • Prim算法 Prim 算法和 Dijkstra 算法很相似,都是从一个点开始把点不停加入到点集合。 Prim算法适合于边疏密的图。 首先定义邻接矩阵、标志数组和一个不断更新的 minCost 数组用来求当前点集到其他点的最小权值...
  • 最小生成树之prim算法(转载出处) 边赋以权值的图称为网或带权图,带权图的生成树也是带权的,生成树T各边的权值总和称为该树的权。  最小生成树(MST):权值最小的生成树。  生成树和最小生成树的应用:要...
  • 图 - 最小生成树(Prim & Kruskal)

    千次阅读 2021-03-13 20:11:50
    prim算法是从顶点出发,在根结点的基础上建起一棵树。@pdai¶ 最小生成树相关名词 连通图: 在无向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该无向图为连通图。强连通图: 在有向图中,若任意两个顶点vivi与...
  • 算法导论 23.2 Prim算法

    2018-07-08 13:56:53
    一,Prim算法的思想 Prim算法和Kruskal算法一样对安全边的选择规则作出了细化,Prim每一步在连接集合A和A之外的结点的所有边中选择一条轻量边的结点信息加入A中,直到A中的结点覆盖所有结点。二,Prim算法介绍 ...
  • 最小生成树-Prim算法

    万次阅读 多人点赞 2018-02-07 22:26:23
    表示的话,Prim算法时间复杂度可缩减为O(E log V),其中E为连通图的边数,V为顶点数。  如果使用较复杂的 斐波那契堆 ,则可将运行时间进一步缩短为O(E + V log V),这在连通图足够密集时(边较多,即 E满足 ...
  • 文章目录Prim算法一、最小生成树(Minimum Spanning Tree,MST)二、Prim算法1、简介2、描述3、示例4、算法实现5、测试 Prim算法 一、最小生成树(Minimum Spanning Tree,MST) 在一给定的无向图G = (V, E) 中,(u, v...
  • 最小生成树 Prime算法 + 时间复杂度

    万次阅读 2016-10-08 17:13:03
    主要就是以点作为目标来考虑, 而不是以边进行考虑。 由于思想一样,所以时间复杂度分析的结果与Dijkstra算法的一模一样。
  • 最小生成树之Prim算法

    万次阅读 2015-08-23 07:28:33
    普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家...
  • Prim算法

    2016-03-24 22:51:41
    void Prim(int v0) { MinEdgeArray MinEdges; int i,j,k; visited[v0]=1; for(i=1;i;i++) { k=Get_MinEdge(MinEdges); visited[k]=1; change_MinEdges_with(MinEdges,k); } } //输出最小生成树 void ...
  • Prim算法(普里姆算法)

    千次阅读 2016-06-24 11:02:18
    普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。 算法描述 1).输入:一...
  • 在图采用邻接表存储时,求最小生成树的Prime算法时间复杂度为? A o(n^2) B o(n^3) C o(n) D o(n+e) 答案是o(n+e)。。。不理解..求过程

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,919
精华内容 3,167
关键字:

prim算法时间复杂度

友情链接: nun_jr77.zip