如何在图中查找元素？

Question

我有以下实体：

表格
块
行
单元格
字段

根元素是 Form。

里面 From 被放置 Block.

Block包含一些Rows，每个Row可以包含一些Cell，里面的内容不同：Field或Block，其中Block又是嵌套结构Block -> Rows -> Cells -> Field/Block.

是从根Form到顶点Field或Block.

的有向有限图

只有 Block 和 Field 实体具有 getId() 方法 returns 顶点 ID。基于此，我构建了从根到具体顶点的路径 (Blcok, Field).

我试图检查具体的顶点实体 (Block) 是否按路径显示在图中，所以我的解决方案是：

设置当前顶点（Block）从哪里开始，设置顶点的收入路径
循环获取当前顶点（块）的所有行
然后在第一个循环中使用循环
然后从每个单元格（字段、块）获取内容
检查它是否是 Block 然后获取它的 id 并与传入路径（id）
如果不相等则将找到的块设置为当前块（for 循环）
继续，直到找不到路径

代码是：

function getBlockFieldByPath(block: Block, path: string) {
   let currentBlock = block;
   let irows = 0;
   let jcells = 0;

   while(irows < currentblock.getRows().length) {
       let cells = rows[irows].getCells();
       while(jcells < cells.length) {
           let content = cells[jcells].getContent(); // it is should be Block or Field,

           if (content.getId() == path) {
               return content;
           }

           if (content == Block) {
              currentblock = content; // Because content is Block
           }

          jcells++;
       }
     irows++;
   }   

}

我的错误在哪里？

Answer 1

通过一些抽象，您得到了一个节点为块的图形。

其中一些是微不足道的叶子。

您只想 dfs 图形，直到找到与您的路径字符串匹配的块

function dfs(block, path) {
  if (block.getId() === path) return block
  let found = null
  block.getRows().find(r => r.getCells().find(bContent => {
    let b = bContent.getContent()
    found = dfs(b, path)
    return found
  }))
  return found
}

堆栈的变化

function dfs(block, path) {
  const stack = [block]
  while (stack.length) {
    const b = stack.pop()
    if (b.getId() === path) return block
    b.getRows().forEach(r => r.getCells().forEach(bContent => {
      let b = bContent.getContent()
      stack.push(b)
    })
  }
  return null
}

如何在图中查找元素？

How to find element in graph?

javascript

algorithm

graph-algorithm