若图有交叉边，则无论图是否单连通
当我看《算法概论3》时，遇到下面这个问题。
22.3-13*有向图G是单连通的，如果u->v暗示G对所有顶点v至多包含一条从u到v的简单路。给出了一个判定有向图是否单连通的有效算法。
但我对这种情况表示怀疑。举个例子，如果图的所有边（A->D,D->E,E->A,B->C,C->A)，DFS从A开始，因此C->A是交叉边，但我认为这个图是单连通的。对不起，我无法上传图片，因为StackOverflow的权限。
共有1个答案
图中可能存在交叉边，也可能存在圈，图将是单连通的（SC）。如果我们有前向边，很明显我们有两条路径到目的地v。但在这种条件下，如果我们有交叉边，图就不是SC：：假设ab或zb是图中的交叉边，如果a和z之间有一条路径，图就不是SC，如果我们没有相同的路径，图就绝对是SC。如果ab（或zb）是我们的交叉边，那么a和Z之间不应该有路径。
-
给定一个节点和边的加权无向图。边缘权重（整数）最大可达。存在查询。每个查询给出两个节点和一个整数绑定的。如果和之间存在路径，使得路径中的每个边权重都是，那么回答是else。 请注意，路径不一定要最短。路径上的最大权重是。天真的方法当然是行不通的。如何快速回答查询（在O(n，lg，n)或类似的情况下）？
-
我把《算法导论》第3版第22行22.3-13中单连通图的定义引用为。我注意到图中的圈并不一定意味着图不是单连通的，因为包含圈的路径不被认为是简单路径。有向图中的一个简单圈可以由相应的边集唯一地表示。让我们考虑一个满足以下两个性质的有向图: (1)它的DFS林中只有树边和后边，(2)图中表示每个简单圈的集合都是不相交的（即它们不共享任何边）。现在我的问题是：满足以上两个条件的有向图一定是单连通图吗？
-
在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。 因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。 一、简介 有向无环图是图论的重要概念，我们将首先介绍图的概念和定义，随后介绍有向图，再逐渐引至有向无环图（DAG）。值得一提的是，当DAG用于指代模型时一般指向贝叶斯网络。 一个图G
-
交叉表图表也称为文本表，以文本形式显示数据。 交叉表图表采用一个或多个维度以及一个或多个度量。此图表还可以显示度量字段值的不同计算，例如总百分比，运行总计等。 例如，如果要查找每个区域中每个细分的销售数量，请考虑数据源：Sample-Superstore。要使用下面的可用订单日期显示每年的数据，请参阅创建交叉表图表的一些步骤。 第1步：将维度订单日期拖到列架中。 第2步：此外，将维度Region和
-
根据CLRS第3版的定义，单连通有向图是指每对顶点(u，v)至多有一条唯一的路从u->v来的图。现在我读过的大多数答案都说，我们从图中的每个顶点运行DFS，如果在任何情况下我们找到一条交叉边或一条前向边，那么图就不是单连通的。我可以理解前向边的概念，但是在这个图上运行这个algo 1-->2<--3将给出一个结果：它不是单连通的，而这个图是单连通的。我们有一个从3->2或1->2的交叉边，这取决于