标签: graph-algorithm

这是与动态编程相关的另一算法问题

这是问题所在:

找到给定矩阵的最小总和,以便在每行和每列中选择一个

例如 :

3 4 2

8 9 1

7 9 5

最小的一个:4 + 1 + 7

我认为解决方案是网络流量(最大流量/最小切割量),但我认为它不应该像它那样难

我的解决方案:单独列出[column],column1,column2 ... column n

然后开始点(S) - > column1 - > column2 - > ... - >列n - >(E)终点并实现最大流量/分钟切割

有人能用简单的单词解释VF2算法的图形同构的步骤吗？我正在学习这个算法,但没有一个有效的例子就很苛刻.有人能引导我正确的方向吗？谢谢.

好的,这是我在Stack Overflow上的第一篇文章,我已经阅读了一段时间,真的很欣赏这个网站.我希望这是可以接受的问题.所以我一直在阅读Intro to Algorithms(Cormen.麻省理工学院出版社),我完全依赖于图算法.我一直在研究用于广度和深度优先详细搜索的正式算法.

这是深度优先搜索的伪代码:

DFS(G)
-----------------------------------------------------------------------------------
1  for each vertex u ? G.V
2      u.color ? WHITE       // paint all vertices white; undiscovered
3      u.? ? NIL
4      time ? 0              // global variable, timestamps
5  for each vertex u ? G.V
6      if u.color = WHITE
7          DFS-VISIT(G,u)

DFS-VISIT(G, u)
-----------------------------------------------------------------------------------
1  u.color ? GRAY          // grey u; it is discovered
2  time ? time + 1 
3  u.d ? time
4  for each v ? G.Adj[u]   // …

我试图准确理解这些算法是如何工作的,但我一直无法找到一个简单的解释.如果有人能提供或指出我对这些算法的描述比原始论文中的描述更容易理解,我将不胜感激.谢谢.

我正在尝试制作一个小型公共交通路线应用程序.

我的数据以下列结构表示:

graph = {'A': {'B':3, 'C':5},
     'B': {'C':2, 'D':2},
     'C': {'D':1},
     'D': {'C':3},
     'E': {'F':8},
     'F': {'C':2}}

哪里:

1. 图形dict键是一个节点
2. subdict键是2个节点之间的边
3. subdict value是边缘权重

我正在使用这里描述的find_shortest_path算法https://www.python.org/doc/essays/graphs/但由于递归而且它没有权重支持,所以它相当慢.

所以我转到Davide Epstein描述的算法http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/(甚至更好的实现可以在评论中找到使用heapq)

它工作得很好,它真的很快,但我只获得最佳路线而不是所有可能路线的列表.这就是我陷入困境的地方.

有人可以帮助我,或者至少给出指示？我在图最短路径算法方面不是很好.

提前致谢!

我有一个有趣的图论理论问题.我得到一个有三个节点和一组边的树T. 当然,T是无向的.每条边都有重量,表示必须访问多少次(至少).我们使用边缘从一个节点到另一个节点漫步,任务是找到满足上述条件的最少数量的所需步骤.我可以从任何节点开始.

例如,这棵树(括号中的边缘权重):

1 - 2(1)

2 - 3(1)

3 - 4(2)

4 - 5(1)

4 - 6(1)

我们需要8步才能走这棵树.例如:1-> 2-> 3-> 4-> 3-> 4-> 5-> 4-> 6

我不知道如何处理这个算法.是否有可能找到这个最佳旅游或者我们能不能直接找到这个最小数量？

我有一组节点和它们之间的有向边集.边缘没有重量.

如何找到必须添加的最小边数以使图形强连接(即应该有从每个节点到所有其他节点的路径)？这个问题有名字吗？

在Haskell的函数图像库(FGL),大部分的图形算法依赖于"匹配"功能,其中,由于一Node n和Graph g,退货c & g',其中c是Context的n,并且g'是图的其余部分(其中包含没有引用n).

我能看到这样做的唯一方法是检查每个上下文g并删除任何引用n并将它们添加到上下文中的边c.我相信,这需要线性时间.

马丁Erwig,谁写的图书馆,表明在这个文件,这个转换可以在不断的或至少子线性时间来完成.任何人都可以向我解释这是如何实现的吗？

我正在观看Robert Sedgewick关于快速联盟改进的视频.(https://youtu.be/sEo6LlPxpHE?t=267)

在那里他使用树的大小而不是高度.实际上问题是找到根节点.如果高度很高,发现将很困难.所以我们应该找到一种方法来减轻身高的影响.只有我们比较高度才能达到预期的效果？将较短的树连接到较高的树而不是解决问题而是:将具有较少节点数的树连接到具有较大节点数的树？

以下案例怎么样？

根据视频中的逻辑:

树的大小= 4

B树的大小= 7

如果你将A连接到B. 实际上我们正在使结果树更高(高度4).但是,如果我们基于树高度完成它,我们可以通过将树B连接到A来解决它.结果树的高度为3.

我对吗 ？如果错了我在哪里错了？

什么是枚举父图的所有子图的有效算法.在我的特定情况下,父图是一个分子图,因此它将被连接,通常包含少于100个顶点.

编辑:我只对连接的子图感兴趣.