开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >如果新的边被添加到无向赋权图G中，则确定MST T是否仍然是新图G的MST

问如果新的边被添加到无向赋权图G中，则确定MST T是否仍然是新图G的MST
EN

Stack Overflow用户

提问于 2019-10-26 13:32:26

回答 1查看 219关注 0票数 0

这是一个复习问题，我想知道我的答案是否正确。

以下是原问题的要点：

你有一个加权无向图的MST，T，然后在原始图的节点(u和v)之间引入一条新的边，以创建一个新的图G‘。给出了判定T是否是G‘的MST的线性时间算法。

我的答案是：

原始图的MST T不包含任何圈。从节点u到节点v应该只有一条路径。我们可以将新的边添加到MST中，这可以在O(1)时间内完成，从而生成我们的新树T‘。然后，我们可以在从u到v的T‘上运行DFS，它在O(|V| + |E|)时间内完成。添加了新的边之后，我们最多只能在u和v之间找到2条路径。我们可以在O(1)时间内比较这两条路径。如果两个图中较短的一个使用了新的边，那么我们知道原始的MST "T“不是新图G‘的MST。我们的整个算法将在线性时间内完成。

time-complexity

depth-first-search

minimum-spanning-tree

语音识别特惠，低至14.9元！

提供业界非常具有性价比的语音识别服务，超高识别准确率，适用多场景

EN

回答 1

Stack Overflow用户

发布于 2019-10-26 16:08:24

这是一个正确的算法，并且您已经证明，如果它找到一棵更轻的树，那么旧树就不是最小树。你仍然需要证明，如果它找不到更轻的树，那么老树仍然是最轻的。

票数 0

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/58571243

复制

相关文章

[MongoDB] 使用PHP在MongoDB中搜索的实现

mongodb 数据库 sql 云数据库 MongoDB 正则表达式

条件操作符用于比较两个表达式并从mongoDB集合中获取数据。 MongoDB中条件操作符有： (>) 大于 - $gt (<) 小于 - $lt (>=) 大于等于 - $gte (<= ) 小于等于 - $lte MongoDB 使用 $regex 操作符来设置匹配字符串的正则表达式，使用PCRE (Perl Compatible Regular Expression) 作为正则表达式语言。 MongoDB OR 条件语句使用了关键字 $or

唯一Chat

2020/02/25

5.2K0

Yii2中的components的使用

这里我们以企查查为例 1.在common下创建components文件夹（如果没有就创建） 2.创建类文件 Name.php <?php namespace common\compo

botkenni

2019/09/02

1K0

MongoDB新增字段,删除字段

新增字段 db.yourcollection.update({},{$set:{"新增字段名称":""},false,true) 删除字段 db.yourcollection.update({},

十月梦想

2018/08/29

2.5K0

MongoDB主键：使用ObjectId () 设置_id字段

mongodb 数据库 sql 云数据库 MongoDB

在MongoDB中，_id字段是集合的主键，以便可以在集合中唯一地标识每个文档。_id字段包含唯一的Object ID 值。

MongoDB中文社区

2020/02/19

5.4K0

MongoDB主键：使用ObjectId () 设置_id字段

使用awk打印文件中的字段和列

shell linux unix 编程算法

Awk 自动将提供给它的输入行划分为字段，一个字段可以定义为一组字符，这些字符通过内部字段分隔符与其他字段分开。如果你熟悉 Unix/Linux 或者做bash shell 编程，那么你应该知道什么是内部字段分隔符 (IFS) 变量是。Awk 中的默认 IFS 是制表符和空格。 Awk: 遇到输入行时，根据定义的IFS，第一组字符为field one，访问时使用 1，第二组字符是字段二，使用访问 2，第三组字符是字段三，使用访问为了更好地理解这个 awk 字段编辑，让我们看看下面的例子： Exampl

入门笔记

2022/06/02

10K0

Yii2中对Composer的使用

composer php yii node.js windows

若使用Composer我们应该先知道这是一个什么东西，主要干什么用的，我们可以把Composer理解为PHP包的管理工具，管理我们用到的Yii2相关的插件。

PHP学习网

2022/08/03

9440

MongoDB学习系列(2)--使用PHP访问MongoDB

mongodb 数据库 php

第一部分：介绍在Windows上安装最新MongoDB步骤非常的简单，这里不做介绍。但是如果你安装的时候没有将MongoDB作为服务运行，每次你都要使用cmd切换到指定的目录下，然后在cmd中启动M

八哥

2018/01/18

9380

MongoDB学习系列(2)--使用PHP访问MongoDB

MongoDB开发系列-字段存储长度使用探讨

mongodb 数据库 api sql 云数据库 MongoDB

针对MongoDB中数据库字段的存储字符长度的疑问，本文采用提出问题假设，描述使用场景，给出对应的接入方案的方式，探讨MongoDB数据建模中字段存储和展示相关的问题，为基于MongoDB的数据库建模提供参考。

needrunning

2019/09/30

1.9K0

MongoDB开发系列-字段存储长度使用探讨

MongoDB更改字段类型

https 编程算法网络安全 javascript

1 Double 浮点型 2 String UTF-8字符串都可表示为字符串类型的数据 3 Object 对象，嵌套另外的文档 4 Array 值的集合或者列表可以表示成数组 5 Binary data 二进制 7 Object id 对象id是文档的12字节的唯一 ID 系统默认会自动生成 8 Boolean 布尔类型有两个值TRUE和FALSE 9 Date 日期类型存储的是从标准纪元开始的毫秒数。不存储时区 10 Null 用于表示空值或者不存在的字段 11 Regular expression 采用js 的正则表达式语法 13 JavaScript code 可以存放Javasript 代码 14 Symbol 符号 15 JavaScript code with scope 16 32-bit integer 32位整数类型 17 Timestamp 特殊语义的时间戳数据类型 18 64-bit integer 64位整数类型

周小董

2019/03/25

7K0

PHP开发——yii2多图上传组件的使用

最近在使用yii2开发一个表单页面的时候，有多图上传的需求，稍微找了找这方面的组件，基本都安利fileInput这个组件，于是就尝试着使用这个库来完成后端表单页面的多图上传功能。使用的过程中发现还是有不少小细节需要注意的，于是记录一下使用的过程。

Originalee

2018/08/30

1.4K0

PHP中的数据库四、mongodb

mongodb 数据库云数据库 SQL Server php

枕边书

2018/01/04

1.5K0

Django中FilePathField字段的使用

class FilePathField(path=None[, match=None, recursive=False, max_length=100, **options]) 一个 CharField ，内容只限于文件系统内特定目录下的文件名。有三个参数, 其中第一个是必需的: FilePathField.path 必填。这个FilePathField 应该得到其选择的目录的绝对文件系统路径。例如: "/home/images". FilePathField.match 可选的.FilePathField 将会作为一个正则表达式来匹配文件名。但请注意正则表达式将将被作用于基本文件名，而不是完整路径。例如: "foo.*.txt$", 将会匹配到一个名叫 foo23.txt 的文件，但不匹配到 bar.txt 或者 foo23.png. FilePathField.recursive 可选的.True 或 False.默认是False.声明是否包含所有子目录的路径 FilePathField.allow_files 可选的.True 或 False.默认是True.声明是否包含指定位置的文件。该参数或allow_folders 中必须有一个为 True. FilePathField.allow_folders 是可选的.输入 True 或者 False.默认值为 False.声明是否包含指定位置的文件夹。该参数或 allow_files 中必须有一个为 True. 当然，这些参数可以同时使用。有一点需要提醒的是 match只匹配基本文件名（base filename）, 而不是整个文件路径（full path）. 例如: FilePathField(path="/home/images", match="foo.*", recursive=True) ...将匹配/home/images/foo.png而不是/home/images/foo/bar.png 因为只允许匹配基本文件名(foo.png 和 bar.png). FilePathField实例被创建在您的数据库为varchar列默认最大长度为 100 个字符。作为与其他字段，您可以更改使用的max_length最大长度。大多数网站在插入图片时一般都是这样处理的：上传大尺寸图时，自动生成一张缩略图；网页中插入缩略图，并把地址指向大尺寸的图。所以在Django中，我这样定义主要字段： title = models.CharField(max_length = 120) img = models.ImageField(upload_to = 'screenshots') thumb = models.FilePathField(path = 'screenshots/thumb') 为什么thumb不是ImageFiled呢？因为考虑到Admin中上传的是大图，而缩略图不是上传，而是自动生成的。所以在这样写。具体的处理是（假设MEDIA_ROOT为/tmp，MEDIA_URL为http://localhost/media/：上传图片(test.jpg)至MEDIA_ROOT/screenshots，此时img的属性是：img.name = screenshots/test.jpg, img.path = /tmp/screenshots/test.jpg, img.url = http://localhost/media/screenshots/test.jpg 判断图片大小是否需要做缩略图，如果不需要，直接复制img.path到thumb，否则，生成一张缩略图（以test-thumb.jpg命名）保存在screenshots/thumb下。在网页中插入图片时，就可以简单地用<a href="{% object.img.url %}"><img title="{% object.title %}" src="{% object.thumb %}" alt="{% object.title %}"></a>来表示了。object表示一个ScreenShot。

菲宇

2019/08/14

3.7K0

[MongoDB]MongoDB(projection字段筛选)

db filter projection

db.users.find({},{projection}) 注意:filter实现的是筛选出某条数据，projection实现的是筛选出某条数据的具体字段

唯一Chat

2020/02/24

9330

在php的yii2框架中整合hbase库的方法

php http hbase TDSQL MySQL 版

Hbase有两套thrift接口（thrift1和thrift2）,但是它们并不兼容。根据官方文档，thrift1很可能被抛弃，本文以thrift2整合为例。

子润先生

2021/07/13

6310

mongodb的启动和使用

mongodb 数据处理

启动mongodb 启动前，先指定mongodb的data目录，如果没有就创建一个： 1 2 [root@test6 ~]# cd /usr/local/mongodb [root@test6 mongodb]# mkdir data 然后，执行如下命令即可启动mongodb： 1 [root@test6 mongodb]# /usr/local/mongodb/bin/mongod --dbpath=/usr/local/mongodb/data/ --logp

用户1220053

2018/02/09

1.4K0

Flink CDC MongoDB Connector 的实现原理和使用实践

mongodb 云数据库 MongoDB flink 数据库数据集成

摘要：本文整理自 XTransfer 资深 Java 开发工程师、Flink CDC Maintainer 孙家宝在 Flink CDC Meetup 的演讲。主要内容包括：

从大数据到人工智能

2022/09/09

2.7K0

Flink CDC MongoDB Connector 的实现原理和使用实践

php使用pecl安装mongodb扩展

php mongodb 数据库 sql 云数据库 MongoDB

默认情况下，php并没有安装mongodb扩展，会报Class 'MongoDB\Driver\Query' not found错误。

章鱼喵

2019/02/21

1.1K0

php使用pecl安装mongodb扩展

点击加载更多

相似问题

使用Yii2和MongoDB登录

11

Yii2中的MongoDB string字段值长度

221

如何使用MongoDB ex: name而非id中的自定义字段对分页进行索引和排序

10

使用yii2框架获取mongodb中的数量和

14

如何使用$inc实现MongoDB文档字段？

13

活动推荐

提供大模型在企业的应用构建、高效便捷

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例