如何编写JS递归函数来跟踪子图，使用邻接列表，获取初始节点列表

问题描述 投票：0回答：1

目标：

目的是开发一个函数，在给定现有的邻接列表实现的情况下，快速跟踪节点列表的子图，并除了原始列表之外还返回连接的 ID 列表

问题

我发现很难理解要返回什么，以及如何/在哪里将找到的 ID 添加到原始列表中。真正的问题是决定：

  1. 函数返回什么，
  2. 这两种情况如何处理，是否进一步递归

我有一个框架代码，但我开始时不知道如何完成它。你能帮忙吗？

邻接列表类


//------------------------------------------
// Adjaceny List Class
//-------------------------------------------
class Graph {
  
  constructor(){
    this.adjacencyList = new Map();
  }

  addNode(node){
    this.adjacencyList.set(node, new Map());
  }

  addEdge(node1, node2){
    this.adjacencyList.get(node1).set(node2);
  }

  getNeighboors(node){
    return this.adjacencyList.get(node);
  }

  hasEdge(node1, node2){
    return this.adjacencyList.get(node1).has(node2);
  }

}

我的半成品骨架

谁能告诉我该怎么做，以便它只返回子图中的节点列表，包括原始 ID？谢谢

function traceSubGraph(ID_list, adjacency) {
    let layer_IDs = []
    for (let ID in ID_list) {
        layer_IDs = adjacency.getNeighboors(ID);        
        if (layer_IDs.length) {
            // add new valid nodes to original list of nodes
            ID_list.concat(layer_IDs);
            // keep recursing, but how to add the new values?
            return traceSubGraph(layer_IDs, adjacency)            
        } 
        else {
          // stop recursing, what to do here?
        }
    }
  // what to return? ID_list, but where to add the new found nodes?
}

我发现通过节点和边缘数组进行查看并不快，然后手动使用 if/else 向下 3 或 4 层也不好。然后我在网上找到了这个邻接列表类。我已经成功地相对轻松地填充了它，但它正在使用它来追踪让我感到困惑的子图。

特别是当我们决定是否递归时，我们正在迭代一个列表，这对于我这个菜鸟来说似乎很困难。

我已经尝试查看它几个小时，并在网上搜索有关递归的教程，但我仍然不确定最佳方法。

javascript recursion graph-theory adjacency-list subgraph
1个回答
0
投票

修复图表

嵌套的 

Map
应该是 
Set
，因为没有与键关联的值。 
addEdge
在某些条件下会破裂。在某些情况下，
getNeighboors
会返回
undefined
。出于此答案的目的不需要
addNode
-

class Graph {
  constructor() {
    this.t = new Map()
  }
  addEdge(node1, node2) {
    const s = this.t.get(node1)
    if (s == null)
      this.t.set(node1, new Set([node2])) // Set, not Map
    else
      s.add(node2)                        // .add, not .set
  }
  getAdjacencies(node) {
    return this.t.get(node) ?? new Set()
  }
}

让我们构建一个具体的图表以用于我们答案的其余部分。下次您将在问题中提供这一点 -

const g = new Graph()
g.addEdge("A", "B")
g.addEdge("B", "C")
g.addEdge("B", "D")
g.addEdge("D", "E")
g.addEdge("P", "Q")
g.addEdge("Q", "P")
g.addEdge("W", "X")
g.addEdge("W", "Y")
g.addEdge("X", "Z")
g.addEdge("Y", "Z")
g.addEdge("Z", "W")

单一入口点

首先，我们将编写 

dir
来遍历图形的单个 
node
入口点。我称其为 
dir
，因为它生成节点的路径，就像列出文件系统中目录的内容 -

class Graph {
  //...
  *dir(node, path = Array(), visited = new Set()) {
    yield [...path, node]
    path.push(node)
    visited.add(node)
    for (const adj of this.getAdjacencies(node)) {
      if (!visited.has(adj)) {
        yield* this.dir(adj, path, visited)
      }
    }
    path.pop()
  }
}

每个 

path
都是一系列节点，我们可以通过使用分隔符连接片段来将它们可视化为熟悉的字符串路径，
/
-

for (const path of g.dir("A")) {
  console.log(path.join("/"))
}

A
A/B
A/B/C
A/B/D
A/B/D/E

但更重要的是，我们可以操纵这些路径来提取我们关心的特定遍历的数据。在此示例中，我们通过选择每个路径的基本名称 -

 来找到
A

子图中的所有唯一节点 
for (const path of g.dir("A")) {
  console.log(path.at(-1)) // basename
}

A
B
C
D
E

多个入口点

目前 

dir
仅接受单个 
node
入口点。为了完成剩下的问题，我们可以编写 
dirs
来接受代表图形多个入口点的 
nodes
数组 -

class Graph {
  //...
  *dirs(nodes) {
    for (const node of nodes) {
      yield* this.dir(node)
    }
  }
}

现在我们用一组入口点调用 

dirs
-

for (const path of g.dirs(["B", "W"])) {
  console.log(path.join("/"))
}

B
B/C
B/D
B/D/E
W
W/X
W/X/Z
W/Y

或者再次使用路径操作来收集从 

B
和 
W
-

可到达的所有节点 
console.log(Array.from(g.dirs(["B", "W"]), path => path.at(-1)))

[ "B", "C", "D", "E", "W", "X", "Z", "Y" ]

备注

希望您能看到以这种方式编写

dir
意味着我们将艰难的选择转移给了程序的用户。 
dir
没有尝试预测遍历消费者的需求，而是生成到每个可到达节点的路径。现在，每个需要遍历该图的程序都可以根据该程序的独特上下文做出不同的选择。

也许您在 

dirs
示例中注意到，即使存在多个路径，我们也只生成了 Z 的 
one
路径。这是我将在下一个回答这个问题时解决的问题。

演示

class Graph {
  constructor() {
    this.t = new Map()
  }
  addEdge(node1, node2) {
    const s = this.t.get(node1)
    if (s == null) this.t.set(node1, new Set([node2]))
    else s.add(node2)
  }
  getAdjacencies(node) {
    return this.t.get(node) ?? new Set()
  }
  *dir(node, path = Array(), visited = new Set()) {
    yield [...path, node]
    path.push(node)
    visited.add(node)
    for (const adj of this.getAdjacencies(node)) {
      if (!visited.has(adj)) {
        yield* this.dir(adj, path, visited)
      }
    }
    path.pop()
  }
  *dirs(nodes) {
    for (const node of nodes) {
      yield* this.dir(node)
    }
  }
}

const g = new Graph()
g.addEdge("A", "B"); g.addEdge("B", "C"); g.addEdge("B", "D"); g.addEdge("D", "E"); g.addEdge("P", "Q"); g.addEdge("Q", "P"); g.addEdge("W", "X"); g.addEdge("W", "Y"); g.addEdge("X", "Z"); g.addEdge("Y", "Z"); g.addEdge("Z", "W")

for (const path of g.dir("A")) {
  console.log(path.join("/"))
}

for (const path of g.dir("A")) {
  console.log(path.at(-1))
}

for (const path of g.dirs(["B", "W"])) {
  console.log(path.join("/"))
}

console.log(Array.from(g.dirs(["B", "W"]), path => path.at(-1)))
.as-console-wrapper { min-height: 100%; top: 0 }

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.