标签: graph-theory

在学习图形算法和画布HTML元素时,它让我觉得我应该在javascript中有一个我自己的小图形库,它使用canvas元素显示图形,你可以指向正确的方向,这样我就可以阅读一些代码[js/python]至于如何显示图形和编写我自己的小lib.

PS:我的意思是边缘和节点不是条形图和饼图.

这是一个术语问题:

在有向图中,没有任何传入边(根)的节点名称是什么？

在我的以下示例(B)中:

我一直在阅读算法设计手册.我有同样的问题,这个最近邻算法中"来自不同的顶点链"是什么意思？但我无法按照那里的答案.

一个不同的想法可能是重复连接最接近的端点对,这些端点的连接不会产生问题,例如过早终止循环.每个顶点都以其自己的单个顶点链开始.在将所有内容合并在一起之后,我们将最终得到一个包含其中所有点的链.连接最后两个端点为我们提供了一个循环.在执行此最近对启发式过程中的任何步骤中,我们将有一组可用于合并的单顶点和顶点不相交链.在伪代码中:

ClosestPair(P)
    Let n be the number of points in set P.
    For i = 1  to n ? 1 do
        d = ?
        For each pair of endpoints (s, t) from distinct vertex chains
            if dist(s, t) ? d then sm = s, tm = t, and d = dist(s, t)
        Connect (sm, tm) by an edge
    Connect the two endpoints by an edge
Please note that sm and tm should be sm and …

是否存在确定性算法来检查图形是否包含从源到目的地的顶点不相交路径,具有复杂性O(nm^2)(n是顶点数,m是边数)或者是NP-Hard(如果是,为什么)？顶点不相交路径表示没有共同内部顶点的路径.例如.

s -> a -> b -> c -> d  
s -> x -> y -> z -> d

顶点不相交但是

s -> a -> b -> c -> d
s -> x -> a -> z -> d
          ^

不是因为a是常见的顶点.

完整的问题是:

假设我在边缘加权无向图中具有源节点S,目的节点D和中间节点P1,P2,P3 ......的集合A. 我想找到顶点丕∈A是最大限度地减少DIST(S,PI)+ DIST(d,PI) ？此外,从S到D的总路径应仅包含集合A中的一个节点.什么是有效的算法？我不想用蛮力的方法.

我知道已经有人问过这个问题，但它没有回答我的具体问题。我了解 Dijkstra 算法和 A* 算法的工作原理，并且 A* 是 Dijkstra 的一般情况。

通常说 A* 可以更快地找到解决方案，这在您使用加速过程/减少有效分支因子的启发式方法时是有意义的。

但我记得，要使 A* 返回最佳结果，您必须搜索成本低于目标成本的所有节点。这确保了最优性，而且据说不可能有更快的算法，因为 A* 着眼于所有节点 <= 目标成本，每个算法至少必须这样做。

但是迪杰斯特拉呢？它也只消耗节点 <= 目标成本，因为它在每一步都扩展了最小可能的路径。

如果您无论如何都必须扩展其他节点以确保最优性，那么 A* 启发式算法有什么用？此外，这两种算法似乎都有 n log n 的运行时复杂度

希望有人能解决这个问题:)

我试图找到一种算法来在无向连通图中找到子图，其中子图中的每个顶点都有一条到子图中每个其他顶点的边。

我真正的问题是我无法对这个问题进行分类，因此我可以研究可能的算法或解决方案。

有谁知道这个问题叫什么，或者是否有任何现有的算法可以实现这一目标？

我有一个由三行组成的矩阵:基因1,基因2,距离.

我想创建一个网络,每个基因都是一个节点,连接线按两个基因之间的距离缩放.

如何在不使用生物信息学或神经网络工具箱的情况下实现这一目标？

谢谢!

我知道算法是如何工作的——但是当使用优先级队列试图找到无法找到的目标节点时，它似乎只会在循环中无休止地反弹。

Dijkstra 的算法是否处理节点与图中断开连接的情况？

在一个用于分析算法的类中,我们为Kruskal算法提供了这个伪代码:

然后他说明了以下不相交的森林:

m个MAKE-SET,UNION和FIND-SET操作的序列,其中n个是MAKE-SET操作,可以在不相交的森林上执行,在最坏情况下的时间O( mα)中通过秩和路径压缩进行并联(n)).

用于计算步骤2和步骤5-8的复杂性

对于连接的G:| E | ≥| V | -1; m = O(V + E),n = O(V);

所以步骤2,5-8:O((V + E)α(V))= O(Eα(V))

α(V)= O(lg V)= O(lg E); 所以我们得到O(E lg E)----- //这里α(V)如何相等？

Kruskal:步骤3,5-8和步骤4:O(E lg E)

观察:| E | <| V | 2 - > lg E = O(lg V)

所以,Kruskal的复杂性:O(E lg V)

我试图理解这个"alpha(n)"/"α(n)"函数背后的逻辑,从我所读到的看来,简单地说,Ackermann函数是指数速度快得令人难以置信的,而且逆是以对数方式非常缓慢地增长.

如果我的解释是正确的,"α(n)"代表什么？这是否意味着MAKE-SET操作最多为O(lg n)？如何/为什么使用逆阿克曼是必要的？我的印象是这个操作执行V次(对于每个顶点).在此之后,α(V)也被简化为O(lg V)= O(lg E),这是否意味着,在最大值时,α(V)可以由O(lg V)表示.

另外,为什么是| E | <| V | ^ 2 - > lg E = O(lg V) …