C++不带权无向网的邻接表的最小生成树的实现所用算法

写了一段不带权无向网邻接表的代码,用算法实现最小生成树,但是Kruskal和Prim两个算法得出的是不一样的,Kruskal是正确的,求解

2个回答

一个图的最小生成树结果是不唯一的,虽然两种算法得出的结果可能不一样但是肯定都是正确的,我觉着有以下两种可能。
1.结果要求的最小生成树可能有某种规则,以至于prime得出的结果虽然也是最小生成树但是不符合这种规则。
2.你prime算法写错了。
这是最好自己设计几个图,输入之后打印中间输出看一下结果,看一看是哪里错了。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
图基本算法 最小生成树 Prim算法(邻接表/邻接矩阵+优先队列STL)
这篇文章是对《算法导论》上Prim算法求无向连通图最小生成树的一个总结,其中有关于我的一点点小看法。   最小生成树的具体问题可以用下面的语言阐述:     输入:一个无向带权图G=(V,E),对于每一条边(u, v)属于E,都有一个权值w。     输出:这个图的最小生成树,即一棵连接所有顶点的树,且这棵树中的边的权值的和最小。   举例如下,求下图的最小生成树:
最小生成树Prim算法实现(采用邻接表存储)C++实现
// Prim算法实现(采用邻接表存储).cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdafx.h" #include #define MAX 100 #define Infinity 65535 typedef int WeiType; using na
C++无向带权图与最小生成树
C++无向带权图与最小生成树参考《算法》一书,C++语言基于邻接表实现了无向带权图以及Prim算法得到图的最小生成树。图的实现在无向图的基础上增加权重即可,可参考《C++邻接表与图》。Prim算法简要说来,可写成如下伪代码:for(int i=0;i<V;i++) { PrimVisit(i); //插入点并更新权重,同时得到更新后距离图最近的点 }具体原理不再详述,可参考《算法》的讲解,此处记
<C/C++图>最小生成树:Prim算法
一,最小生成树算法基本概念 最小生成树是数据结构中图的一种重要应用,它的要求是从一个有n个节点的带权完全图中选择n-1条边并使这个图仍然连通(也即得到了一棵生成树),同时还要考虑使树的权之和最小。最小生成树可以用,Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。
图算法 最小生成树邻接表 Kruskal算法(并查集)
之前对最小生成树Prim算法进行了一定的总结,并给出了代码实现,详见:图的最小生成树,Prim实现。 一、介绍    由于忙于各类事务,在算法方面的学习有所停滞,现在将求最小生成树的另外一种算法补上,也就是Kruskal算法。有关最小生成树算法正确性的证明见上面链接。   Kruskal算法是一种实现起来较为简单,比较容易理解的算法,在图较为稀疏时能够获得很好的性能,
最小生成树----Prim算法(邻接矩阵存图)
起初找任意一个点作为初始点,成为其他所有点的前置点并且更新dis数组,并将这个点放入集合内(vis标记),然后找到所有点到其前置点最短的那个,线段即为局部最优加入到sum内,线段终点也加入到集合里,然后遍历所有不在集合内的点,如果遍历到的点到它前置点的距离大于到线段终点的距离,就将线段终点作为其前置点并更新dis数组,依次进行就是非优先队列版的prim算法。代码:#include <cstdio>
邻接矩阵存储带权值的无向图
vertex.h#pragma onceclass vertex { public: char data;//节点用字符表示 vertex(char c=' '); bool isVisited;//是否被访问过 void visited(); };vertex.cpp#include"vertex.h" # include<iostream> using names
邻接表的最小生成树kruskal算法
邻接表最小生成树Kruskal
Prim算法——求无向图的最小生成树
1212 无向图最小生成树基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注N个点M条边的无向连通图,每条边有一个权值,求该图的最小生成树。Input第1行:2个数N,M中间用空格分隔,N为点的数量,M为边的数量。(2 &amp;lt;= N &amp;lt;= 1000, 1 &amp;lt;= M &amp;lt;= 50000) 第2 - M + 1行:每行3个数S E W,分别表示M...
数据结构:不带权有向图的邻接矩阵和邻接表储存及求出入度实现
14.假设不带权有向图采用邻接矩阵G存储,设计实现以下功能的算法。 (1) 求出图中每个顶点的入度。 (2)求出图中每个顶点的出度。 (3)求出图中出度为0的顶点数。 15. 假设不带权有向图采用邻接表G存储,设计实现以下功能的算法。 (1) 求出图中每个顶点的入度。 (2)求出图中每个顶点的出度。 (3)求出图中出度为0的顶点数。 #include #include #de
最小生成树——Kruskal算法(C语言版)
1,问题描述 设G=(V,E)是无向连通带权图,如果G的一个子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树的各边权的总和称为该生成树的耗费,求在G的所有生成树中耗费最小的最小生成树。 2,算法思想 (1)将代价树中权值非0的所有的边进行小顶堆排序,依次存入到road[]数组中,然后将road[]进行倒置,注意在进行排序时,按照road[i]的权值进行排序,然后记
无向图的邻接表表示法
/*无向图的邻接表表示法*/ #include<stdio.h> #define vnum 10 typedef struct arcnode { int adjvex; /*下一条边的顶点编号*/ struct arcnode * nextarc; /*指向下一条边的指针*/ }ArcNode; typedef s
无向连通网的最小生成树算法[第2部分]
4.2 primMst算法及时间复杂度分析void primMst(int **AdjMatrix,EDGENODE *edgeSet,int n,int start) { int iter,minPos,to; EDGENODE edge; initEdgeSet(AdjMatrix,edgeSet,n,start); //初始化边集合 fo
最小生成树 prim算法实现(利用图的邻接矩阵来存放图)
定义:最小生成树并不像数据结构中的树一样,而是从图演化而来,生成树有DFS生成树,BFS生成树,最小生成树等。 所谓最小生成树,就是在有N个节点的连通图中,找出N-1条边使N个点仍然连通,并且个边权值和最小。 代码如下: /**********计算出图的最小生成树的代价,不能直达的点之间的权值设为100,假设所有点之间的 权值不超过99,代码暂时显示出生成树的路径貌似有bug********
【数据结构与算法】带权有向图
MyGraph.h#pragma once #include <iostream> #include <stack> #include <queue> using namespace std;// 邻接矩阵 // 带权有向图const int MAXSIZE = 20; const int INFINITE = 100;template <class T> class CMyGraph { publ
无向带权图的邻接矩阵表示法
/*无向带权图的邻接矩阵表示法*/ #include<stdio.h> #define vnum 20 typedef struct gp { int vexs[vnum]; /*顶点信息*/ int arcs[vnum][vnum]; /*邻接矩阵*/ int vexnum,arcnum; /*顶
邻接表-建立无向图、无向网、有向图、有向网
#include#include#define MAX_VERTEX_NUM 20#define OK  1#define ERROR 0typedef int InfoType;       /* 该弧相关信息的指针类型 */typedef char VertexType;      /* 顶点的类型 */typedef struct ArcNode       /* 弧结点的结构 */
C语言:实现图的邻接表存储表示
// 图的数组(邻接矩阵)存储表示 #include #include #include #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20 typedef int InfoType;
最小生成树(prime 算法和克鲁斯卡尔算法)
最小生成树-Prim算法和Kruskal算法  分别适用于不同类型的图结构:prime算法适合于边多而定点少的,库鲁萨卡尔算法适合于边少定点多的情况。 Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其
基于邻接矩阵和邻接表的两种方法实现无向图的BFS和DFS
广度优先搜索(Breadth-First-Search)和深度优先搜索(Deep-First-Search)是搜索策略中最经常用到的两种方法,特别常用于图的搜索. BFS的思想:       从一个图的某一个顶点V0出发,首先访问和V0相邻的且未被访问过的顶点V1、V2、……Vn,然后依次访问与V1、V2……Vn相邻且未被访问的顶点。如此继续,找到所要找的顶点或者遍历完整个图。我们采用
[C++]C++ STL Dijkstra算法 带权有向图(邻接表)单源最短路径求解
单源最短路径问题求解带权有向图(邻接表表示法)完整源码#include <iostream> #include <vector> #include <tuple> #include <map> using namespace std;map<int , vector<tuple<int, int, double>>> EWD;int main() { int V, E; cin >>
【数据结构和算法10】 带权图
    上一节我们已经看到了图的边可以有方向,这一节里,我们将探讨边的另一个特性:权值。例如,如果带权图的顶点代表城市,边的权可能代表城市之间的距离,或者城市之间的路费,或者之间的车流量等等。     带权图归根究底还是图,上一节那些图的基本操作,例如广度优先搜索和深度优先搜索等都是一样的,在这一节里,我们主要来探讨一下带权图的最小生成树最短路径问题。小生成树     首先探讨下最小生成树问题...
设计一个算法,采用BFS方式输出图G中从顶点u到v的最短路径(不带权的无向连通图G采用邻接表存储)
思想:图G是不带权的无向连通图,一条边的长度计为1,因此,求带顶点u和顶点v的最短的路径即求顶点u和顶点v的边数最少的顶点序列。利用广度优先遍历算法,从u出发进行广度遍历,类似于从顶点u出发一层一层地向外扩展,当第一次找到顶点v时队列中便包含了从顶点u到顶点v最近的路径,如图所示,再利用队列输出最路径(逆路径),所以设计成非循环队列。
数据结构.图.无向带权&邻接矩阵.最短路径Dijkstra算法
图的应用实在很广,课堂所学实为皮毛 考虑基于邻接矩阵的无向带权图,边的权值的典型意义就是路途的长度,从顶点u到顶点v的边权值为w,可以表示城市u到城市v之间路长为w。 最短路径问题考虑的就是从某个顶点出发到其他任何一个顶点所经过的最短的路径。 Dijkstra迪杰斯特拉算法 根据起点V0,最终得到的是一个从V0到其他顶点的路径按路径长度依次递增的次序产生最短路径,可知一共有(顶点总数-1)条路径,分
【啊哈!算法】算法8:巧妙的邻接表(数组实现)
之前我们介绍过图的邻接矩阵存储法,它的空间和时间复杂度都是N2,现在我来介绍另外一种存储图的方法:邻接表,这样空间和时间复杂度就都是M。对于稀疏图来说,M要远远小于N2。先上数据,如下。   4 5 1 4 9 4 3 8 1 2 5 2 4 6 1 3 7           第一行两个整数n m。n表示顶点个数(顶点编号为1~n),m表示边的条数。接下来m行
有向图无向图领接表深度优先广度优先最小生成树
#include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXVEX 100 #define MAXEDGE 100 #define INFINITY 65535 #define MAXSIZE 100 typedef int Status;
构建有向带权图用邻接矩阵求最短路径
#include <bits/stdc++.h> #include <limits> using namespace std; int main() { int tu[100][100]={0}; int du[100]={0}; int num; cout<<"输入定点数:"<<endl; cin>>num; int x,y,t; for(i
数据结构与算法之带权图的最小生成树
http://blog.csdn.NET/xinzhi8/article/details/62222154 图介绍与深度优先搜索   http://blog.csdn.Net/xinzhi8/article/details/62222154 广度优先搜索   http://blog.csdn.net/xinzhi8/article/details/63682781 有向图的拓扑排序
图的邻接矩阵c语言表示(无向网)---《数据结构》算法7.2
邻接矩阵是图的一种表示法,构造具有n个顶点和e条边的无向网G的时间复杂度为(n^2+e*n),代码如下:#include #define infinity 2000000000 #define MAX_VERTEX_NUM 100 typedef enum{DG,DN,UDG,UDN} GraphKind; typedef struct { int vexs[MAX_VERTEX_NUM];
无向图的深度和广度优先搜索遍历(C)
无向图的深度和广度优先搜索遍历(C)   以邻接表作为图的存储结构,实现连通无向图的深度优先和广度优先遍历。以指定的结点作为起点,分别输出每种遍历下的结点访问序列。   #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #d
最小生成树(带权无向图)
在一个无向图中找出一棵最小生成树:      一个无向图G的最小生成树就是由该图的那些连接G的所有顶点的边构成的树,且其总价值最低,最小生成树存在当且仅当G是连通的。在最小生成树中边的条数是|V|-1,并且无圈。      对于任一个生成树T,如果将一条不属于T的边e添加进来,则产生一个圈。如果从该圈中除去任意一条边,则又恢复生成树的特性。如果边e的值比除去的边的值低,那么新的生成树的值就比原生成...
带权图的多种算法(有向图,无向图,Dijkstra算法,到每个顶点的最短距离算法,佛洛依德算法(Floyd),找出每对顶点的最短路径,带权重无向图最小生成树,prim算法,Kruskal算法求最小生成树)java实现,有注释
带权图的多种算法(有向图,无向图,Dijkstra算法,到每个顶点的最短距离,佛洛依德算法(Floyd),找出每对顶点的最短路径,带权重无向图最小生成树,prim算法,Kruskal算法求最小生成树)java实现, 有注释,简单轻松搞懂图,全部是自己实现,
Kruskal(克鲁斯卡尔) 最小生成树 算法详解+模板
最小生成树在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树。 例如,对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。 克鲁斯卡尔算法介绍 克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路。
图的定义,存储结构是邻接矩阵(无向图,包含带权图)
//头文件 //Edge.h #ifndef EDGE_H #define EDGE_H #include using namespace std; template class Edge{ public: //边的起始与终点 int start, end; //权重 T weight; Edge(); Edge(int st, int en, T wei); bool operat
最短路径(邻接表)-Dijkstra算法
最短路径(邻接表)-Dijkstra算法:生成的图采用邻接表的存储方式。        具体的实现代码如下: package com.threeTop.www; import java.util.Hashtable; import java.util.Stack; /** * 邻接表存储方式的Dijkstra算法 * @author wjgs * */ public class
最小生成树的prime算法
/**   * 最小生成树的prim算法   * @author liuy   */   public class Prim {              public static void prim(int num, float[][] weight) {  //num为顶点数,weight为权           float[] lowcost = new float[num 
java 普里姆(Prim)算法求图的最小生成树
1. 基本思想: 设G=(V,E)是连通网,T=(U,D)是最小生成树,V,U是顶点集合,E,D是边的集合 ①若从顶点u开始构造最小生成树,则从集合V中取出顶点u放入集合U中,标记顶点v的visited[u]=1; ②若集合U中顶点ui与集合V-U中的顶点vj之间存在边,则寻找这些边中权值最小的边,但不能构成回路,将顶点vj加入集合U中,将边(ui,vj)加入集合D中,标记visited[vj]=1
无向带权图的最小生成树算法——Prim及Kruskal算法思路
边赋以权值的图称为网或带权图,带权图的生成树也是带权的,生成树T各边的权值总和称为该树的权。    最小生成树(MST):权值最小的生成树。    生成树和最小生成树的应用:要连通n个城市需要n-1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。    构造网的最小生成树必须解决下面两个问题:     1、尽可能选取权值小的边,但不能构成回路;
图——最小生成树的克鲁斯卡尔算法
/* *Copyright (c) 2015 , 烟台大学计算机学院 *All right resvered . *文件名称: Kruskal算法.cpp *作 者: 郑兆涵 *图——最小生成树的克鲁斯卡尔算法 */ 问题: 最小生成树的Kruskal算法例子 测试用图为: 编程代码: //头文件:graph.h,包含定义图数据结构的代码、宏定义、要实现
最小生成树的Prime算法的思想
普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C.
Java邻接表表示加权有向图,附dijkstra最短路径算法
图这种adt(abstract data type)及相关的算法,之前一直是我未曾涉足过的领域。 主要是作为一个小测试,在平常的工作中也用不着,就算面试,至今也未曾碰到过相关考题。 但是前几天,原公司的小美女谈到面试过程中就碰到一题: 从A到B,有多条路线,要找出最短路线,应该用哪种数据结构来存储这些数据。 等等,这不是显然的考查图论的相关知识了么, 1.图的两种表示方式
实现图的邻接矩阵和邻接表的存储
编写一个程序graph.cpp,设计带权图的邻接矩阵和邻接表的创建和输出运算(包括邻接矩阵和邻接表之间的转换)  //图的基本运算算法 #include #include //图的两种存储结构 #define INF 32767    //定义∞ #define MAXV 100    //最大顶点个数 typedef char InfoType; //以下定义邻接矩阵类
所有边权均不相同的无向图最小生成树是唯一的证明
用反证法,假设G存在俩个不同的最小生成树 ①.设G的俩个不同的最小生成树T1 T2,设这俩颗生成树的并集为子图G1,G1为连通图且T1 T2显然为G1的最小生成树,将G1中两颗生成树的公共边删去,得到子图G2。G2由一个或多个连通分量组成,其中至少有一个连通分量的最小生成树不唯一(否则若所有连通分量的最小生成树唯一,则将删掉的公共边加上,则T1等于T2,这与假设相矛盾)。 ②.对其中一个最小生
C-数据结构-图-邻接表和邻接矩阵创建和定义
//图 //定义 const int vnum=20; typedef struct gp { VertexType vexs[vnum]; int arcs[vnum][vnum]; int vexnum,arcnum;//顶点/边数 }Graph; //带权 const int vnum=20; const int MAX_INT=32768; typedef struct gp {
c语言编程 输出一个无向图的邻接表,邻接矩阵,进行深度和广度优先遍历
#include #include #include #include #define MAXVERTEX 10 //最大顶点数 typedef struct ArcNode //表结点的类型定义 { int adjvex; //边指向的顶点的位置 struct ArcNode *nextarc; //指示下一个与该顶
图的最小生成树Prim算法朴素版(C++)
Prim算法从一个节点开始不断选择权值最小的边加入当前已有的树结构,最终遍历完所有的节点得到最小生成树。时间复杂度为O(V^2)。V为图中顶点个数。C++代码如下:#include <iostream> #include <vector>using namespace std;typedef int DATA_TYPE; // 权值为int型 const DATA_TYPE NO_EDGE = 1
带权图的最小生成树 及其java实现
如图所示:选择哪些边架设电缆,能使得安装有线电视系统的造价最低呢? 方法是利用最小生成树,它将有5条边(比城市数量少1),连接6个城市,并具有建立连接所需的最小代价。设计算法: 算法要点:下面是用图的术语重申一下算法。 从一个顶点开始,把它放入树的集合。然后重复做下面的事情: 1.找到从最新的顶点到其他顶点的所有边,这些顶点不能在树的集合中。把这些边放入优先级队列。 2.找出权值最小的边,
普里姆算法(Prim算法求最小生成树)
普里姆算法的基本思想:普里姆算法是一种构造最小生成树的算法,它是按逐个将顶点连通的方式来构造最小生成树的。时间复杂度为O(n^2)。 从连通网络N = { V, E }中的某一顶点u0出发,选择与它关联的具有最小权值的边(u0, v),将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中,把它的顶
最小生成树思想(普利姆算法、克鲁斯卡尔算法)
给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树. 求最小生成树的算法 (1) 克鲁斯卡尔算法 图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很实用,浪费时间. (2) 普里姆算法 图的存贮结构采用邻接矩阵.此方法是按各个顶点连通的步骤进行,需要用一个顶点集合,开始为空集,以后将以连通的顶点
c语言实现无向图的邻接表储存
图有一种邻接表储存结构,这里以无向图为例,输入图的参数,构造并输出图的邻接表。 #include #include #define MAX_VERTEX_NUM 100 typedef struct ArcNode{ int adjvex;//该边的另一个顶点的位置 struct ArcNode *nextarc; //指向下一条边 }ArcNode; typedef struct VN
立即提问