标签: graph-algorithm

我得到了有向图，其中有n个节点，边为具有向量1（0，-1）的向量（每个向量的长度为m）的维数。我想找到从一个节点到另一节点（我们可以多次访问节点）的任何路径（或者说这种路径不存在），这样其权重之和就等于零向量。我当时在考虑蛮力回溯算法，但不能保证它会结束。我们可以以n和m的方式限制这种路径的长度吗？n = 8，m = 2的图形示例 路径示例

正如标题所说,我正在尝试实现一种算法,该算法找出给定图形中所有节点对之间的距离.但还有更多:(可能有助于你的事情)

• 图表未加权.这意味着可以将所有边缘视为权重为1.
• |E| <= 4*|V|
• 图表非常大(最多144个深度)
• 该图是针对性的
• 可能有周期
• 我正在用python编写我的代码(如果你引用算法,那么代码也会很好:))

对于所有对,我都知道约翰逊的算法,Floyd-Warshal和Dijkstra.但是当图表具有权重时,这些算法是好的.

我想知道我的情况是否有更好的算法,因为这些算法用于加权图.

谢谢!

我有一个有限度量空间给定为(对称)k乘k距离矩阵.我想要一种算法(近似)在欧几里德空间R ^(k-1)中等距地嵌入它.虽然通过求解距离给出的方程组并不总是可以完成,但我正在寻找一种嵌入了一些(非常小的)可控误差的解决方案.

我目前使用多维缩放(MDS),输出维度设置为(k-1).在我看来,通常MDS可能会针对您尝试将环境嵌入维度减少到小于(k-1)(通常为2或3)的情况进行优化,并且可能有更好的算法用于我的限制案件.

问题:使用欧氏距离在R ^ {k-1}中实现大小为k的度量空间的好/快算法是什么？

一些参数和指针:

(1)我的k相对较小.说3 <k <25

(2)我实际上并不关心我是否嵌入了R ^ {k-1}.如果它简化了事物/使事情变得更快,任何R ^ N也会很好,只要它是等距的.如果我有一个更快的算法,或者如果我增加到R ^ k或R ^(2k + 1),我会很高兴.

(3)如果你可以指向python实现,我会更高兴.

(4)任何比MDS更好的东西都能奏效.

我尝试在不使用优先级队列(Heap)的情况下在循环加权图上使用Djikstra算法,并且它有效.

然后我搜索谷歌"为什么我们需要一个优先级队列来实现这个？" 作为搜索的结果,我浏览了维基百科,在那里我了解到原始实现不使用优先级队列并在O(| V | 2)中运行,即V平方时间.

现在,如果我们只删除优先级队列并使用正常队列,则运行时间是线性的,即O(V + E).

请有人建议那么为什么我们需要优先队列？

网站http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html描述了当使用邻接列表时,DFS和BFS具有复杂度O(V + E),如果使用邻接矩阵,复杂度为O(V ²).为什么是这样？

BFS,DFS和Dijkstra的实现几乎是一样的,除了BFS使用队列,DFS使用堆栈,而Dijkstra使用最小优先级队列？

更确切地说.我们是否可以对所有BFS,DFS和Dijkstra使用以下代码,Q是BFS的队列,DFS的堆栈和Dijkstra的最小优先级队列？谢谢!

Init d[]=Inf; // distance from the node s
Init c[]='w'; // color of nodes: 'w':undiscovered, 'g':discovered, 'b':fully explored
Init p[]=null; // previous node in the path
c[s]='g';
d[s]=0;
Q.push(s);
while(!Q.empty()) {
    u = Q.front();
    Q.pop();
    for v in adj[u] {
        if(c(v)=='w') {
            c[v]='g';
            if(d[u]+w(u,v)<d[v]) {
                d[v]=d[u]+w(u,v);
                p[v]=u;
            }
            Q.push(v);
        }
    }
    c[u]='b';
}

我们A是该图的邻接矩阵G = (V,E).A(i,j) = 1如果节点i和j边连接,A(i,j) = 0否则.

我的目标是了解是否G是非循环的.循环定义如下:

• i并j连接:A(i,j) = 1
• j并k连接:A(j,k) = 1
• k并i连接:A(k,i) = 1

我已经实现了一个解决方案,它按如下方式导航矩阵:

• 从边缘开始 (i,j)
• 选择O传出的边缘集合j,即j第 - 行中的所有1A
• O以DFS方式导航
• 如果从该导航生成的路径之一通向该节点i,则检测到循环

显然这个解决方案非常慢,因为我必须评估矩阵中的所有路径.如果A非常大,所需的开销非常大.我想知道是否有一种导航邻接矩阵的方法,以便在不使用昂贵的算法(如DFS)的情况下找到周期.

我想在MATLAB中实现我的解决方案.

提前致谢,

Eleanore.

我正在寻找一种方法来对给定的定向未加权图执行拓扑排序,其中包含循环.结果不仅应包含顶点的排序,还应包含给定排序违反的边集.这组边缘应该是最小的.

由于我的输入图可能很大,我不能使用指数时间算法.如果在多项式时间内无法计算最优解,那么对于给定的问题,什么启发式算法是合理的？

我正在寻找一个解释为什么AStar/A*算法被称为AStar.所有类似的(最短路径问题)算法通常都被命名为它的开发者,所以AStar代表什么？

我正在尝试使用igraph和实现单变量网络数据的分类工具包python.

但是,我的问题实际上更多的是关系分类领域的算法问题,而不是编程.

我正在关注网络数据文件中的分类.

我很难理解本文所指的" 网络唯一贝叶斯分类器 "(NBC),它是本文中解释的关系分类器之一.

我之前Naive Bayes使用单词包特征表示实现了文本数据的分类器.Naive Bayes关于文本数据的想法在我的脑海中清晰可见.

我认为这种方法(NBC)是将相同的想法简单地翻译成关系分类区域.但是,我对方程中使用的符号感到困惑,所以我无法弄清楚发生了什么.我也有在纸中使用的符号的一个问题在这里.

NBC 在论文的第14页有解释,

摘要:

我需要在第14页的论文中解释的" 仅网络贝叶斯分类器 "(NBC)的伪代码.

伪码表示法:

1. 让我们调用vs图中的顶点列表.len(vs)是长度.vs[i]是第i个顶点.
2. 假设我们有一个单变量和二元情形,即,vs[i].class或者是0或者1没有节点的其他给定特征.
3. 假设我们之前运行本地分类器,以便每个节点都有一个初始标签,由本地分类器计算.我只对关系分类器部分感兴趣.
4. 让我们调用v我们试图预测v.neighbors()的顶点,并且是邻居的顶点列表v.
5. 我们假设所有的边权重都是1.

现在,我需要伪代码:

def NBC(vs, v):
   # v.class is 0 or 1
   # v.neighbors is list of neighbor vertices
   # vs is the …