相关疑难解决方法(0)

如何从有向图中找到(迭代)有向图中的所有周期？

例如,我想要这样的东西:

A->B->A
A->B->C->A

但不是:B-> C-> B.

给定具有n个顶点(| V | = n)的无向图G =(V,E),如何找到它是否包含O(n)中的循环？

我知道这个问题有很多答案.但是,我发现它们中没有一个能够真正实现它.
有人认为一个循环(几乎)与强连通组件相同(s.在有向图中查找所有循环),因此可以使用为该目标设计的算法.
有人认为找到一个循环可以通过DFS完成并检查后端(s.文件依赖关系的boost图文档).

我现在想对是否可以通过DFS检测图中的所有循环并检查后沿有一些建议？
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf(在SO上找到)陈述了一种基于循环基础的方法.我个人而言,我觉得它不是很直观,所以我正在寻找一个不同的解决方案.

编辑:我最初的意见显然是错误的.S."Moron"的下一个回答.
初步意见:我的观点是它确实可以这样工作,因为DFS-VISIT(DFS的伪代码)刚刚进入尚未访问过的每个节点.从这个意义上讲,每个顶点都表现出一个潜在的循环开始.此外,由于DFS每次访问每个边缘,因此也会覆盖通向循环起点的每条边.因此,通过使用DFS和后沿检查,确实可以检测图中的所有周期.注意,如果存在具有不同数量的参与者节点的循环(例如,三角形,矩形等),则必须进行额外的工作以区分每个循环的实际"形状".

如果我有一个无向图,我怎样才能获得所有周期的列表？

例如,从下图中,我想要循环:

(a,b,d,e,c)
(a,b,c)
(b,d,e)

我从昨天开始就被这个问题困住了。不幸/幸运的是，这个问题只占我超级庞大（对我来说，一个 c++ 新手）算法的 0.5% 左右，因此需要一个现有代码库，一个可以适应并让事情正常工作的现有代码库。

我想检测并给出无向图中的所有圆圈。我的边缘没有加权。是的，我真正需要的是所有循环，即类似于有向图的所有哈密顿循环

我一直在玩boost图库，DFS算法似乎很有前途，但是，它只访问顶点一次，因此不能给出所有的哈密顿圆。

目前，我只需要代码工作，这样我就可以继续我的算法设计，之后我可能会考虑性能问题。即使是带有 5 个嵌套 for 循环的解决方案也是受欢迎的。

这是我从 boost 得到并玩过的代码，但我不知道如何记录和访问我的 back_edges 的前辈，即使解决了，boost DFS 也只会访问顶点一次：

struct detect_loops : public boost::dfs_visitor<>
{
   template <class Edge, class Graph>
   void back_edge(Edge e, const Graph& g) {
      std::cout << source(e, g)
        << " -- "
        << target(e, g) << "\n";
   }
};

int main(int,char*[])
{
    typedef std::pair<int,int> Edge;
    std::vector<Edge> edges;
    edges.push_back(Edge(0,1));
    edges.push_back(Edge(1,2));
    edges.push_back(Edge(2,3));
    edges.push_back(Edge(3,1));
    edges.push_back(Edge(4,5));
    edges.push_back(Edge(5,0));
    edges.push_back(Edge(4,0));
    edges.push_back(Edge(5,6));
    edges.push_back(Edge(2,6));

    typedef adjacency_list<
       vecS, vecS, undirectedS, no_property,
       property<edge_color_t, default_color_type>
    > graph_t;
    typedef …

请参阅图片：http：//i.stack.imgur.com/NPUmR.jpg

我有一个无向图，其中包含一个或多个连接的子图。该图由一组连接的顶点的有序对定义。最多可能有300个顶点。该图是平面的。

我需要识别图像中所示的多边形。每个单独的多边形中的彩色区域。粗略的试探法可能是，多边形是图形中封闭边缘环（循环）之间的“封闭区域”。在类似的帖子中已经建议可以使用“深度优先”遍历并标记访问的顶点来标识周期。

但是，我不确定在此之后如何进行操作以获取所需的输出，如图中所示。

要求 ：

i）多边形不得重叠或相交。即：循环ABFHDCA不是有效的多边形，因为它将与多边形FHGE重叠。循环ABFEGHDCA是有效的多边形。

ii）多边形可以具有3个或更多的边，并且多边形必须以图形的边为边界。XYZ是有效的多边形，尽管与图的其余顶点断开了连接。

iii）诸如K和L（即叶子）之类的顶点不构成多边形的一部分。我们不在乎边缘JK。

更新： iv）在图中，边不交叉。两条边只能相交的地方是顶点。通过前一阶段/算法可以保证确实如此。

问题：

1. 我是否在使用DF纵行寻找轨道方法的正确轨道上？在这种情况下，DF遍历会给我提供我需要考虑的所有（简单）循环吗，尤其是在XYZ与图的其余部分断开连接的情况下？

2. 是否存在解决此问题的替代算法？

附加条款：

a）我在用更具体的计算几何术语来定义此问题时遇到了麻烦，因此坚持在无向图内查找多边形。我必须承认，自从学习图论以来已经有好几年了。我现在正在整理。

b）对此的解决方案似乎不是凹/凸包算法。我们正在谈论的是一组相连的边-真正的多边形，而不仅仅是需要包含的点云。

c）上面的示例是我可以在短时间内提出的。我认为它涵盖了大多数“边缘”情况（双关语）:)

类似解决方案

1. 我发现了类似的帖子，但是被接受的解决方案似乎无法为该示例生成正确的周期。

提前致谢！

我有一个由边和顶点G组成的图。中的顶点以二维坐标表示。该图是平面的，这意味着没有两条边相交。{E}{V}{V}

图G有一些循环，假设一个点落在图的内部，如果它落入 的一个循环中G。循环示例可以是A---B---C---A，其中A、B和C是顶点，---是边。

现在给定一个点(x, y)，如何确定它是在图内还是在图外？最好的方法或最简单的方法是什么？

我正在使用Python，如果有帮助的话。

更新：是的，所有边缘都是直线。

REWRITE:我对这个问题没有得到太多反馈,我认为我没有正确地写它并试图澄清.

我正在制作一个让人们创建国家的计划.下图中的粗红线是所述国家的边界​​.我试图弄清楚如何生成一个多边形,填充"边框"线内的整个区域.我有接受多边形工作的三角测量代码 - 我用手动输入的多边形测试了 - 现在我想弄清楚如何从线/链接点生成多边形.

有关详细信息 - 所有红线都是黄点连接在一起的方式.用户将黄点拖动到一起以链接线条.多边形可能在内部有一个洞并且是开放的 - 我要做的是制作处理开放多边形的代码和在其中有孔的多边形,并生成所有黄点位置的输出(带有x和z的vector3)对于我的三角测量代码,它位于y平面上的0处).

我仍然想方设法解决这个问题,但我还没有想出去哪里开始寻找解决方案.谢谢你的帮助.

以下老问题

我试图找到一种方法将点链接在一起形成一个内部多边形.基本上,我正在创建一个程序,让人们将线路连接在一起.在形成闭合多边形之后,应该在线内生成新的多边形对象.

我不太确定如何做到这一点 - 我已经做到了这样它们可以生成线条并将它们链接在一起,但如何做一个封闭的多边形让我感到惊讶.我看着凸壳,但这是不一样的,并尝试寻找或思考一些似乎不起作用的不同的东西.我很好奇是否有人能指出我的写作方向/关于如何继续创作的教程或想法.

我上传了两张照片以帮助显示我的观点.

上面是我想要做但不太确定的方法 - 基本上,当用户完成一个闭合的多边形(所有的黄色点都是多边形的外部点)时,我希望它生成一个内部多边形(由黑色1标记, 2和3).

我正在使用算法第4版来稍微改进我的图论.这些书附带了大量的图形处理代码.
目前,我遇到了以下问题:如何在无向图中找到所有周期？我想修改现有的循环检测代码来做到这一点.

这是重要的部分:

private void dfs(Graph G, int u, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if cycle already found
            if (cycle != null) return;

            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, v, w);
            }

            // check for cycle (but disregard reverse of edge leading to v)
            else if (w != u) {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[x]) …

给定N边线图中的点，Map<Point, List<Edge>>可以得到这些边线形成的多边形O(N log N)？

我知道的是，您必须遍历所有顶点，并以包含该顶点的边为起点。这些是voronoi图的边缘，每个顶点最多包含3个艺术家。因此，在映射中，键是顶点，值是列表，其中顶点是起始节点。

例如：

要点：a,b,c,d,e,f,g

边缘：[a,b]; [a,c]; [a,d], [b,c], [d,e], [e,g], [g,f]

我的想法是逆时针迭代地图，直到获得初始顶点。那是一个多边形，然后我将其放在多边形列表中，然后继续寻找其他多边形。问题是我不想克服复杂性O(N log N)

谢谢！