标签: graph-algorithm

任何人都可以在C#中实现Reverse Breadth First遍历算法？

通过反向宽度第一次遍历,我的意思是不是从公共节点开始搜索树,而是想从底部搜索树并逐渐收敛到公共节点.

让我们看下图,这是广度优先遍历的输出:

在我逆向广度优先遍历9,10,11和12将是第一个找到的几个节点(它们的顺序并不重要,因为他们都是第一顺序).5,6,7和8是发现第二几个节点,依此类推.1将是找到的最后一个节点.

任何想法或指针？

编辑:将"广度优先搜索"更改为"广度优先遍历"以澄清问题

我有一个算法问题,我在很多状态之间导出了一个传递矩阵.下一步是对它进行取幂,但它非常大,所以我需要对它进行一些减少.具体来说它包含很多对称性.下面是一些关于通过简单观察可以消除多少节点的示例.

我的问题是,是否有一种算法可以有效地消除有向图中的对称性,类似于我在下面手动完成它的方式.

在所有情况下,初始向量对于所有节点具有相同的值.

在第一个例子中,我们看到b,c,d和e所有的接收值a和对方的一个.因此,它们将始终包含相同的值,我们可以合并它们.

在这个例子中,我们迅速发现,该图形是从视图的点相同a,b,c和d.同样对于它们各自的侧节点,它附着在哪个内节点上也无关紧要.因此,我们可以将图形缩小到仅两个状态.

更新:有些人很合理,不太确定"国家转移矩阵"是什么意思.这里的想法是,您可以将重组问题分解为多个状态类型n.矩阵然后告诉你如何从获取n-1到n.

通常你只对你的一个州的价值感兴趣,但你也需要计算其他州,所以你总能达到一个新的水平.但是,在某些情况下,多个状态是对称的,这意味着它们将始终具有相同的值.显然,计算所有这些都是非常浪费的,所以我们希望减少图形,直到所有节点都"独特".

下面是示例1中缩小图的传递矩阵的示例.

[S_a(n)]   [1  1  1] [S_a(n-1)]
[S_f(n)] = [1  0  0]*[S_f(n-1)]
[S_B(n)]   [4  0  1] [S_B(n-1)]

任何建议或对论文的参考都表示赞赏.

我想在图中找到最近的边.请考虑以下示例:

图1: 黄色:顶点,黑色:边缘,蓝色:查询点

一般信息: 该图包含大约1000万个顶点和大约1500万个边.每个顶点都有坐标.边缘由两个相邻顶点定义.

最简单的解决方案: 我可以简单地计算从查询点到图中每个其他边缘的距离,但这将非常慢.

想法和困难: 我的想法是使用一些空间索引来加速查询.我已经实现了一个kd树来找到最近的顶点.但是如图1所示,入射到最近顶点的边缘不一定最接近查询点.我会得到边缘3-4而不是更近的边缘7-8.

问题: 是否有算法在图中找到最近的边？

我有一个节点的无线网状网络,每个节点都能够向其邻居报告它的"距离",以(简化的)信号强度测量它们.节点在地理上位于3d空间中,但由于无线电干扰,节点之间的距离不需要三角(三角)？一致.即,给定节点A,B和C,A和B之间的距离可以是10,A和C之间的距离也是10,但是在B和C 100之间.

我想要做的是根据节点的连接性来可视化逻辑网络布局,即包括视觉中节点之间的逻辑距离.

到目前为止,我的研究表明,多维缩放(MDS)就是针对这种事情而设计的.鉴于我的数据可以直接表示为2d距离矩阵,它甚至是更通用的MDS的更简单形式.

现在,似乎有许多MDS算法,例如http://homepage.tudelft.nl/19j49/Matlab_Toolbox_for_Dimensionality_Reduction.html和http://tapkee.lisitsyn.me/.我需要在C++中这样做,我希望我可以使用现成的组件,即不必从纸上重新实现算法.所以,我认为这是:https://sites.google.com/site/simpmatrix/将成为故障单.它有效,但是:

• 布局不稳定,即每次重新运行算法时,节点的位置都会发生变化(请参阅下面的图像1和2之间的差异 - 这是因为已经运行两次,没有任何进一步的更改).这是由于初始化矩阵(包含每个节点的初始位置,算法然后迭代地校正)传递给该算法 - 我传递一个空的矩阵,然后实现派生一个随机的.通常,布局确实接近我从给定输入数据预期的布局.此外,在不同的运行之间,节点的方向(顺时针或逆时针)可以改变.见下面的图3.

• 我认为很明显的"解决方案"是传递一个稳定的默认初始化矩阵.但是当我把所有节点放在同一个地方时,它们根本就没有被移动; 当我把它们放在一个轴上时(节点0在0,0;节点1在1.0;节点2在2.0等),它们只沿那个轴移动.(见下图4).但是它们之间的相对距离是可以的.

因此,似乎此算法仅更改节点之间的距离,但不会更改其位置.

感谢您阅读这一点 - 我的问题是(我很高兴只得到一个或几个回答,因为他们每个人都可能会给我一个关于继续前进方向的线索):

• 在哪里可以找到有关许多MDS算法的属性的更多信息？
• 是否有算法可以导出网络中每个节点的完整位置,而无需为每个节点传递初始位置？
• 有没有一种可靠的方法来估计每个点的位置,以便算法可以正确地缩放它们之间的距离？我没有这些节点的地理位置,这是本练习的重点.
• 是否有任何算法可以保持网络在运行之间的"角度"保持不变？

如果所有其他方法都失败了,我的下一个选择就是使用我上面提到的算法,增加迭代次数以保持运行之间的差异在几个像素左右(我必须试验需要多少次迭代)然后,"旋转"节点0周围的每个节点,例如,从左到右对齐水平线上的节点0和1; 这样,在通过MDS算法确定它们的相对距离之后,我将"校正"点的位置.我还必须纠正每个节点周围的连接节点(顺时针或逆时针)的顺序.这可能会很快变得毛茸茸.

显然我更喜欢稳定的算法解决方案 - 增加迭代以平滑随机性并不是非常可靠.

谢谢.

编辑:我被提到cs.stackexchange.com并在那里做了一些评论; 有关算法建议,请参阅https://cs.stackexchange.com/questions/18439/stable-multi-dimensional-scaling-algorithm.

图1 - 随机初始化矩阵:

图2 - 运行相同的输入数据后,与1相比旋转:

图3 - 与之前的2相同,但节点1-3在另一个方向:

图4 - 在一条线上的节点的初始布局,它们在y轴上的位置不会改变:

我一直试图理解二分图.据我所知,它是一个图G,可以分为两个子图U和V.So U和V的交集是一个空集,并且union是图G.我试图找到一个图是否是二分或不使用BFS .我还不清楚我们怎么能用BFS找到它.

我们假设我们的图表定义如下.

a:e,f
b:e
c:e,f,h
d:g,h
e:a,b,c
f:a,c,g
g:f,d
h:c,d

我需要的是逐步解释这个图是如何使用BFS的二分图.

我有一棵树作为广度优先搜索的输入,我想知道算法在哪个级别进展？

# Breadth First Search Implementation
graph = { 
    'A':['B','C','D'],
    'B':['A'],
    'C':['A','E','F'],
    'D':['A','G','H'],
    'E':['C'],
    'F':['C'],
    'G':['D'],
    'H':['D']
    }


def breadth_first_search(graph,source):
    """
    This function is the Implementation of the breadth_first_search program
    """
    # Mark each node as not visited
    mark = {}
    for item in graph.keys():
        mark[item] = 0

    queue, output = [],[]

    # Initialize an empty queue with the source node and mark it as explored
    queue.append(source)
    mark[source] = 1
    output.append(source)

    # while queue is not empty
    while queue:
        # …

我已经研究了两个图遍历算法,深度优先搜索和广度优先搜索.由于这两个算法都用于解决图遍历的相同问题,我想知道如何在两者之间进行选择.我的意思是比一个更有效其他或任何理由为什么我会在特定场景中选择一个而不是另一个？

谢谢

我一直在使用我编写的一个小蟒蛇脚本来管理我的室友之间的债务.它有效,但有一些缺失的功能,其中之一是简化不必要的复杂债务结构.例如,如果下面的加权有向图表示某些人,而箭头表示他们之间的债务(Alice欠Bob 20美元和Charlie $ 5,Bob欠Charlie 10美元,等等):

很明显,该图应简化为下图:

如果爱丽丝可以直接将它交给查理,10美元从艾丽丝到鲍勃,然后从鲍勃到查理,没有任何意义.

那么,在一般情况下,目标是采用债务图并简化它(即生成具有相同节点但不同边缘的新图),以便

1. 没有节点有边缘指向它的内部(没有无用的钱转手)
2. 所有节点都具有与原始图中相同的"流"(它们在资金最终位置方面相同).

通过"流量",我的意思是所有输入的值减去所有输出(这是否有技术术语？我不是图论专家).所以在上面的例子中,每个节点的流量值是:

• 鲍勃:+10
• 爱丽丝:-25
• 查理:+15

您可以看到第一个和第二个图表在每个节点上具有相同的流量,因此这是一个很好的解决方案.还有一些其他简单的情况,例如,可以通过移除最低值边缘并从所有其他边缘减去其值来简化任何循环.

这个:

应简化为:

我无法想象没有人研究过这个问题; 我只是不知道要搜索哪些术语来查找信息(再次,不是图论专家).我一直在寻找几个小时无济于事,所以我的问题是:根据上面针对任何加权有向图指定的条件,什么算法会产生简化(新图)？

我有一些无向图,我试图找到清晰点.有例子

它有一个关节点 - 顶点#2.

但我也想找到#4和#5作为清晰组点.因为联合移除#4,#5也将图形切割成未连接的子图.我想象示例图作为3个连接的子图.

我怎样才能找到指定的切点？

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