查找无向图中不包含子圈的所有圈 - 腾讯云开发者社区

问题提出背景：在非结构化三角形网格生成过程中，若采用前沿推进法，在推进过程中是不好构造三角形的（而且也没有要），最好在把所有的边都连好以后再找出所有三角形，于是提出了问题：在由三角形构成的平面无向图中如何找出所有三角形...要注意的是，这个无向图很特殊， 1.这个图在平面上。 2.这个图是由三角形构成的（如果不是由三角行构成，那这个网格就没有用处了）。...我的算法如下，伪代码表示: 1 2 3 4 5 6 7 8 9 10 11 12 foreach(点 p in所有的点){ foreach(点 np in p的所有邻居点){...foreach(点 nnpin np的所有邻居点){ if( p,np,nnp三点两两不重合 && p,np,nnp三点两两相连...这两个函数的原理相同， uniqPointOfTriangle( )uniqPointOf2Points（）唯一的作用是它的一个性质：输出和输入参数的顺序无关。

3453 0

有向无环图中一个节点的所有祖先（拓扑排序）

题目给你一个正整数 n ，它表示一个有向无环图中节点的数目，节点编号为 0 到 n - 1 （包括两者）。...给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。...请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有祖先，这些祖先节点升序排序。...= toi 图中不会有重边。图是有向且无环的。...）链接：https://leetcode-cn.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph 著作权归领扣网络所有

8412 0

您找到你想要的搜索结果了吗？

是的

没有找到

数据结构与算法－图

弧：有向图中，顶点 Vi 到顶点 Vj 的边，记作，Vj为弧头箭头端；Vi弧尾无箭头端。 3. 完全图 (1). 无向完全图：边数=n*(n-1)/2的无向图，其中n为顶点数。...子图：图G和G′，若有V(G′) 包含于 V(G) 和 E(G′) 包含于 E(G)，则称 G′ 为图 G 的子图。 6. 邻接：若 (Vi ,Vj ) 属于 E(G)，则称Vi和Vj互为邻接点。...度D(Vi )：有向图的度=入度+出度，即 D(Vi ) = OD(Vi )+ID(Vi )；图中边数与顶点的度的关系为：所有顶点度数之和的一半即为边数。 9....简单回路：第一个和最后一个顶点相同的简单路径，简单回路只能有一个圈。 14. 连通：无向图中，若从顶点Vi到Vj顶点有路径，则称Vi和Vj是连通的。 15. 连通图和连通分量 ? 16....G的子图G’边数小于n-1，则G’中一定不连通。 17. 生成森林：在非连通图中，每个连通分量都可得到一个极小连通子图，也就是生成树。这些生成树就组成了一个非连通图的生成森林。图的基本运算 1.

5724 0

从一道算法面试题看我国信息科技的原创性不足:查找包含所有元素的最短子数组

前不久我遇到这样一道算法面试题：在一个包含重复元素的数组中，找到一个最短子数组，要求该子数组包含了整个数组的所有元素，例如给定数组：7, 3, 7, 3, 1, 3, 4, 1，包含所有元素的最短子数组为...现在问题在于，我们并不知道t和h的值，但我们可以确定的是，只要任何一个子数组，如果它包含了数组的所有元素，那么最短子数组就有可能被这个子数组所包含，所以算法要点就是先找到一个包含所有元素的子数组，然后再看看能不能对其进行压缩...，看看是否能在一个包含所有元素的子数组中，确定最短子数组。...算法第一步是查找给定数组中的所有元素，做到这个不难，我们先遍历数组，然后将当前访问到的元素加入哈希表，如果元素在表中已经存在，说明该元素是重复元素，可以直接忽略，如此遍历一遍后，我们就能得到该数组的所有元素...此时我们得到的子数组a[start…end]可能是包含所有元素的最短子数组，也有可能不是。我们需要继续探寻，以确认后面是否会存在包含所有元素但长度更短的子数组。

6612 0

5 分钟了解下【圈复杂度】是如何计算的？

+ 2*P E 为图中边的个数，N 为图中节点的个数，P 为图中连通分量的个数。...此图中，E = 9, N = 8, P = 1，因该程序圈复杂度为 9 - 8 + (2*1) = 3 ；边的个数和节点的个数很好理解，但：什么是连通分量？...原来，在无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图；虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-V2-V3 和 V1-V4-V3，因此称...若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量；如图示：而在有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路...，则称此有向图为强连通图；若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。

2.8K0 0

【计算理论】计算复杂性 ( NP 完全问题 | 顶点覆盖问题 | 哈密顿路径问题 | 旅行商问题 | 子集和问题 )

| G 是无向图 , 包含 k 个节点的点集覆盖 \} 其中 \rm k 个节点的点集覆盖就是无向图中有 \rm k 个点的点集子集 , 满足点集覆盖要求 ; 点集覆盖是 \rm NP...完全问题 ; 二、哈密顿路径问题 ---- 哈密顿路径问题在图论中是很重要的问题 ; 在下图中 , 从某个顶点出发 , 将所有的顶点都走一遍, 并且每个顶点只能经过一次 , 经过所有顶点的圈称为...哈密顿圈 , 经过所有顶点的道路称为哈密顿道路 , 又称为哈密顿路径 ; 哈密顿路径问题就是找到无向图中的哈密顿路径 ; 涉及到的其它概念 : … 途径 : 顶点和边的交替出现的序列...与哈密顿圈 ; 哈密顿路径问题是 \rm NP 完全的 ; 无向图中哈密顿路径是否存在 , 该问题也是 \rm NP 完全的 ; 前者是求出具体的哈密顿路径 , 后者求哈密顿路径是否存在...; 三、旅行商问题 ---- 旅行商问题 : 无向图中 , 每条边都有一个权重 , 求是否有一条哈密顿路径的权重之和 , 不超过给定的自然数 \rm W ; 旅行商问题是 \rm NP 完全的

1.8K0 0

图论基本概念（更新之中）

（r-正则图表示所有节点的度都是r）无向图：边没有方向性。有向图：边具有方向性。加权图：是一种赋予了边值的图，这些值称为权重或者成本。...*有向图的边集由有序对构成，无向图的边集由无序对构成度（无向图）：节点的度指的是与节点v邻接的节点数。记作：deg(v). 入度：以顶点v为终点的边的数目，称为v的入度。...连通图：图中任意两个节点间都存在路。测地线路：是指节点u和v之间长度最短的路，简称为测地线。标记图：给所有的节点都给以记号来表示。子图的数目：对于一个标记图而言，它的子图的数目是：2ʌk。...k为标记图中连接了被标记节点的边的数目。连同分量：在非连通图中，各个分支称为连同分量。严格来说，图的连同分量指的是极大连同子图。极大不是最大。...（极大是指子图包含的顶点个数极大）一个连通图只有一个连同分量，就是它本身。平凡图：只有一个节点的图。记作K1。圈：n个节点构成的有回路的2—正则图。

1.2K1 0

最全的JavaScript 算法与数据结构

/总和范围查询示例 A 树状数组 (二叉索引树) A 图 (有向图与无向图) A 并查集 A 布隆过滤器算法算法是如何解决一类问题的明确规范。...莫里斯-普拉特算法 - 子串搜索 A 字符串快速查找 - 子串搜索 A 最长公共子串 A 正则表达式匹配搜索 B 线性搜索 B 跳转搜索 (或块搜索) - 搜索排序数组 B 二分查找 B 插值搜索 -...(BFS) 图 B 深度优先搜索 (DFS) B 广度优先搜索 (BFS) A 戴克斯特拉算法 - 找到图中所有顶点的最短路径 A 贝尔曼-福特算法 - 找到图中所有顶点的最短路径 A 弗洛伊德算法...- 找到所有顶点对之间的最短路径 A 判圈算法 - 对于有向图和无向图 (基于DFS和不相交集的版本) A 普林演算法 - 寻找加权无向图的最小生成树 (MST) B 克鲁斯克尔演算法 - 寻找加权无向图的最小生成树..., 不考虑以后情况 B 跳跃游戏 A 背包问题 A 戴克斯特拉算法 - 找到所有图顶点的最短路径 A 普里姆算法 - 寻找加权无向图的最小生成树 (MST) A 克鲁斯卡尔算法 - 寻找加权无向图的最小生成树

1.4K1 0

图

子图（Sub-Graph） - 当图 G'=(V',E') 其中 V‘包含于 V，E’包含于 E，则 G' 称作图 G=(V,E) 的子图。每个图都是本身的子图。...有向图 - 如果给图的每条边规定一个方向，那么得到的图称为有向图。无向图 - 边没有方向的图称为无向图。...轨迹（Track） - 如果路径 P (u,v) 中的顶点各不相同，则该路径称为 u 到 v 的一条轨迹。闭的轨迹称作圈（Cycle）。...桥（Bridge） - 若去掉一条边，便会使得整个图不连通，该边称为桥。如果图的边没有方向性，则被成为无向图。...# 图的基本操作创建一个图结构 - CreateGraph (G) 检索给定顶点 - LocateVex (G,elem) 获取图中某个顶点 - GetVex (G,v) 为图中顶点赋值 - PutVex

2803 0

C++ 图论算法之欧拉路径、欧拉回路算法（一笔画完算法）

欧拉图的几个概念：欧拉回路：指在图（无向图或有向图）中，经过图中所有边且只经过边一次所形成的回路，称为欧拉回路。具有欧拉回路的图称为欧拉图。...欧拉图的性质：欧拉图中所有顶点的度数都是偶数。也就是说，图中存在欧拉回路的充要条件是图中每个结点都是偶节点（连接该节点的边的数量为偶数）。...欧拉图的判定法：无向图是欧拉图当且仅当：非零度顶点是连通的；顶点的度数都是偶数。无向图是半欧拉图当且仅当：非零度顶点是连通的；恰有 2 个奇度顶点。...Tips：根据欧拉图的判断法，下图中每一个节点都是偶节点，满足无向图是欧拉图的前提条件。选节点1为起点，并将该起点加入路径中。Fleury算法选择栈存储欧拉路径。...寻找子回路：如下从节点1开始，沿着边遍历图，一边遍历一边删除经过的边。如果遇到一个所有边都被删除的节点，那么该节点必然是 1（回到初始点）。将该回路上的节点和边添加到结果序列中。

1.2K2 0

漫画：什么是 “图”？

树的节点之间是一对多的关系，并且存在父与子的层级划分；而图的顶点（注意，这里不叫节点）之间是多对多的关系，并且所有顶点都是平等的，无所谓谁是父谁是子。...（貌似是这样）因此，QQ的好友关系可以认为是一个没有方向区分的图，这种图被称为无向图。图的表示邻接矩阵拥有n个顶点的图，它所包含的连接数量最多是n（n-1）个。...同时，无向图对应的矩阵是一个对称矩阵，V0和V1有关联，那么V1和V0也必定有关联，因此A[0][1]和A[1][0]的值一定相等。那么，有向图的邻接矩阵又是什么样子呢？...这样就麻烦一些了，我们要遍历每一个顶点所在的链表，看看链表节点中是否包含节点1，最后发现顶点0和顶点3可以到达顶点1。像这种逆向查找的麻烦，该如何解决呢？我们可以是用逆邻接表来解决。...总结 1.我们这一次介绍了图的定义和分类。根据图的边是否有方向，可分为有向图和无向图。根据图的边是否有权重，可分为带权图和无权图。当然，也可以把两个维度结合起来描述，比如有向带权图，无向无权图等等。

7812 0

漫画：什么是 “图”？（修订版）

树的节点之间是一对多的关系，并且存在父与子的层级划分；而图的顶点（注意，这里不叫节点）之间是多对多的关系，并且所有顶点都是平等的，无所谓谁是父谁是子。 ?...（貌似是这样）因此，QQ的好友关系可以认为是一个没有方向区分的图，这种图被称为无向图。图的表示 ? ? 邻接矩阵拥有n个顶点的图，它所包含的连接数量最多是n（n-1）个。...同时，无向图对应的矩阵是一个对称矩阵，V0和V1有关联，那么V1和V0也必定有关联，因此A[0][1]和A[1][0]的值一定相等。那么，有向图的邻接矩阵又是什么样子呢？ ?...这样就麻烦一些了，我们要遍历每一个顶点所在的链表，看看链表节点中是否包含节点1，最后发现顶点0和顶点3可以到达顶点1。 ? 像这种逆向查找的麻烦，该如何解决呢？我们可以是用逆邻接表来解决。 ?...初学十字链表的时候，可能会觉得有些乱。总结 1.我们这一次介绍了图的定义和分类。根据图的边是否有方向，可分为有向图和无向图。根据图的边是否有权重，可分为带权图和无权图。

6711 0

清北NOIP训练营集训笔记——图论（提高组精英班）

d.重复步骤b和c直到所有顶点都包含在S中。啊~上面的的乱七八糟的概念太难懂了，还是举个例子吧！如下图！ 3.jpg 我们假设1号节点为原点。...如果没有输出所有的顶点，则有向图中一定存在环 //拓扑排序，时间复杂度：O(n+m) #include #include const int N=100500; const...强连通图：有向图中，任意一对点都满足强连通，则这个图被称为强连通图。强联通分量：有向图中的极大强连通子图，就是强连通分量。...欧拉回路：在欧拉路径的基础上回到起点的路径（从起点出发一笔画遍历每一条边）。欧拉路径存在：无向图：当且仅当该图所有顶点的度数为偶数或者除了两个度数为奇数外其余的全是偶数。...有向图：当且仅当该图所有顶点出度=入度或者一个顶点出度=入度+1，另一个顶点入度=出度+1，其他顶点出度=入度欧拉回路存在：无向图：每个顶点的度数都是偶数，则存在欧拉回路。

7911 0

C++ 不知图系列之基于邻接矩阵实现广度、深度搜索

图中的所有顶点构建成一个顶点集合。是图的组成部分。...如上图中的 (V1, V2, V3, V1) 就是一个环。图的类型：综上所述，图可以分为如下几类：有向图：边有方向的图称为有向图。无向图：边没有方向的图称为无向图。...加权图：边上面有权重信息的图称为加权图。无环图：没有环的图被称为无环图。有向无环图：没有环的有向图，简称 DAG。...2.2 定义图 ---- 根据图的特性，图数据结构中至少要包含两类信息：所有的顶点构成的数据集合信息，这里用 V 表示（如地图程序中，所有城市构在顶点集合）。...有权图中，路径指从一个顶点到另一个顶点经过的所有边上权重相加之和。如查找到 A1 到 E5 之间的路径长度：直观思维角度查找一下，可以找到如下路径以及路径长度。

1.2K2 0

PHP数据结构-图的概念和存储结构

（1）子图：假设有两个图 G=(V, E) 和 G'=(V', E') 如果 V' 包含于 V 且 E' 包含于 E ，则称G' 为 G 的子图 ?...上图中右边的那些子图都是属于原图的子图，可以看出子图可以产生非常多的形态，有向图也是相同的概念，不过相对于无向图来说，有向图能够生成的子图更少一些，因为它的边是有方向的。...其实完全图的概念就是图中所有相邻的结点都有边能够连结在一起。...如果整个图中所有的结点都可以是互相连通的，则这个图就是连通图。连通分量就是无向图非连通图中的极大连通子图。 ? 包括后面的三个概念也在这张图中一并给出了。...在无向图中，连通分量就等于极大连通子图，在这个图中，我们有两个连通分量。

8733 0

离散数学---树

1.基本概念及其相关运用（1）无向树：连通而且没有回路的无向图就是无向树；森林就是有多个连通分支，每个连通分支都是树的无连通的无向图；树叶就是这个无向图里面的度数是1的节点，分支点就是度数大于等于...条边，我们在根据这个握手定理，就可以的出来这个无向树的度数和就是边数的两倍，也就是10，这个时候我们再进行列举所有的可能会出现的情况，因为是6个顶点，最大的数字度数就只能是5，否则就会出现重边和环，不满足这个无向树的定义了...，这个是很明显的，其次生成子图还需要满足这个生成子图需要包括这个原来的平面图上面的所有的顶点，而且没有重边，没有环；实际上对于一个图而言，是可以有很多个生成子图的，所以一个连通图可以有很多个不同的生成树...；虽然这个生成子图剩下的弦的集合叫做余树，但是这个并不是真正的树，因为显然这个余树是不联通的，不符合树的定义；（2）最小生成树我们上面介绍的生成树是可能有多个的，这些情况里面的这个权重最小的就是最小生成树...，最小生成树同样也不是唯一的；这个求解最小生成树的算法有这个避圈法，这个方法的主要逻辑就是躲避开所有的圈，按照从小到大的权重进行相应的排列，不能形成圈，满足这个树的定义； 3.有向树（1）有向树就是指那些不关注方向的情况下

380 0

图论碎碎念（2.3）

a 树是一个图 b 无向 c 无圈 d 连通那么问题来了：a树是一个图，b无向在上一节里已经讲到了，但c和d什么鬼？这就需要对图扩展下。 ? 其中 ? ? 问题c.1：图论中的圈是啥？...如果图中的一条链首位相连，这条链就是一个圈。问题c.2：图论中的链是啥？在有向或无向图中，若有点边交替序列： ? 如果可以有 ? 则称该序列为链接vi0至vik的一条链。...有的同学就要问了：问题c.3：链+圈的概念与路+回路的概念有啥区别？链（黄色）可以回头指向，路（红色）只能单行指向： ? ? 圈和路区别同理： ? 问题d.1：连通图是啥？...连通图中每个点都在一条链上，不存在孤立点 ? 总之，树的定义可以按下图来理解： ? 在这棵树中可以看到，点分为两类：一类是结点（圆），一类是端点（终端结点）（三角）。本宝宝是一棵树 ?...临近期末，这是一枚短小的推送。不知道现在的你是否也和小编一样奔波在三点一线间忙于复习呢？后台回复【壁纸】获取MATHWORK网站MATLAB图标的大图壁纸呦~~

5742 0

Python 图_系列之基于邻接炬阵实现广度、深度优先路径搜索算法

图的类型：综上所述，图可以分为如下几类：有向图：边有方向的图称为有向图。无向图：边没有方向的图称为无向图。加权图：边上面有权重信息的图称为加权图。无环图：没有环的图被称为无环图。...有向无环图：没有环的有向图，简称 DAG。 1.2 定义图根据图的特性，图数据结构中至少要包含两类信息：所有顶点构成集合信息，这里用 V 表示（如地图程序中，所有城市构在顶点集合）。...add_vertex( vert )：向图中添加一个新节点，参数应该是一个节点类型的对象。 add_edge(fv，tv )：在 2 个项点之间建立起边关系。...find_vertex( key ) : 根据关键字 key 在图中查找顶点。 find_vertexs( )：查询所有顶点信息。...搜索路径在图中经常做的操作，就是查找从一个顶点到另一个顶点的路径。

9793 0

08.一道美团算法题，Don E.Knuth 花了 24 小时才解出来！

如果执着于二分查找的思路去优化，答案是无果，优化的方向是使用快慢指针。...1、通过快慢指针的方式，在环中寻找它们的第一次相遇的节点位置 2、当快慢指针相遇的时候： x 代表从头节点到环形入口节点的节点数（不包含头节点） y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点...） z 代表从第一次相遇节点到环形入口的节点数（不包含第一次相遇节点）此时，快指针走了 x + y + n (y + z)，其中，x + y 表示快指针第一次到达相遇节点，n 代表快指针在环里面绕了多少圈...（不包含头节点） // y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点） // z 代表从第一次相遇节点到环形入口的节点数（不包含第一次相遇节点）...（不包含环形入口节点） // 所以 n（y + z） - y 时，b 到达了环形入口节点位置 // 由于 x 代表从头节点到环形入口节点的节点数（不包含头节点）

5642 0

《offer来了》第四章学习笔记

5.二叉查找树满足以下条件的树： ◎ 若左子树不空，则左子树上所有节点的值均小于它的根节点的值； ◎ 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值； ◎ 左、右子树也分别为二叉排序树...◎ 每个叶子节点（NIL）都是黑色的。 ◎ 如果一个节点是红色的，则它的子节点必须是黑色的。 ◎ 从一个节点到该节点的子孙节点的所有路径上都包含相同数量的黑色节点。结构 ?...7.1.无向图从顶点 Vi到 Vj的边没有方向，则称这条边为无向边。顶点和无向边组成的图为无向图 ?...，直到图中所有已被访问的顶点的邻接点都被访问；若此时图中尚有顶点未被访问，则另选图中未曾被访问的一个顶点作为起始点重复上述过程，直至图中所有顶点均被访问。...，直至图中所有节点都被访问。

9684 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

找出平面上的特殊无向图中的所有三角形的算法

有向无环图中一个节点的所有祖先（拓扑排序）

数据结构与算法－图

从一道算法面试题看我国信息科技的原创性不足:查找包含所有元素的最短子数组

5 分钟了解下【圈复杂度】是如何计算的？

【计算理论】计算复杂性 ( NP 完全问题 | 顶点覆盖问题 | 哈密顿路径问题 | 旅行商问题 | 子集和问题 )

图论基本概念（更新之中）

最全的JavaScript 算法与数据结构

图

C++ 图论算法之欧拉路径、欧拉回路算法（一笔画完算法）

漫画：什么是 “图”？

漫画：什么是 “图”？（修订版）

清北NOIP训练营集训笔记——图论（提高组精英班）

C++ 不知图系列之基于邻接矩阵实现广度、深度搜索

PHP数据结构-图的概念和存储结构

离散数学---树

图论碎碎念（2.3）

Python 图_系列之基于邻接炬阵实现广度、深度优先路径搜索算法

08.一道美团算法题，Don E.Knuth 花了 24 小时才解出来！

《offer来了》第四章学习笔记

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐