标签: graph-algorithm

我正在寻找C++ Kruskal实现来对我自己的基准测试......如果你知道一些好的,请分享!

我的问题是关于检测是否存在循环.我不关心循环发生在哪里,但只有在存在循环的情况下.特别是,我正在研究(最大)生成树算法的实现.我按降序对边缘进行了排序,然后我选择了一条边并将其放入图形边缘IFF的集合中,它不会导致循环.

我发现,对于无向图,只能检查是否no_of_edges> no_of_vertices - 1.这是正确的吗？我试图找到一个不真实的案例,但我不能.当然,这并不意味着这是正确的.

谢谢

假设我想要父节点匹配某些条件的所有节点.

除了检查每个节点并构建一个充满节点或子树的结果对象之外,是否有一种可接受的方法可以做到这一点？

我有旋转矩形的四个2d顶点ABCD,我需要使用setpixel(x,y,color)在pixelbufer中光栅化/绘制它(有效)

怎么做？

我正在尝试使用一些代码

    // convertilg a b c d do up down left right, 
    // calculating some dx_left dx_right on y--
    // etc (frustrating on special cases when there are 2 up_y vertices in same line etc)


    for(;;)
    {

     drawhorizontalline(y, xstart, xend, color);

     if(y==downy) break;

     y--;
     xstart+=dxstart;
     xend+=dxend;

     if(y==lefty)  dxstart = dxright;
     if(y==righty) dxend = dxleft;

     }

但它是最令人沮丧的(非常容易出错和最令人沮丧)我真的厌倦了昨天整整这一天,我需要找到一些工作代码,而不是试图调试这个

我想在无向图中找到固定长度的路径(在运行程序时给出).我正在使用我的图的邻接矩阵.
我尝试使用一些算法,如DFS或A*,但它们只返回最短路径.

无法再次访问节点.

因此,假设我的图表有9个节点,最短路径是从4个节点构建的.
我希望有一个额外的变量,它将"告诉"我想要找到具有7个节点的路径的算法(例如),并且它将返回包含在我的预期路径中的节点{1,2,4,5,6, 7,8}.
当然,如果没有我想要的路径解决方案,它将不返回任何东西(或者它会返回接近我的表达的路径,让我们说19而不是20).

有人告诉DFS有回溯,但我对此一无所知.
有人可以解释如何使用DFS与回溯或推荐一些其他算法来解决这个问题？

正如问题所述.我似乎无法找出与纸张和铅笔结果相对应的公式.我正在寻找一个公式,在UNDIRECTED图中给出最大可能数量的三角形.

三角形被定义为形成循环的路径长度3的节点的任何连接.例如,如果我有1 < - > 2 < - > 3 < - > 1的图形是一个三角形(< - >是一个无向连接).如果三角形是什么不清楚,第2页的顶部有一个数字显示三角形在这个背景下的内容http://arxiv.org/pdf/1202.5230v1.pdf.

谢谢

我需要一个方法来查找有向无环图的根.我使用布尔邻接matix来表示java中的图.所以请建议.图也是未加权的图

我试图解决第6章 - 点位置"计算几何算法和应用,第3版 - 德伯格等人"一书的一些练习.不幸的是,我不知道如何解决以下练习:

Given a convex polygon P as an array of its n vertices in sorted order
along the boundary. Show that, given a query point q, it can be tested in
time O(log n) whether q lies inside P.

我的想法到目前为止: 我知道确定一个点是否位于O(log n)中的p内的唯一方法是使用有向无环图.为了使用有向无环图,我需要构建它,这在O(log n)中是不可能的.因此,我需要使用有序数组,但我所知道的唯一解决方案将花费O(N).

我希望有人可以帮助我.

我有一个有向图的nxn邻接矩阵.我想搜索以查看是否有任何列总和为n.问题是我必须在O(n)时间内完成这项工作.有没有办法用O(n)时间来处理这个问题或者是不可能的(不需要代码)？

供参考,以下是我要解决的问题:

问题:

在学校的乐队选举期间,每个人对总统有一些偏好,并且一个人的偏好一直包括他/她自己."完美"的总统是每个人都喜欢的人,除了他/她自己不喜欢任何人.我们想要知道的是这样一个人是否存在.

• 定义与所述一组候选作为顶点和从顶点的有向边的有向图一到顶点b当且仅当b是在该组的偏好的一个.
• 有n个人
• 我们想要一种在O(n)时间内执行的算法
• 我们以nxn邻接矩阵的形式给出了上述图形

我想如果每个人都投票给"完美的总统",那么他/她将有n个传入节点,因此总结列应该给我们n.如果有更好的方法来解决这个问题而不是我正在做的事情,那么任何提示都会受到赞赏,以指导我朝着正确的方向前进.

给定一个顶点为0到n-1的无向图，编写一个函数，该函数将找到最长的路径（按边数计），该路径的顶点顺序递增。

您会建议采用哪种方法来解决这个难题？