标签: graph-theory

检测有向图中所有周期的最有效算法是什么？

我有一个有向图表示需要执行的作业计划,作业是节点,依赖是边缘.我需要检测此图中循环的错误情况,从而导致循环依赖.

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

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

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

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

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

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

我想知道什么时候应该使用Prim的算法,什么时候Kruskal才能找到最小的生成树？它们都具有简单的逻辑,同样最坏的情况,唯一的区别是实现可能涉及一些不同的数据结构.那么决定因素是什么？

BFS的基本算法:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

所以我认为时间的复杂性将是:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

v顶点1到哪里n

首先,我说的是正确的吗？其次,这是怎样的O(N + E),直觉为什么会非常好.谢谢

我正在尝试确定完成下述任务的最佳时间效率算法.

我有一套记录.对于这组记录,我有连接数据,表明该组中的记录对如何相互连接.这基本上代表一个无向图,其中记录是顶点,连接数据是边.

集合中的所有记录都有连接信息(即不存在孤立记录;集合中的每个记录都连接到集合中的一个或多个其他记录).

我想从集合中选择任意两条记录,并能够显示所选记录之间的所有简单路径."简单路径"是指路径中没有重复记录的路径(即仅限于有限路径).

注意:两个选择的记录将始终不同(即开始和结束顶点永远不会相同;没有循环).

例如:

    If I have the following records:
        A, B, C, D, E

    and the following represents the connections: 
        (A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
        (C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)

        [where (A,B) means record A connects to record B]

如果我选择B作为我的起始记录而E作为我的结束记录,我希望找到通过记录连接将记录B连接到记录E的所有简单路径.

   All paths connecting B to E:
      B->E
      B->F->E
      B->F->C->E
      B->A->C->E
      B->A->C->F->E

这是一个例子,实际上我可能有包含数十万条记录的集合.

背景

这张照片说明了问题:

我可以控制红圈.目标是蓝色三角形.黑色箭头表示目标将移动的方向.

我想以最少的步数收集所有目标.

每回合我必须向左/向右/向上或向下移动1步.

每转一圈,目标也会根据棋盘上显示的方向移动一步.

演示

我在Google appengine上发布了一个可玩的问题演示.

如果有人能够击败目标分数,我会非常感兴趣,因为这会显示我当前的算法不是最理想的.(如果你管理这个,应该打印祝贺信息!)

问题

我目前的算法与目标数量的关系非常严重.时间以指数方式上升,对于16条鱼来说已经是几秒钟了.

我想计算板尺寸为32*32和100个移动目标的答案.

题

用于计算收集所有目标的最小步骤数的有效算法(理想情况下是Javascript)是什么？

我试过的

我目前的方法是基于记忆,但它非常慢,我不知道它是否总能产生最佳解决方案.

我解决了"收集一组给定目标并最终达到特定目标的最小步数是多少？"的子问题.

通过检查先前要访问的目标的每个选择来递归地解决子问题.我假设尽可能快地收集前一个目标子集然后尽快从你结束的位置移动到当前目标(尽管我不知道这是否是一个有效的假设)总是最佳的.

这导致计算n*2 ^ n个状态,其非常快速地增长.

当前代码如下所示:

var DX=[1,0,-1,0];
var DY=[0,1,0,-1]; 

// Return the location of the given fish at time t
function getPt(fish,t) {
  var i;
  var x=pts[fish][0];
  var y=pts[fish][1];
  for(i=0;i<t;i++) {
    var b=board[x][y];
    x+=DX[b];
    y+=DY[b];
  }
  return [x,y];
}

// Return the number of steps to track down the given fish
// Work by iterating and selecting first time when …

我有一个带有大约100个节点和大约200个边的无向图.一个节点标记为"开始",一个节点标记为"结束",并且大约有十几个标记为"必须通过".

我需要找到通过此图表的最短路径,该路径从'start'开始,在'end'结束,并通过所有'mustpass'节点(以任何顺序).

(http://3e.org/local/maize-graph.png/http://3e.org/local/maize-graph.dot.txt是有问题的图表 - 它代表宾夕法尼亚州兰开斯特的一个玉米迷宫)

首先,让我说我正在使用LyX,尽管我使用ERT没有问题.

其次,在Latex中绘制这样一个简单图形的最简单方法是什么？

我已经看过一些带有图形的文档,我看过一些例子,但是我无法弄清楚如何绘制一个简单的图形 - 我需要哪些软件包等等？

我需要建议来渲染具有178,000个节点和500,000个边缘的无向图.我尝试过Neato,Tulip和Cytoscape.Neato甚至没有近距离接触,Tulip和Cytoscape声称他们可以处理它,但似乎无法做到.(郁金香什么也没做,Cytoscape声称工作,然后停止.)

我只是喜欢一个矢量格式文件(ps或pdf),它具有远程合理的节点布局.