标签: graph-traversal

想象一下有一个图表。节点的形式为 GraphNode。图可以有重复的节点。我们必须在图上做一个 BFS。一开始我们并不知道整个图，即没有办法索引图的节点。例如，只有根节点作为 BFS 函数的输入。

这是 GraphNode 的定义，不能更改。

public class GraphNode {
  int val;
  GraphNode left;
  GraphNode right;
  GraphNode(int x) { val = x; }
}

在 BFS 算法中处理访问节点的最佳方法是什么？请记住，图中有重复的节点，即具有相同键的多个节点。我们不想删除或忽略重复项。

我知道标题有点乱,但我不知道如何更好地解释它.

我正在做的事情:

使用文本文件中的图形,找到并打印从顶点A到顶点B的最短路径(最小顶点数量).

注意:使用广度优先搜索,而不是Dijkstra.

我得到了什么:

一种在图上应用BFS的工作算法,但没有实际打印出最短路径的好方法.

我很难区分最短路径中的顶点与简单地通过算法运行的顶点,但不是最短路径中的顶点.

例如:找到0到4之间的最短路径.0连接到1,2和3. 1连接到4.我的路径原来是[0,1,2,3,4]而不是[0,1, 4].

我一直没能找到问同样的问题,或者BFS的任何一个角落,通过包括该任何线程,所以我不知道如果我做了这一点,是这样难度比它是什么？

编辑:可能感兴趣的人的代码(如果我避开圈子,根本不确定？)

编辑2:改变了我将路径存储到堆栈的方式.

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];

    q.add(v);
    Stack<Integer> path = new Stack<Integer>();
    while(q.peek() != null) {
        runBFS(q.poll(),w,visited,q,path);
    }
    return path.toString();
} 

private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
    if(visited[v]) {
    }
    else if(v == w) {
        path.add(v);
        q.clear();
    }
    else {
        path.add(v);
        visited[v] = true; …

在haskell中表示一棵树很容易:

data Tree a = Node Tree a Tree | Leaf a

但这是因为它不需要命令式样式"指针"的概念,因为每个Node/Leaf都有一个,而且只有一个父节点.我想我可以将它表示为Maybe Ints 列表的列表... Nothing为那些没有路径的节点创建一个表,对于那些Just n那些...但这看起来真的很丑陋而且不实用.

PyYAML可以处理常规python对象中的循环图.例如:

片段#1.

class Node: pass
a = Node()
b = Node()
a.child = b
b.child = a
# We now have the cycle a->b->a
serialized_object  = yaml.dump(a)
object = yaml.load(serialized_object)

此代码成功,因此显然有一些机制可以在加载序列化对象时阻止无限递归.当我编写自己的YAML构造函数时,如何利用它？

例如,假设Node是具有瞬态域的一类foo和bar,以及intransient场child.只child应将其纳入yaml文档.我希望这样做:

小片#2.

def representer(dumper, node):
  return dumper.represent_mapping("!node", {"child": node.child})

def constructor(loader, data):
  result = Node()
  mapping = loader.construct_mapping(data)
  result.child = mapping["child"]
  return result

yaml.add_representer(Node, representer)
yaml.add_constructor("!node", constructor)

# Retry object cycle a->b->a from earlier code snippet
serialized_object  = …

我有一个用例,我必须从一个特定的顶点开始遍历一串顶点.它是一个线性链(像火车),只有一个顶点连接到前一个.虽然遍历我必须根据一些标准发射某些顶点,直到我到达链的末端.

第二个用例是上述用例的扩展,但不是从单个顶点开始的单个链,而是有多个这样的链,同样从单个顶点开始.我必须遍历每个链并检查顶点中的特定属性值.当找到该属性匹配时,我必须发出该顶点,并以第二个链开始,依此类推.

我必须使用Gremlin java API实现这一点.这看起来很简单,但我是gremlin的新手,并且在gremlin java API上没有太多关于互联网的帮助.

在BGL中,我无法弄清楚如何在bfs/dfs搜索期间访问图中的顶点的固有颜色(白色表示未触摸,灰色表示已访问,黑色表示完成).

有人可以说明如何从dfs/bfs访问者中访问顶点颜色吗？比如写自定义examine_edge？

我试图了解Neo4J java遍历API,但经过彻底的阅读后,我仍然坚持某些观点.

我似乎知道的:

PathExpander和之间的区别BranchOrderingPolicy.根据我的理解,前者告诉我们哪些关系有资格从特定位置进行探索,后者指定应该评估它们的顺序.

我想知道以下事项:

1. 这种理解是否正确或在何种程度上是正确的,或者是否可以改变以给出正确的理解.

2. 如果正确,有何PathExpander不同Evaluator.

3. 怎么做PathExpander和BranchOrderingPolicy工作.我打算问的是,PathExpander每次在遍历中添加关系时都会查询,并且对返回的可迭代关系有什么作用.与分支排序类似.

4. 在遍历期间如何以及何时组件Expander,BranchOrdering,Evaluator,Uniqueness进入画面.基本上我想知道模板算法,其中一个人会说第一个扩展器被要求扩展关系的集合,然后咨询订购策略以选择其中一个符合条件....

5. 如果正确,那么指定的排序策略是否BranchOrderingPolicy仅适用于符合条件的关系(在扩展器完成之后).也许它一定是.

请包含可能有助于理解API的任何其他内容.

这是关于良好做法的问题

考虑典型的情况,例如在3D引擎,物理引擎,有限元方法或经典分子动力学求解器中:您有各种类型的对象(例如顶点,边,面,有界实体体积)彼此交叉链接(例如顶点知道哪个边连接到它,反之亦然).对于这种引擎的使用性能和便利性,能够快速浏览这种连接的网络是至关重要的.

问题是:通过数组中的索引或指针指向链接对象是否更好？......特别是在表现方面

typedef index_t uint16_t;

class Vertex{
    Vec3 pos;
    #ifdef BY_POINTER
    Edge*   edges[nMaxEdgesPerVertex];
    Face*   faces[nMaxFacesPerVertex];
    #else
    index_t edges[nMaxEdgesPerVertex];
    index_t faces[nMaxFacesPerVertex];
    #endif
}

class Edge{
    Vec3   direction;
    double length;
    #ifdef BY_POINTER
    Vertex* verts[2];
    Faces*  faces[nMaxFacesPerEdge];  
    #else
    index_t verts[2];
    index_t faces[nMaxFacesPerEdge];
    #endif
}

class Face{
    Vec3   normal;
    double isoVal; // Plane equation: normal.dot(test_point)==isoVal
    #ifdef BY_POINTER
    Vertex* verts[nMaxVertsPerFace];
    Edge*   edges[nMaxEdgesPerFace];
    #else
    index_t verts[nMaxVertsPerFace];
    index_t edges[nMaxEdgesPerFace];
    #endif
}

#ifndef BY_POINTER
// we can use …

我有一个 DAG（有向无环图），它由边列表表示，例如

edges = [('a','b'),('a','c'),('b','d')]

将给出图表

a - > b -> d
|
v
c

我正在执行许多操作，我必须检查两个节点是否位于同一路径上（b并且d位于同一路径上，b而 和c不是来自上面的示例），这反过来又减慢了我的程序。我希望我能以某种方式遍历该图一次并保存所有路径，这样我就可以在恒定的时间内检查它。

这种加速可能吗？我将如何在 python 中实现它？

编辑：请注意，我需要检查两个方向，因此如果我有一对节点，(a,b)我需要检查atob和bto a。

首先是的,这是我的Perl课程的家庭作业项目.我不是在寻找答案(尽管那会很好).据我了解,我需要使用BFS和正则表达式来组织我的数据以供使用.我需要一些方向.我如何使用BFS？我是否使用大量堆栈并浏览堆栈中的每个项目？我应该使用巨型哈希表吗？有没有人解决过这个问题？你是怎么做的？我只是需要一些方向.这类似于BST吗？这可能不使用图形模块吗？这是否可以使用哈希值？