标签: graph-algorithm

我正在研究Kruskal用于查找给定图形的MST的算法,并且我理解您必须首先将所有顶点视为森林的基本概念.之后,您必须找到最小边并将边的顶点连接到一个树中.并递归执行此操作,直到只剩下一个包含所有顶点的树.

我偶然发现了这个算法的以下实现.

#include<iostream.h>

int p[10];

void kruskal(int w[10][10],int n)
{
    int min,sum=0,ne=0,i,j,u,v,a,b;
    for(i=1;i<=n;i++)
    p[i]=0;
    while(ne<n-1)
    {
        min=999;
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(w[i][j]<min)
            {
                    min=w[i][j];
                u=a=i;
                v=b=j;
            }
        }
        while(p[u])
            u=p[u];
        while(p[v])
            v=p[v];
        if(u!=v)
        {
            ne++;
            sum+=min;
            cout<<"\nedge "<<a<<"-->"<<b<<" is "<<min;
            p[v]=u;
        }
        w[a][b]=w[b][a]=999;
    }
    cout<<"\nmin cost spanning tree= "<<sum;
}

void main()
{
    int w[10][10],n,i,j;
    clrscr();
    cout<<"enter no.of vertices\n";
    cin>>n;
    cout<<"enter weight matrix\n";
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cin>>w[i][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(w[i][j]==0)
                w[i][j]=999;
    kruskal(w,n);
}

我不明白的是需要:

while(p[u])
    u=p[u];
while(p[v])
    v=p[v];

这两个while循环究竟做了什么？

编辑:以及 - 的必要性 …

这似乎是一个常见的调度问题,但我没有看到解决方案,甚至没有看到问题.它就像拓扑一样,但不同......

比如说有一些依赖性

A -> B -> D -- that is, A must come before B, which must come before D
A -> C -> D

拓扑排序可能有多种解决方案:

    A, B, C, D
and A, C, B, D

都是解决方案.

我需要一个返回这个的算法:

(A) -> (B,C) -> (D)

也就是说,做A,然后是B和C的全部,那么你就可以做D.所有歧义或不关心都是分组的.

我认为像Topological Sort with Grouping那样的算法不能正确处理如下情况.

A -> B -> C -> D -> E
A - - - > M - - - > E

为此,算法应该返回

(A) -> (B, C, D, M) -> (E)

这个

A …

要找到无向图G的最小支配集,您可以使用如下的贪婪算法:从空集开始D.直到D是支配集,添加具有最大数量的未覆盖邻居的顶点v.

该算法通常没有找到最优解,它是ln(Delta) - 近似.(如果Delta是G中顶点的最大度数)

现在我正在寻找一个简单的例子,其中贪婪算法找不到最佳解决方案.我找到的唯一一个是集合覆盖问题的相关实例.(http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm图片右侧)将此图片转换为图表将导致至少14个顶点和大量边缘.

有谁知道一个小例子？

提前致谢

什么是获得输入文件或std out数据流的大致行数的最快方法.仅供参考,这是一个概率算法,我在网上找不到很多例子.

数据可能只是来自csv文件的awk脚本的一列或两列!让我们说我想在其中一个列上使用aprox groupby.我会使用数据库组,但行数超过6-7亿.我希望第一个近似结果在3到4秒内.然后在对先前做出决定之后运行贝叶斯或其他东西.关于一个非常粗略的初始组计数的任何想法？

如果你可以在python或java中提供算法示例,那将非常有帮助.

我有一组例如8分.我知道每个点之间的所有距离.是否有算法重建这些点的三维坐标.

我有一个网格,网格有两个"材料" -

• 地板
• 壁

例如 :

在这个网格中,我们有对象具有大小和位置(对象的位置是左上角).

在每个对象上我们可以做一些动作,如 -

• 提升
• 下移
• 向左移动
• 向右移
• 转动物体(相对于左上角)

我需要创建一个函数来返回我需要对对象执行的最小操作量,以便将它从一个点移动到另一个点(我只需要操作量).

我使用dijkstra的算法解决了这个问题,但没有转弯动作.

所以任何人都可以帮我构建这个功能.

问题的例子 -

• 起点 -

• 终点

我需要返回我需要对对象执行的最少量操作.

我之前参加了考试,有一个问题困扰着我和我交谈的其他人.它问了以下问题:

给出一个未加权的图G和两个顶点s和f的例子,这样s和f之间有一条最短路径,即广度优先搜索(从s开始)将永远不会找到,无论它访问邻近的顶点的顺序如何特别的优势.

对我们来说,这似乎不可能.我的第一个想法是,如果最短路径包含一个顶点作为其第n个步骤,可以从s以m步长到达,其中m < n,那么BFS将永远不会找到该路径,因为顶点已经被标记为参观.但如果是这种情况,所述路径根本不是最短路径,因为通过以m步进入顶点然后继续正常而获得的路径更短.

我们的教授提出了一个不可能的问题(可能是一个错字),还是我错过了什么？

编辑:为了消除任何可能的歧义,问题并没有要求举例说明BFS无法找到从s到f的最短路径.相反,它要求给出一个例子,其中存在从S到f的一些最短路径,BFS将永远找不到.因此,BFS完整且最优的事实并不排除这种可能性,除非我误解了这些术语的含义.

编辑2:也可以假设我们正在使用的BFS算法不会两次处理同一节点.例如,请参阅BFS Wiki上的算法大纲.

我想找到两个顶点之间有最短约束的最短路径：最多可以访问n个顶点。该图是有向图，连接图，非负图，可能包含循环。

例：

1. 最短路径0-> 2与n = 2时是18
2. 最短路径0-> 3与n = 3的是22
3. 最短路径0-> 3与N = 4是9

到目前为止，我已经实现了Djikstras算法来获得最短的最短路径，而我的想法是保持当前访问的顶点的计数，如果超过n，它会往后退一步，然后尝试另一条路径。据我所知，Djikstras不能如这里所述用于回溯。

另一个想法是以某种方式存储表中每个节点之间的每个路径。但我不确定Djikstra如何找到权重为18的0-> 2路径，因为它实际上并不是最短的路径...

有谁知道如何解决这个问题？

我有一个问题,理解Djisktra算法的复杂性,希望有人能纠正我.

在我的例子中,我拍摄了一个包含n个顶点的完整图形.

你选择一个起始顶点,让我们说a1,标记它,然后计算边上的所有n-1权重.上)

你挑选最小的一个.让我们说顶点a2并标记它.上)

之后,您在边缘上计算n-2个新权重,并查找下一个未标记的顶点以添加您标记的顶点集.

等等...

算法运行直到您可以标记所有顶点.复杂性:n-1 + n-2 + ... + n - (n - 1)= Binom(n,2),它在O(n ^ 2)中,而不是O(n*ln(n))我是什么想.

我读了很多次人们使用堆进行优化,但是我仍然没有看到如何避免Binom(n,2)计算.

我不得不在某些方面做错,但不要看到哪里.

题

在有向无环图（DAG）中，是否总是通过反转要添加的关系来防止由于添加关系而导致的循环传递关系？

例：

• 现有关系：A -> B，B -> C以及通过该传递关系A -> C，因此可以将其视为A -> B -> C
• 要添加的关系：C -> A这将导致A -> B -> C -> A循环
• 想法：将要添加的关系求反，C <- A这将导致A -> B -> C <- A并因此仍然是非循环的

这里给出的示例当然很简单，因此我想知道这种方法在所有情况下是否可行。

背景

为了建模实体之间的有向关系（例如，“跟随”，“先行”，“父”，“子”），OpenProject应用程序将其关系信息存储在有向非循环图（DAG）中。实体/节点具有日期信息，并且可以由用户重新安排。如果用户更改日期值，则可能需要自动重新安排其他实体的时间，例如，当将前任转移到未来两天时，还需要转移其后继者。

由于大多数关系都用于调度，因此正因为它是一个非循环图，所以避免了循环。它们将导致无限的调度循环。

尽管大多数关系也从语义的角度出发指明方向，但也存在通用的“相对于”关系，该关系相对于用户是无向的，只是传达存在某种关系的信息。由于其性质，前端中的用户看不到DAG中存在的“与...相关”关系的方向方面。

当用户尝试创建“相对于”关系时，他当前可能会遇到错误消息，警告循环关系，这对于用户来说是不可理解的，因为他对关系的理解是无向的。

有两种可能的方法可以解决该问题，最简单的方法是在这种情况下简单地逆转该关系，因为DAG内的方向对于这种关系对用户而言并不重要。