在图采用邻接表存储时，求最小生成树的Prime算法的时间复杂度为?

问题描述

在图采用邻接表存储时，求最小生成树的Prime算法的时间复杂度为?

在图采用邻接表存储时，求最小生成树的Prime算法的时间复杂度为?
A o(n^2) B o(n^3) C o(n) D o(n+e)
答案是o(n+e)。。。不理解..求过程

解决方案

不对，这题应该选A
求顶点的入度的时间复杂度为O(e)*n=O(n*e)
遍历顶点的时间复杂度是O(n^2)
相加是O(n^2+n*e)=O(n^2)

解决方案二：

详细的解释
http://www.cskaoyan.com/redirect.php?fid=24&tid=23630&goto=nextoldset

解决方案三：

一开始我也觉得奇怪，不理解，后来搞清楚了，e代表邻接表表示法边的个数。

设e代表邻接表表示法边的个数，求顶点的入度的时间复杂度为O(e)
遍历顶点的时间复杂度是O(n)
相加是O(n+e)
千万不要把e当作自然底数。

时间： 2024-02-19 10:58:05

在图采用邻接表存储时，求最小生成树的Prime算法的时间复杂度为?的相关文章

图的邻接表存储结构

程序调用入口: using System; namespace Graphic_AdjacencyList { internal class Program { private static void Main(string[] args) { var adjacencyList = new AdjacencyList<char>(); Console.WriteLine("1.初始化树结构:"); Console.WriteLine("=============

图的邻接表存储 c实现

图的邻接表存储 c实2011-10-07 10:34 4047人阅读 评论(2) 收藏 举报 存储cstruct数据结构null编程   用到的数据结构是 一个是顶点表,包括顶点和指向下一个邻接点的指针 一个是边表, 数据结构跟顶点不同,存储的是顶点的序号,和指向下一个的指针 刚开始的时候把顶点表初始化,指针指向null.然后边表插入进来,是插入到前一个,也就是直接插入到firstedge指向的下一个,而后面的后移   [cpp] view plaincopyprint? #define  Ma

图的邻接表存储表示示例讲解_C 语言

复制代码 代码如下: //---------图的邻接表存储表示------- #include<stdio.h>#include<stdlib.h> #define MAX_VERTEXT_NUM 20 typedef int InfoType;typedef char VertextType; typedef struct ArcNode{    int adjvex;    struct ArcNode *nextArc;    InfoType *info;}ArcNode;

C++实现图的邻接表存储和广度优先遍历实例分析_C 语言

本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示       2 3表示该图的

数据结构实践——操作用邻接表存储的图

本文是针对[数据结构基础系列(7):图]的实践. [项目 - 操作用邻接表存储的图] 假设图G采用邻接表存储,分别设计实现以下要求的算法: (1)输出出图G中每个顶点的出度: (2)求出图G中出度最大的一个顶点,输出该顶点编号: (3)计算图G中出度为0的顶点数: (4)判断图G中是否存在边<i,j>. 利用下图作为测试用图,输出结果. 提示:(1)分别设计函数实现算法:(2)不要全部实现完再测试,而是实现一个,测试一个:(3)请利用图算法库. [参考解答] #include <stdi

邻接矩阵(以顶点为中心)，比较稀疏时，采用邻接表；图的两种遍历

对于边比较稠密的图,可以采用邻接矩阵(以顶点为中心)的方式表示,而边比较稀疏时,采用邻接表的结构更合适.两种都不能直观表达哪两个点相连或者最短路径是什么. 深度优先遍历类似于树的先根序遍历.与树不同的是,它需要对已经访问过的节点添加标记以免被重复遍历. public class Depth { /** * 对k号节点深度遍历 * @param a * @param color * @param k 节点 */ public static void depthTraversal(int[][] a

关键路径:php实现图的邻接表,关键路径,拓朴排序

<?php//调用require 'algraph.php';$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j');$e = array('ab'=>'3', 'ac'=>'4', 'be'=>'6', 'bd'=>'5', 'cd'=>'8', 'cf'=>'7', 'de'=>'3', 'eg'=>'9', 'eh'=>'4', 'fh'=>'6', 'gj'=>

【算法导论】邻接表存储的拓扑排序

        上一篇文章中讲述了用邻接矩阵存储的图的拓扑排序,下面本文介绍用邻接表存储的图的拓扑排序.         关于拓扑排序的概念及基本思想,我在上一篇文章中已经较为详细的描述了,这里不在介绍.我们知道利用邻接矩阵进行拓扑排序时,程序实现较为简单,但是效率不高,算法的复杂度为O(n^3).而利用邻接表会使入度为0的顶点的操作简化,从而提高算法的效率. 在邻接表存储结构中,为了便于检查每个顶点的入度,可在顶点表中增加一个入度域(id),这样的邻接表如下图所示,这样只需对由n个元素构成的顶

图的邻接表实现 Adjacency List of the Graph

图的邻接表实现 Adjacency List of the Graph eryar@163.com 一.图的邻接表   邻接表(Adjacency List)是图的一种链式存储结构.在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边,对有向图是以顶点Vi为尾的弧.如下图所示的图用邻接表表示如下:    根据上图来定义用邻接表表示图的数据结构.当用邻接表来表示图时,图是由顶点序列组成的,在每个顶点中,记录下与该顶点相连的顶点在顶点序列中的位置.相关的数据结构如下所