完全图、连通图、非连通图、连通分量、强连通图、生成树的概念-程序员宅基地

技术标签：算法图论数据结构

图

对于n个结点的图来说：

无向完全图：有n（n-1）/2 条边，如下：4个顶点有6条边

连通图：无向图中，任意两个顶点是连通的（一个顶点不必与另一个顶点直接相连，可以通过其它顶点到达即可）最少有n-1条边；如下：4个顶点最少需要3条边才能够连通

非连通图，即边数少于n-1条，最多有（n-1）*(n-2)/2条，如下：5个结点，非连通，最多有6条边

连通分量：无向图中（区别于有向图）的极大连通子图，极大即要求拥有连通子图的所有边，例如，如果A1中少了a-d这条边就不是极大连通子图了

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bPb3bINB-1659012648961)(../typ-img/image-20220728203945406.png)]

强连通图：从a到b和从b到a都有路径。最少有n条边，假若少了A-D的路径，则A可以到D，但是D到不了A，就不满足条件。

强连通分量：有向图中的极大强连通子图，对比无向图中连通分量

生成树：包含图中全部顶点的一个极小连通子图（生成树不唯一）。若去除一条边，则生成树会变成非连通图；若多加上一条边，则会形成回路

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NQSYvvNk-1659012648962)(../typ-img/image-20220728204539370.png)]

注意：极大连通子图要求连通子图包含所有边，极小连通子图要求使图保存连通的前提下使边数最少。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4Wl7L39J-1659012648963)(../typ-img/image-20220728201520617.png)]

简单路径：顶点不重复出现的路径称为简单路径

区分：无向图关于连通图和连通分量，有向图关于强连通图和强连通分量

本文链接：https://blog.csdn.net/qq_46440190/article/details/126043711

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

C++面试宝典第11题：两数之和-程序员宅基地

文章浏览阅读1.9k次，点赞51次，收藏47次。通过这道题，我们对算法的时间复杂度和空间复杂度有了一定的理解。时间复杂度和空间复杂度并不是完全独立的两个概念，虽然它们衡量的是算法效率的不同方面，但在实际应用中，这两个因素有时会相互制约，形成一种“时间-空间”的平衡。比如：对于某些问题，使用一种时间复杂度较低的算法可能需要更多的空间来存储中间结果或额外的数据结构，而使用一种空间复杂度较低的算法可能会牺牲一些时间效率。然而，时间复杂度和空间复杂度并不是矛盾的。它们分别衡量算法在不同方面的效率，可以同时达到最优。

基于Java语言的安卓程序编程之二HelloWorld程序的运行_android中helloworld测试程序的执行过程-程序员宅基地

文章浏览阅读6.8k次，点赞3次，收藏11次。1 程序保存路径设置鼠标双击Eclipse.exe，打开Eclipse程序。首先在弹出的对话框中设置Eclipse的工作空间，即编写的安卓程序保存的路径，可以使用默认路径，也可以通过点击“Browse...”按键进行自定义设置，如图1-1所示。图1-1 设置Eclipse的工作空间2 安卓应用程序的创建2.1 新建程序在Eclipse主界面的菜单栏中，选择“File->_android中helloworld测试程序的执行过程

UVa 11287 - Pseudoprime Numbers_uva11287-程序员宅基地

文章浏览阅读168次。题目判断一个数是不是为伪素数。能够通过费马测试的合数。分析数论，直接按照定义判断即可。说明学python，ヾ(◍°∇°◍)ﾉﾞimport mathdef is_prime(x): for i in range(2, int(math.sqrt(x))+2): if x % i == 0: return False ..._uva11287

大学python实训总结-【python实训总结和体会】作文写作问答 - 归教作文网-程序员宅基地

文章浏览阅读4.6k次。对python学习的总结怎么写1.Python初步Python是一种面向对象、直译式计算机程序设计语言。公认的特点是简单、易学、免费、开源等等。个人觉得特别喜欢Python的地方是对字符串操作特别的灵活、采取缩进的方式简单明了（虽然百度百科上把这个说成是局限）、以及简单的语法。Python 和c类似，是顺序进行的，不想visual c++是事件触发不同模块进行的。操作和matlab相似，有编辑窗口..._大学生python实训总结

解决Win下使用conda activate python虚拟环境无效的问题_conda activate environment不生效-程序员宅基地

文章浏览阅读8.9k次，点赞14次，收藏9次。在有些Win系统中会出现激活用户自定义的虚拟环境无效的问题conda activate env输入上述代码，并没有进入名为env的虚拟环境中。解决方法：首先输入命令行：activate可以看到进入了（base）环境中再输入：conda activate env即能成功进入名为env的虚拟环境..._conda activate environment不生效

怎么开启windows hypervisor platform,解决hypervisor platform消失无法安装的问题-程序员宅基地

文章浏览阅读3.7w次，点赞7次，收藏24次。正常的windows功能面板我的很好,没有安装windows hypervisor platform的机会,但是没关系然后cmd 或powershll 管理员身份运行Dism /online /Get-Features可以查看到hypervisor platform是禁用状态pushd “%~dp0”dir /b %SystemRoot%\servicing\Packages*..._windows hypervisor platform