标签: graph-algorithm

我正在为.net框架寻找一个开源(GPL,LGPL等)图形布局库,最好是完全托管代码.我并不担心事物的可视化方面.

我可以找到很多用于Java的,但没有用于.net ...

谢谢!

我正在尝试使用networkx作为图形表示在Python中实现Hopcroft Karp算法.

目前我就是这样:

#Algorithms for bipartite graphs

import networkx as nx
import collections

class HopcroftKarp(object):
    INFINITY = -1

    def __init__(self, G):
        self.G = G

    def match(self):
        self.N1, self.N2 = self.partition()
        self.pair = {}
        self.dist = {}
        self.q = collections.deque()

        #init
        for v in self.G:
            self.pair[v] = None
            self.dist[v] = HopcroftKarp.INFINITY

        matching = 0

        while self.bfs():
            for v in self.N1:
                if self.pair[v] and self.dfs(v):
                    matching = matching + 1

        return matching

    def dfs(self, v):
        if v != None:
            for …

我正在考虑在有向图中找到负权重循环的算法.问题是:我们有一个图G(V,E),我们需要找到一个有效的算法来找到负权重的循环.我理解本PDF文档中的算法

简而言之,该算法通过迭代| V | -1次进行松弛来应用Bellman Ford算法.之后它会检查是否有一条甚至可以放松的边缘,然后存在一个负的重量循环,我们可以通过父指针追溯它,一切顺利,我们发现负重量循环.

然而,我正在考虑另一种在图上使用深度优先搜索(DFS)的算法,通过跟踪到目前为止所经过的距离的总和,我在开始时将所有节点标记为白色并在我使用时将它们设置为灰色搜索一个路径,并在它们完成时将它们标记为黑色,这样我知道我找到一个循环当且仅当我找到一个被访问的节点并且它是灰色的(在我的路径中),而不是黑色已经完成了深度 - 首先搜索,对于我的算法,如果我到达一个已经访问过的灰色节点,我会检查它的更新是什么(新的距离),如果它比以前低,我知道我有一个负重循环并可以追溯它.

我的算法错了吗？如果是这样,你能找到一个反例吗？如果没有,你能帮我证明一下吗？

谢谢

您将使用什么算法来创建给定适当数据的应用程序(城市列表,列车路线,火车站)能够返回任何两个用户选择的城市之间的连接列表？应用程序必须只选择那些属于已接受的列车更改限制的连接.

示例:如果我需要从巴黎到莫斯科旅行,我会询问应用哪条火车.1站/开关 - 应用程序返回路线:火车1(巴黎 - 柏林) - >火车2(柏林 - >莫斯科)(不存在直接连接).

图形示例

http://i.imgur.com/KEJ3I.png

如果我向系统询问从A 镇到G 镇的可能连接,我会收到回复:

• 棕色线(0开关=直接)
• 布朗线到B镇/橙线到G镇(1个开关)
• 布朗线到B镇/橙色线到D镇/红线到G(2个开关)
• ......所有其他可能性

而且你的第二和第三选项比第一选项更短,它应该是优先考虑的第一选项(因为不涉及列车切换).

我们假装我有以下网格.我必须连接成对的字母.不仅必须连接相同的字母,而且还必须确保连接路径不会相互交叉.什么算法可以告诉我是否可以连接所有对而没有交叉路径和最短路径？

我意识到这是一个图形问题,可以使用BFS解决最短路径部分.我不确定的是过路.

  +---+---+---+---+---+---+---+---+
  | A |   |   | B |   |   |   |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +-------------------------------+
  |   |   | B |   |   |   | D |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +-------------------------------+
  |   | C |   |   | C |   |   |   |
  +-------------------------------+
  |   |   |   | A |   |   |   |   |
  +-------------------------------+
  |   |   |   |   |   |   | D |   | …

我正在研究分支机构和最好的第一次搜索我的论文工作,但在网络上发现了很多关于这两个概念的矛盾.首先,我认为分支和绑定仅修剪以高成本解决方案结束的分支(使用启发式)并且不优先搜索(在修剪之后对树的其余部分执行简单的DFS或BFS).然而,后来我发现许多资源说BB也对状态进行排名,并且首先考虑具有更高排名的节点(优先搜索).如果是这样,BB和最佳优先搜索之间究竟有什么区别？

我想做一些类似于约会调度算法的事情(N个人有N个自由忙插槽,约束满足).使用Hopcroft-Karp算法.但我的额外要求是我的时间间隔是重叠的.例如.时段可以是上午10点至11点或上午10点15分至11点15分.所以如果我选择上午10点到11点的时段,我不想选择上午10点15分到11点15分.是否有可能在不严重影响性能的情况下实现这一目标？

正如您可以看到下面的示例图片,我的问题是如何确定由一系列点形成的多边形.

1. 在左图中,点的系列是{A,B,C,D,E,A},因此它只形成1个多边形{A,B,C,D,E}.

2. 在图片的右侧,一系列点是{A,B,C,D,E,F,A}.它创建了2个多边形{A,F,G }和{B,C,D,E,G },其中G是来自线AB和FE的交点.

我不仅对多边形的数量感兴趣,而且我还想知道从它创建的多边形信息(多边形的一系列点).

该算法将在移动设备中实时使用,因此必须足够快才能进行计算.哦,一系列点将由用户的拖动触摸点生成.

假设:

1. 仅由2个共线点组成
2. 它并不总是闭链多边形.例如,从右边的图片中,一系列点是{A,B,C,D,E,F},没有边缘FA.

我一直在考虑解决方案,并且为了查看交叉点,我坚持使用O(N ^ 2)解,N =边数.我可以做的优化是在一些区域内维护线组,所以我只是最小化可以相互计算的总线数.

至于提取形成多边形的解决方案,我仍然卡住了.

我在想一个算法来解决下面的问题:

由顶点和边组成的给定图.

有N个客户想要从顶点行进到另一个顶点.每个客户需求都需要一个有向边来连接两个顶点.

问题是如何找到满足所有客户要求的最小边数？

有一个简单的例子:

• 客户1想要从顶点a行进到顶点b.
• 客户2想要从顶点b行进到顶点c.
• 客户3想要从顶点a行进到顶点c.

最简单的方法是为每个客户提供优势:

• 边1:顶点a - >顶点b
• 边2:顶点b - >顶点c
• 边3:顶点a - >顶点c

但实际上只需要2个边缘(即边缘1和边缘2)来满足三个客户的要求.

如果客户数量很大,如何找到满足所有客户要求的最小边缘？

有没有算法来解决这个问题？

在n人中," 名人 "被定义为 每个人都知道但不认识任何人的人.问题是识别名人,如果存在的话,只询问表格的问题," 对不起,你知道那边的那个人吗？ "(假设所有的答案都是正确的,甚至那个名人也会也回答.)目标是尽量减少问题的数量.

这个订单的解决方案是否少于明显的解决方案O(n^2)？