标签: graph-algorithm

我理解DFS和BFS之间的区别,但是我很想知道何时使用一个比另一个更实用？

任何人都可以举例说明DFS如何胜过BFS,反之亦然？

如何从有向图中找到(迭代)有向图中的所有周期？

例如,我想要这样的东西:

A->B->A
A->B->C->A

但不是:B-> C-> B.

在以下方面,段树,间隔树,二进制索引树和范围树之间有什么区别:

• 关键思想/定义
• 应用
• 更高维度/空间消耗的性能/订单

请不要只给出定义.

我试图理解为什么Dijkstra的算法不适用于负权重.阅读最短路径上的示例,我试图找出以下场景:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

来自网站:

假设边缘全部从左向右指向,如果我们从A开始,Dijkstra算法将选择最小化d(A,A)+长度(边缘)的边(A,x),即(A,B).然后设置d(A,B)= 2并选择另一个边(y,C),使d(A,y)+ d(y,C)最小化; 唯一的选择是(A,C),它设置d(A,C)= 3.但它从未找到从A到B的最短路径,通过C,总长度为1.

我无法理解为什么使用Dijkstra的以下实现,d [B]将不会更新为1(当算法到达顶点C时,它将在B上运行放松,看到d [B]等于2,因此更新它的价值1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ? Ø
   Q ? V[G]//priority queue by d[v]
   while Q ? Ø do
      u ? Extract-Min(Q)
      S ? S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v ? V(G)
      d[v] ? ?
      ?[v] …

Dijkstra的算法教给我如下

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

但是我一直在阅读关于算法的一些阅读,我看到的很多版本都使用了reduce-key而不是insert.

为什么会这样,这两种方法之间有什么区别？

我正在关注Steve Yegge关于准备技术编程访谈的建议:http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

在他关于图表的部分中,他指出:

在内存中表示图形有三种基本方法(对象和指针,矩阵和邻接列表),您应该熟悉每种表示及其优缺点.

CLRS中描述了矩阵和邻接列表表示的优缺点,但我无法找到将这些表示与对象表示进行比较的资源.

只要想一想,我就可以自己推断一些,但我想确保我没有错过一些重要的东西.如果有人能够全面地描述这一点,或者指向一个这样做的资源,我将非常感激.

我正在OpenStreetMap地图上写一个快递/物流模拟,并且已经意识到如下图所示的基本A*算法对于大型地图(如大伦敦)来说不够快.

绿色节点对应于放置在开放集/优先级队列中的绿色节点,并且由于数量巨大(整个地图大约为1-2百万),需要5秒左右才能找到所示的路线.不幸的是,每条路线100毫秒是我的绝对限制.

目前,节点存储在邻接列表和空间100×100 2D阵列中.

我正在寻找可以在预处理时间,空间和路线最佳性能之间进行权衡的方法,以便更快地进行查询.根据剖析器,启发式成本的直线Haversine公式是最昂贵的函数 - 我尽可能地优化了我的基本A*.

例如,我在想是否从2D阵列的每个象限中选择一个任意节点X并在每个象限之间运行A*,我可以将路径存储到磁盘以供后续模拟.查询时,我只能在象限中​​运行A*搜索,以便在预先计算的路径和X之间进行搜索.

是否有我上面所描述的更精致的版本,或者我应该追求的另一种方法.非常感谢!

为了记录,这里有一些基准测试结果,用于任意加权启发式成本并计算10对随机选取的节点之间的路径:

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

令人惊讶的是,将系数增加到1.1几乎将执行时间减半,同时保持相同的路线.

我正在寻找一种简单的算法来"序列化"有向图.特别是我有一组在执行顺序上具有相互依赖性的文件,我想在编译时找到正确的顺序.我知道它必须是一件相当普遍的事情 - 编译器会一直这样做 - 但我的google-fu今天一直很弱.什么是'go-to'算法？

我有一个无向的正边缘权重图(V,E),我想要一个覆盖顶点V的子集k的最小生成树(Steiner树问题).

我不是将生成树的大小限制为k个顶点; 而且我确切地知道MST中必须包含哪些 k个顶点.

从整个MST开始,我可以削减边缘/节点,直到我得到包含所有k的最小MST .

我可以使用Prim算法来获取整个MST,并开始删除边缘/节点,同时不破坏子集k的MST; 或者我可以使用Floyd-Warshall获得所有对最短路径并以某种方式结合路径.有没有更好的方法来解决这个问题？

relaxation of an edge在图论的背景下意味着什么？我在研究Dijkstra的单源最短路径算法时遇到了这个问题.