1回答
我对图形很陌生，我试图用Java来解决这个问题：
给定一个具有N个节点和N个加权双向边的图，如果一个新的边'q‘允许减少图的总权重，则该算法必须响应是。
如果存在边'e‘，则边'q’满足这个条件，这样就可以将'e‘替换为'q’，使图保持连通并减少其整体权重。
我用邻接表实现了这个图：
public class Vertex {
private final int element;
private final Set<Edge> edges; // Collection of edges to neighbors
public Vertex(
浏览 4提问于2020-06-23得票数 1
回答已采纳
1回答
我似乎在网上找不到任何关于这个问题的暗示，而且由于我正在考试，所以问题很简单，任何解释都会受到欢迎(尽管简单的是或否也可以)。
对于Dijkstra的算法，图必须是强连通的吗？也就是说，每一个停战都可以从其他任何一个停战点中得到？或者，是否可能有无法到达的顶点，因此必须使用该算法从另一个节点开始？
为了补充这个问题:Dijkstra的算法只适用于无向图吗？因为我课本上的所有例子都是关于无向边的。
浏览 5提问于2016-12-11得票数 1
回答已采纳
假设我们可以构造一个有N个顶点的图，那么图需要的最小边数是多少，这样它就不能有一个交点？换句话说，它需要双管齐下。
一个完整的图显然没有任何的交点，但我们仍然可以删除它的一些边，它可能仍然没有任何。因此，它似乎可以有较少的边数比完整的图。对于N个顶点，我们可以用多种方法构造图。所以这个最小数应该满足所有这些图。
澄清，因为标题是混淆的用户-最小的m(作为一个函数的n)，使每个n-顶点图，至少有m边必然是两个相关的？
浏览 5提问于2014-08-25得票数 2
回答已采纳
2回答
来自
有向图被称为弱连通图，如果用无向边替换它的所有有向边产生一个连通(无向)图
这个准确吗？
上面的图是连通的，当所有有向边都被无向edges.But替换时，B到D或D到B之间没有路径，这违反了弱类型的property..Am I，对吗？
浏览 2提问于2013-09-06得票数 4
回答已采纳
如何用java找到图的中心(顶点，与其他顶点相连，但边指向图的中心)。这是一个非常有用的facebook类网站应用程序。
浏览 3提问于2012-11-22得票数 2
1回答
我们知道：
从形式上讲，区间图是区间.Moreover族的一类交图，它对集合中的每个区间都有一个顶点，并且对应于相交的区间的每一对顶点之间都有一个链接/边。
但问题是:区间图是不连通的，还是必须总是连通的？
请看图:是区间还是非区间？
浏览 2提问于2015-09-17得票数 0
1回答
如何以最少的步骤删除一个图？
、、、、
给定有向图，如何找到删除最小节点数以删除整个图所需的顺序？我假设如果一个节点被删除，连接到它的所有外部节点(任意程度)也会被删除。
例如，在二进制搜索树中，删除树中所有节点的最快方法(给定假设)是删除根节点。然而，给定任何一个图表，如何才能确定要删除哪些节点？
我的想法(很慢)：
生成所有可能的子图，并找到具有最外边的子图。
删除那个子图。
重复，直到没有剩馀的节点。
为什么这是一个很好的问题：假设我们得到了一个有向图，它的节点代表了世界上所有的问题，而所有这些节点都与表示原因/效果的边相连接(即有些问题导致了其他问题)。我们如何才能找到最小数目的问题，以摆脱所有的问题？
浏览 1提问于2015-09-07得票数 3
1回答
连通无向无圈图与树
、、、
当我在麻省理工学院的“算法概论”中学习图论的时候，我被介绍了一些关于图和树的定义。
在麻省理工学院对算法第三版书的介绍中，附录树一章向我展示了定理B.2，“自由树的特性”
设G= (V，E)是无向图。以下语句是等价的。
G是一棵免费的树..。
G是无环的，且x-E=V- 1.
是否有一个连通的、无向的、非循环的图不是树的例子？
从理论上讲，如果有一个无向无圈图，它满足了一个条件，那就可以作为例子了吗？
如果有一个例子满足这个条件，你能给我看一下吗？
浏览 4提问于2015-11-17得票数 4
回答已采纳
1回答
我想说明的是，对于一个示例图族，连通子图的数量随着n的增加而增加。
对于一个完整的图，这很容易显示，因为一个完整的图具有
n(n-1)/2 =n/2
边。一条边要么在子图中，要么不在子图中。因此，每个子图都可以用长度为
2^(n超过2)
因为它是一个完整的图，所以每个子图都是连通的。
但让我们假设，例如，我们想要显示3-或4-正则图中的连通子图的数量也呈指数增长。我们可以用同样的方式枚举子图。但我们必须排除它们中的许多，因为它们是不相关的。
我们如何做到这一点？有没有办法区分所有连通子图和非连通子图？
致以问候和感谢您的想法
浏览 0提问于2016-03-18得票数 0
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
2回答
是否有一个直接的算法来生成一个随机的无向双连通图(给定多个顶点作为输入)？我知道如何确定给定的图是否是双向的，但我很难通过编程来生成一个图。
浏览 4提问于2015-08-24得票数 6
回答已采纳
1回答
有向图中的Euler电路
、、、、
如何检查有向图是否是欧拉图？
1)所有非零度顶点都属于单个强连通分量。
2)在度上等于每个顶点的出度。来源：
问题：在给定的两个条件下，第一个是严格的吗？我的意思是，为什么图必须是“强”连通图？如果这个图只是连通的呢？
我学到了条件1可以用弱连通图代替。同样，如果图是连通的而不是弱连通的呢？会很高兴看到一些例子。
P.S：考虑条件2在上述讨论中总是得到满足。所谓“刚刚连接”，我的意思是在图中存在一个顶点，从这个顶点可以到达所有其他顶点。
浏览 12提问于2020-04-19得票数 1
回答已采纳
2回答
我们知道：
如果我们有N个顶点来构造一个连通的无向图，你至少需要N个边。设M是具有N-1边的可能连通无向图的集合.
我们能否证明或证明，如果有一个无向连通图有超过N1边，那么它必须包含M中的一个图？换句话说，我们可以用M中的一个图来添加边来创建这个新的图吗？
(所谓“包含”，我的意思是它有另一个图的所有边，再加上一些。)
浏览 4提问于2016-12-09得票数 1
回答已采纳
1回答
我试图找到我的图表的SPQR树，所以我发现sage可以帮助我。我把我的代码放在这里-- (而不是sage programe)。下面是：
H=Graph({"AL":["GR","ME","MK","RS"],"GR":["BG","MK","TR"],"ME":["BA","HR","KO","RS"],"MK":["BG","RS
浏览 0提问于2021-04-06得票数 2
回答已采纳
1回答
引理1:如果H是图G的子图，则dist_G(u，v)<= dist_H(u，v)。
证明 H中的每条u-v路径也出现在G中，并且G可能有比H中的任意u-v路径更短的u-v路。
引理2:如果H是图G的连通子图，使得V(H)=V(G)，则直径(G)≤直径(H)
证明
直径(G)=最大{dist_G( u，v)}对所有u，v在V(G)中
假设直径(G)= dist_G(x，y)对某些x，y在V(G) = V(H)中
某些a，b在V(H) = V(G)中的直径(H)= dist_H(a，b)
注意，dist_H(s，t) <= dist_H(a，b)适用于V(H)中的所有s
浏览 3提问于2016-07-08得票数 0
1回答
有人知道这个算法吗，因为我正在考虑使用它，但我不确定它是否真的满足我的所有要求。所以基本上，我想要做的是将一个图分成几个子图。然而，每个子图的节点应该是连接的，也就是说，不应该是这样的情况，例如，如果我想到达节点x，我必须通过另一个子图。而这正是我所关心的。有没有可能，当我用Kernighan-Lin算法分割一个图时，子图的节点会分散在各处？
浏览 28提问于2013-07-08得票数 1
我想在无向图中找到一个强连通的组件，也就是说，如果我从一个节点A开始，那么我将返回到节点A，并且每条边都被访问一次。
对于有向图，可以使用Tarjan的算法求强连通分量，但如何处理无向图。
浏览 5提问于2017-06-16得票数 3
1回答
给予：
有向图
节点有标签
相同的标签可以多次出现。
边缘没有标签
我想找到一组最大(连通)子图，它们是相等的，考虑到节点的标签。
图可能是巨大的(数百万节点)，有人知道一个有效的解决方案吗？
我正在寻找算法和理想的Java实现。
更新:因为这个问题很可能是NP-完全的。我也会对产生近似解的算法感兴趣。
这似乎至少是近在眼前：
浏览 1提问于2009-05-08得票数 0
1回答
TL;DR
如何构造顶点均为偶数的连通图的任意2-正则脱离？适当的算法，数据结构？伪码？实际执行了吗？
定义
D1：如果H的每个顶点都有2次，则称图H是2-正则的。
D2：图G的脱离H是通过将图G的一些顶点分割成多个顶点，并在子顶点之间任意共享入射边而得到的图(参见)。
问题：我想用Java编写一个程序来构造连通图G的任意2-正则脱离H，其顶点都是偶数度的(参见)。
我至今所做的一切
我搜索了伪代码和一个实际的实现，但是除了以下定理之外，我没有找到任何相关的东西：“如果一个连通图G的顶点都是偶数度的，则G的边集可以划分为循环，其中没有两个图具有相同的边”。下面还有一个关于这个定理的建设性证明。
浏览 3提问于2015-05-19得票数 2
1回答
需要一些关于如何定义图是对偶欧拉的指导吗？这意味着有两个电路，如果组合在一起，我们会访问图中的所有边。我可以假设图包含一个欧拉电路。
编辑
@ Evgeny Kluev答复
如果该图包含至少一个具有4个或多个边的顶点，则该图具有2个Euler圈。
浏览 2提问于2012-04-03得票数 2
假设我有这段代码，它创建了一个DiGraph：
dict = {1:['a1', 'a2', 'a3'], 2:['a4', 'a5','a7']}
graph = nx.from_dict_of_lists(dict)
digraph = nx.DiGraph(graph)
我怎样才能在这张图中找到所有的根？此图的预期输出为1,2
如果它更适合您，我已经在中编写了代码，您可以在这里看到图表，希望它能有所帮助。
编辑:这在某种程度上与这个有关，不同的是，在那篇文章中，假设图是连通的，所以只有一个根，
浏览 4提问于2020-06-19得票数 1
回答已采纳
2回答
强连通有向图是一个有向图，其中每个顶点都有一个有向路径，其中有一个从to到to的有向路径和一个从to到的直接路径。设= (，)是强连通有向图，设= (，)∈是图中的边。设计了一种有效的算法，它决定了没有边的图是否是强连通的。解释其正确性并分析其运行时间。
所以我所做的就是运行BFS，对标签进行求和，一次在原始图from上，然后在G‘中，再一次在G’中，没有边(同样从)，然后:如果第二次和(在G') <原始和(在G中)，那么这个图就不是强连通的。
这是我考试中的一个问题，我只拿到了3/13分，我想知道我是否应该上诉。
浏览 6提问于2019-02-11得票数 5
回答已采纳
我有一个有向图G，它是用Python语言中的networkX创建的。每条边都是双向的。我有一个特定的节点列表，我正在尝试查找这些节点中的连接组件。下面我已经创建了一个样本数据集(我处理的实际图形要大得多)。 import networkx as nx
G = nx.DiGraph()
nodeList = range(1,10)
for i in range (0,len(nodeList)):
G.add_node(nodeList[i])
o_nodes = [1,1,2,3,3,3,3,4,4,5,5,6,7,7,8,9,9,10]
d_nodes = [8,3,3,1,7
浏览 22提问于2019-09-27得票数 4
回答已采纳
1回答
这个问题是我先前提出的类似问题的延续：。
问题摘要：我需要找到图中从顶点A到顶点B的最佳路径，假设路径质量是以路径上边权的最小值来计算，其次是具有最大最小值的最佳路径。通常情况下，它被称为。
以前我需要用非常小的图(最多15个顶点)来解决这个问题，所以我不需要复杂的算法，而且在友好的人的帮助下，我设计了我的工作算法。不幸的是，现在我需要重新定义我的需求，使我的图形可以非常大(甚至5万条边)。我知道我需要为我的图找到最大生成树，并在得到的MST中从开始到停止得到一个简单的路径。我决定使用库。它已经实现了。通过将每个边权乘以(-1)，用Kruskal表示最小生成树，就可以得到最大生成树，但该库中的
浏览 2提问于2013-09-04得票数 0
一个完全连通的有向图，其中每个节点最多有一个入站边是一棵树。每个节点最多有一个出站边的全连通有向图是否有一个名称？反树？！
浏览 0提问于2015-11-14得票数 1
回答已采纳
2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
1回答
弱连通平衡有向图
、、
我如何证明如果一个平衡有向图是弱连通的，那么它也是强连通的？(平衡有向图意味着对于每个节点，它的索引度和出度是相同的，弱连接意味着这个图的无向版本是连接的)。
到目前为止，我能想到的是:如果图是平衡的，这意味着它是有向循环的并集。因此，如果我移除任何循环，它将保持平衡。此外，循环中的每个顶点都有一条边进入它，另一条边通向它。
然后我想我需要使用一些矛盾或归纳来证明这个图是强连通的。这就是我困惑的地方。
浏览 2提问于2011-12-01得票数 1
1回答
连通图中切边数的最大化
、、、、
这个问题非常类似于。给定一个无向图，我们想要找到所有的桥梁。无向连通图中的边是一个桥当且仅当移除它使图断开。
变体
我不想找到所有的桥，我想要最大化要删除的边数，这样图才能保持连通。
示例1
Input: n = 5, edges = [[1, 2], [1, 3], [3, 4], [1, 4], [4, 5]]
Output: 1
首先，我可以删除[3,4]、[1,3]或[1,4]。接下来，在移除这三个边中的任何一个后，剩下的边都是桥。因此，为了使图保持连通，要删除的最大边数为1。
示例2
Input: n = 6, edges = [[1, 2], [1, 3], [2, 3],
浏览 3提问于2019-11-07得票数 0
回答已采纳
1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
1回答
可能重复：
你什么时候会用Kruskal算法而不是Prim算法找到最小生成树？哪种输入图和节点更适合每种类型？在什么情况下，当涉及到空间和时间时，使用其中之一更有效？
它们的特殊投入是否使其中一种比另一种更好？
浏览 3提问于2012-12-11得票数 2
2回答
我正在阅读关于强连接组件在下面的链接。
这里作者提到
回想一下，关系是对象对集合的另一个词(如果您愿意，可以将关系看作是有向图，但不是我们用来定义连通性的那个)。等价关系a#b是满足以下三个简单性质的关系：
自反性质:对于所有的a，a。任何顶点都是强连接的，根据定义。
对称属性:如果a# b，那么b# a.对于强连通性，这遵循于定义的对称性。相同的两条路径(一条从a到b，另一条从b到a)表明a~b，以另一个顺序(从b到a，另一个从a到b)显示b~a。
传递性质:如果a#b和b# c，那么a# c，让我们把它扩展到强连通性:如果a~b和b~ c，我们有四条路径: a-b，b-a，b
浏览 3提问于2015-06-23得票数 2
1回答
我刚开始在R中使用图，还没有找到这个问题的解决方案。取一个简单的图
library(igraph)
df <- data.frame(a = c("a","a","a","b","c","f"),
b = c("b","c","e","d","d","e"))
my.graph <- graph.data.frame(df, directed = FALSE)
浏览 3提问于2022-07-13得票数 0
回答已采纳
我用R中的i图来计算图的测度，我的图是在PIN中生成的，它是不连通图，是不连通图。连通图的封闭方法是好的，正确的计算，而对于断开图在不好！
library(igraph)
# Create of Graph Matrix for Test Closeness Centrality
g <- read.table(text="A B
1 2
2 4
3 4
3 5", header=TRUE)
gadj <- get.adjacency(graph.edgelist(as.matrix(g), directed=FALSE))
igObject &l
浏览 2提问于2015-06-16得票数 2
回答已采纳
3回答
单连通图是一个有向图，它最多有1条路从u到v∀u，v。
我想出了以下解决办法：
从任何顶点运行DFS。
现在再次运行DFS，但这次从顶点开始，以减少完成时间。只对某些以前的DFS中未访问的顶点运行此DFS。如果我们在同一分量中找到一个交叉边或一个前向边，那么它就不是单连通的。
如果所有顶点都已完成，且没有这样的前向边交叉，则单连通。
O(V+E)
是这样的吗？或者有没有更好的解决方案。
更新:最简单的1条路径。
浏览 3提问于2013-11-12得票数 2
3回答
如何生成随机图？
、、、
我希望能够在Java中生成随机、无向和连通的图。此外，我希望能够控制图中的最大顶点数。我不知道解决这个问题的最佳方法是什么，但以下是我能想到的几个：
(1)在0和n之间生成一个数字，并将其设为顶点数。然后，以某种方式将顶点随机链接在一起(可能生成每个顶点的随机数，并让它成为从所述顶点产生的边数)。从任意顶点(比如宽度优先搜索)开始遍历该图，并让我们的随机图G成为所有访问节点(这样，我们确保G是连通的)。
(2)生成一个随机平方矩阵( 0's和1's)，其边长介于0和n之间(以某种方式)，这将是图的邻接矩阵(矩阵的对角线应该是1的，也可以是0的)，从图中构造一个数据结构，从任何节
浏览 7提问于2013-11-24得票数 11
回答已采纳
4回答
我试图将一个有向(无圈)图分裂成方向连通的路径，依赖于连通性：
当我测试弱连通子图和强连通子图时，我得到了以下内容：
Weak connectivity :
['16', '17'], ['3', '41', '39', '42']
Strong connectivity :
['17'], ['16'], ['39'], ['41'], ['3'], ['42']
我理解弱连通性的结果，但不理
浏览 0提问于2019-04-16得票数 2
回答已采纳
我需要帮助证明这个问题：
设G是k-连通图.证明了如果G‘是通过收缩边从图G中得到的，则G’是(k−1).
浏览 1提问于2016-05-03得票数 0
回答已采纳
1回答
我不知道一个无向图是否可以被认为是连通的？
例如：
甲
假设我们有三个顶点，A，B和C。如果图和上面的图一样是无向的，它是连通的吗？A到达B，但它到达C吗？
另一个例子是：
A->>B<-C
我说这个有向图不连通是因为A不能到达C，对吗？因为在我看来这张图不是多向的。
另一个例子是：
甲
这个无向图是连通的吗？
如果有人能详细解释的话，非常感谢。
浏览 1提问于2015-12-07得票数 1
回答已采纳
1回答
我有一个有向图G(V，E)。G可能包含循环。每个v以一个值nv开头。让我们调用S{v}，在G中v可以到达的所有顶点，对于每个v，我需要用max(nu)，u∈S{v}更新nv。
我尝试过使用快速联合和路径压缩，但我做不到，因为G是一个有向图。
一个选项是在每个节点上使用DFS，但是在最坏的情况下，复杂度是O(V(V+E))。
是否有更好的方法来处理它(可能使用拓扑排序、传递约简或强连通分量)？
浏览 2提问于2020-03-08得票数 2
回答已采纳
2回答
有没有一种算法，当给定一个图时，计算该图的顶点连通性(为了将该图分成两个连接的图而要删除的最小顶点数)。(请注意，该图可能已断开连接)。谢谢!
浏览 1提问于2013-04-14得票数 2
回答已采纳
2回答
我知道如何使用DFS变体找到无向图的交点。但它似乎是对无向图和只寻找后缘。但是，如果我的图有前向边或交叉边，我知道我总是可以为每个节点运行dfs，并且计算出它，但是有更好的算法吗？
浏览 3提问于2017-05-14得票数 0
1回答
我们随机选择两个顶点并将它们连接起来。那么，当图被连接时，期望的边数是多少呢？
我试着用归纳法解决这个问题，但没有找到答案。解决这个问题的正确方法是什么？
浏览 0提问于2012-02-01得票数 7
我试图对图形类的dijkstras算法执行测试。为了做到这一点，我生成了一个有几千个顶点的图，然后通过随机添加数千条边使图连通，直到这个图被连接。然后，我可以一遍又一遍地在任意两个随机顶点之间执行搜索，并确保它们之间有一条路径。问题是，我经常以一个几乎稠密的图结束，因为我使用的是邻接列表表示，导致我的搜索算法非常慢。
问题：给定一组顶点V，如何生成一个强连通有向图，它的边比同一顶点上的稠密图少得多？
我想做以下几件事：
vertex 1 <--> vertex 2, vertex 2 <--> vertex 3, ..., vertex n-1 <--> v
浏览 2提问于2015-01-09得票数 4
2回答
我读过Mkyong的这个伟大的关于Hibernate中一对多关系的文章，我对此有很大的怀疑。Mkyong在他的示例中使用了两个clase：Stock.java and StockDailyRecord.java
我认为类图必须是：“股票有许多库存透析记录”，因此，作为数据库实体关系图，必须是：“库存一对多的库存透析记录”。
但是Mkyong已经走得更远了，这里是我怀疑的地方。他设置了一个名为Stock stock on the StockDialyRecords class的属性。也就是说，他创造了一个的双向关系。这是对的？我知道这条路对ORM来说，我们可以朝两个方向走。但从图类来看，的观点是
浏览 1提问于2012-11-22得票数 0
回答已采纳
1回答
图分类
、、
我使用networkx进行图形分类、读取edgelist文件、分割训练、测试和检查火车组是否是连通图：
import networkx as nx
trainGraph = nx.read_edgelist('trainEdgelist.txt', create_using=nx.Graph(), nodetype=int)
nx.is_connected(trainGraph)
如果我想使用10倍交叉验证并使用以下内容：
from sklearn.model_selection import KFold
KFold(n_splits=10, random_state=None
浏览 3提问于2020-03-22得票数 1
回答已采纳
1回答
边的数量和周期检测？
、、、、
我遇到了一个具有挑战性的问题:当我们知道O(|V|)而不是O(|V|+|E|)的边数时，我们可以检测一个简单的无向图是否有圈。
我知道有一种O(|V|)算法可以用来判断循环是否存在。但是上面这句话说的是，边的数目是已知的吗？！！有没有人能描述它是真是假？
浏览 0提问于2015-02-12得票数 1
1回答
顶点度计数子图中的边数
、、、、
我有一个子图，它只被识别为一组已知度的顶点。
我想知道这个子图中有多少条边。有什么方法来计算这个吗？
请注意，不是每个边都在子图中。在子图中有连接顶点的边，在它的外部有连接顶点的边，所以它不能简单地算作顶点的度之和除以2。
如果这有什么帮助的话，我正在使用JGraphT。
浏览 1提问于2015-02-28得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
