小编Dom*_*tin的帖子

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

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

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

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

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

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

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

我需要能够在python中操作一个大的(10 ^ 7个节点)图形.对应于每个节点/边缘的数据是最小的,例如,少量的字符串.在内存和速度方面,最有效的方法是什么？

dicts的词典更灵活,更易于实现,但我直观地期望列表列表更快.list选项还要求我将数据与结构分开,而dicts允许这样的东西:

graph[I][J]["Property"]="value"

你会建议什么？

是的,我应该对效率的意思更清楚一点.在这个特殊情况下,我的意思是随机访问检索.

将数据加载到内存中不是一个大问题.这是一劳永逸的.耗时的部分是访问节点,因此我可以提取信息并测量我感兴趣的指标.

我没有考虑过让每个节点成为一个类(所有节点的属性都相同),但似乎会增加一层额外的开销？我希望有人可以直接体验他们可以分享的类似案例.毕竟,图形是CS中最常见的抽象之一.

是否有GraphViz的开源Java替代品？我知道Grappa的存在,它基本上将Graph接口包装为GraphViz作为JavaAPI.但是,GraphViz二进制文件仍然可以完成布局.

我正在寻找一个纯java,开源库,提供与GraphViz相同的功能和布局算法.

假设我以下面的方式连接节点,我如何得出给定点之间存在的路径数量和路径详细信息？

1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9

找到1到7的路径:

答案:找到2条路径,它们是

1,2,3,6,7
1,2,5,6,7

在这里找到的实现很好,我将使用相同的

这是python中上面链接的片段

# a sample graph
graph = {'A': ['B', 'C','E'],
             'B': ['A','C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F','D'],
             'F': ['C']}

class MyQUEUE: # just an implementation of a queue

    def __init__(self):
        self.holder = []

    def enqueue(self,val):
        self.holder.append(val)

    def dequeue(self):
        val = None
        try:
            val = self.holder[0]
            if len(self.holder) == 1:
                self.holder = [] …

我想知道是否有人可以推荐一个好的C++树实现,希望有一个stl兼容,如果可能的话.

为了记录,我之前已经多次编写树算法,我知道它可以很有趣,但是如果可能的话,我想要务实和懒惰.因此,实际的工作解决方案链接就是目标.

注意:我正在寻找一个通用树,而不是平衡树或地图/集,在这种情况下,结构本身和树的连接性很重要,而不仅仅是数据.因此,每个分支都需要能够保存任意数量的数据,并且每个分支应该是可单独迭代的.

通过这里的图表我的意思是类似这些图像的东西:

理想的解决方案是:

• 仅使用托管代码
• 允许输出到位图图像
• 允许输出到WPF元素
• 包括某种交互式表面,用于显示支持节点缩放,平移和重组的图形

我也有兴趣了解可能被用作此类工作起点的项目.如果需要一些开发来实现我想要的东西,那么我已经准备好解决它了.这个目标中最复杂的部分似乎是在合理的时间范围内获得图形布局.

平面文件和关系数据库为我们提供了一种序列化结构化数据的机制.XML非常适合序列化非结构化树状数据.

但是很多问题最好用图表来表示.例如,热模拟程序将通过电阻边缘与彼此连接的温度节点一起工作.

那么序列化图形结构的最佳方法是什么？我知道XML在某种程度上可以做到这一点 - 就像关系数据库可以序列化复杂的对象网络一样:它通常可以工作,但很容易变得丑陋.

我知道graphviz程序使用的点语言,但我不确定这是最好的方法.这个问题可能是学术界可能正在研究的问题,我很乐意参考讨论这个问题的任何论文.