文章/答案/技术大牛

发布

社区首页 >问答首页 >求有向图中两个顶点之间的所有节点

问求有向图中两个顶点之间的所有节点
EN

Stack Overflow用户

提问于 2014-09-08 14:35:58

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

我正在寻找一个算法，以找到有向图的两个特定节点之间的所有节点。例如，下图中节点"a“和"j”之间的节点如下：

b c d e f g h i

图是有向的，边是向上的(向下到顶部)。

algorithm

graph-theory

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-09-08 14:55:48

您正在寻找一组节点，其中开始节点s可以到达节点，该节点可以到达目标节点t。其中一种方法是从s处执行DFS，查找从s到的所有节点，从t查找所有可以到达t的节点，然后取这两个集合的交集。如果通过在节点本身中存储标记位来维护这些集合，则这将在线性时间内运行。

希望这能有所帮助！

票数 2

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

原文链接：

https://stackoverflow.com/questions/25734105

复制

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

https 网络安全编程算法

给你一个正整数 n ，它表示一个有向无环图中节点的数目，节点编号为 0 到 n - 1 （包括两者）。

Michael阿明

2022/03/10

8550

邻接矩阵求顶点度

#include //蓝多多算法实验六 #include using namespace std; #define MAXVEX 100//最大顶点数 typedef char VertexType;//顶点类型 typedef int EdgeType;//边的权值 typedef struct { VertexType vexs[MAXVEX];//顶点表 EdgeType edges[MAXVEX][MAXVEX];//邻接矩阵 int n, e;//顶点数和边数 }MGraph; MGrap

川川菜鸟

2021/10/18

5620

在图中，从某顶点到另一顶点长度为n的路径有多少条？(矩阵乘法的应用)

cin int 程序计算机数学

0 1 0 1 2 1 2 1

砖业洋__

2023/05/06

2870

Frogger POJ - 2253（求两个石头之间”所有通路中最长边中“的最小边）

编程算法

题目主要说的是，有两只青蛙，在两个石头上，他们之间也有一些石头，一只青蛙要想到达另一只青蛙所在地方，必须跳在石头上。题目中给出了两只青蛙的初始位置，以及剩余石头的位置，问一只青蛙到达另一只青蛙所在地的所有路径中的“the frog distance”中的最小值。

_DIY

2020/02/13

7180

最短路径：Dijkstra算法（求单源最短路径）Floyd算法（求各顶点之间最短路径）[通俗易懂]

https java 网络安全编程算法

在一个带权图中，顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径最短的那条路径称为最短路径。

全栈程序员站长

2022/06/25

2.2K0

最短路径：Dijkstra算法（求单源最短路径）Floyd算法（求各顶点之间最短路径）[通俗易懂]

C语言实例：求100——200之间的所有素数

编程算法

素数是大于1的整数，除了能被自身和1整除外，不能被其他正整数整除。算法过程是：让i被2～i除，如果i能被2～i之间的任何一个整数整除，则结束循环；若不能被整除，则要判断j是否是最接近或等于i的，如果是则证明是素数，否则继续下次循环。

C语言中文社区

2022/05/30

1.7K0

二分图匹配详解

编程算法

二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)G=(V,E)是一个无向图。如顶点集VV 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图GG 为二分图。我们将上边顶点集合称为XX 集合，下边顶点结合称为YY 集合，如下图，就是一个二分图。

风骨散人Chiam

2020/10/28

9570

数据结构第六章图

存储编程算法

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G=(V，E) 其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。

Twcat_tree

2022/11/29

4720

8-2 图的存储结构

编程算法存储

图结构的元素之间虽然具有“多对多”的关系，但是同样可以采用顺序存储，即使用数组有效地存储图。

TeeyoHuang

2019/07/02

5910

关于图中节点间的概率求解问题

java

（本文年代久远，请谨慎阅读）前提：节点是含有若干特征（小节点）的大节点，大节点间连接实际为特征间的连接

ZONGLYN

2019/08/08

8580

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

javascript 编程算法

问题提出背景：在非结构化三角形网格生成过程中，若采用前沿推进法，在推进过程中是不好构造三角形的（而且也没有要），最好在把所有的边都连好以后再找出所有三角形，于是提出了问题：在由三角形构成的平面无向图中如何找出所有三角形？

byronhe

2021/06/25

3470

有向图----有向图的实现

数据结构 api

术语定义：一个顶点的出度为由该顶点指出的边的总数一个顶点的入度为指向该顶点的边的总数一条有向边的第一个顶点称为它的头，第二个顶点称为它的尾数据结构：使用邻接表来表示有向图，其中v->w表示为顶点v对应的邻接链表中包含一个w顶点。有向图API： public class Digraph Digraph(int V) 创建一个含有V个顶点但不含有边的有向图 int V() 顶点数 int E() 边数 void addEdge(int v,int

SuperHeroes

2018/05/30

1.5K0

7.4 图的连通性问题

编程算法 c 语言

1、在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。

小林C语言

2020/12/12

1.2K0

[数据结构拾遗]图的最短路径算法

https 网络安全编程算法

在需要使用到相应算法时，能够帮助你回忆出常用的实现方案并且知晓其优缺点和适用环境。并不涉及十分具体的实现细节描述。

蛮三刀酱

2019/05/06

3.2K0

图的拓扑排序的算法实现，C语言，栈，超详细版本

编程算法数据结构

拓扑排序在工程管理领域中的应用广泛，可用于判断工程能否顺利开展，即判断有向图中是否存在回路。对于一个有向图，先由键盘输入其顶点和弧的信息，采用恰当存储结构保存该有向图后，依据拓扑排序算法思想输出其相应的顶点拓扑有序序列，并提示用户是否存在回路。

Java架构师必看

2021/04/22

1.2K0

深入解析最短路径算法

编程算法

转载自：http://blog.csdn.net/fengchaokobe/article/details/7478774

全栈程序员站长

2022/09/05

6450

[数据结构拾遗]图的最短路径算法

https 网络安全编程算法

在需要使用到相应算法时，能够帮助你回忆出常用的实现方案并且知晓其优缺点和适用环境。并不涉及十分具体的实现细节描述。

Rude3Knife的公众号

2019/08/06

2.8K0

图（graph）原

编程算法数据结构

图是非线性数据结构，是一种较线性结构和树结构更为复杂的数据结构，在图结构中数据元素之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

云飞扬

2019/03/12

1.9K0

经典算法之最短路径问题

https 网络安全编程算法

所谓最短路径问题是指：如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小。最短路径问题一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域有重要的应用。

用户3467126

2019/12/13

2.5K0

基于networkx分析Louvain算法的社团网络划分

node.js jquery 编程算法

一个图G = （V, E）由一些点及点之间的连线（称为边）构成，V、E分别计G的点集合和边集合。在图的概念中，点的空间位置，边的区直长短都无关紧要，重要的是其中有几个点以及那些点之间有变相连。

用户7886150

2020/12/24

3.6K0

相似问题

用R求有向图中两个顶点之间的时间

找到有向图中任意两个顶点之间的所有边。

求有向无环图中两个节点之间的路径数

219

有向图中两个顶点之间的圈

求有向图中的所有根

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

社区富文本编辑器全新改版！诚邀体验～

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

问求有向图中两个顶点之间的所有节点
EN

回答 1

Stack Overflow用户

用R求有向图中两个顶点之间的时间

找到有向图中任意两个顶点之间的所有边。

求有向无环图中两个节点之间的路径数

有向图中两个顶点之间的圈

求有向图中的所有根

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问求有向图中两个顶点之间的所有节点EN

回答 1

Stack Overflow用户

用R求有向图中两个顶点之间的时间

找到有向图中任意两个顶点之间的所有边。

求有向无环图中两个节点之间的路径数

有向图中两个顶点之间的圈

求有向图中的所有根

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问求有向图中两个顶点之间的所有节点
EN