js 数组筛选问题？

Question

linkData: [
    { source: '部门名称1_1', target: '部门名称2_3' },
    { source: '部门名称1_1', target: '部门名称2_4' },
    { source: '部门名称1_1', target: '部门名称2_7' },
    { source: '部门名称1_4', target: '部门名称2_1' },
    { source: '部门名称1_4', target: '部门名称2_6' },
    { source: '部门名称1_7', target: '部门名称2_9' },
    { source: '部门名称1_7', target: '部门名称2_1' },
    { source: '部门名称1_9', target: '部门名称2_2' },
    { source: '部门名称1_10', target: '部门名称2_8' },
    { source: '部门名称1_11', target: '部门名称2_11' },
    { source: '部门名称1_12', target: '部门名称2_2' },
    { source: '部门名称2_3', target: '部门名称3_6' },
    { source: '部门名称2_2', target: '部门名称3_4' },
    { source: '部门名称2_8', target: '部门名称3_5' },
    { source: '部门名称2_8', target: '部门名称3_9' },
    { source: '部门名称2_11', target: '部门名称3_9' },
],

如图这样的一个数组，假定选择target为部门名称3_9的这条属性，他的source为部门名称2_11,而以部门名称2_11为target的是部门1_11,如何筛选出部门名称2_11,部门名称1_11这样一个数组合集呢？

Answer 1

这个数据不是树结构啊，部门名称3_9 有 2 个 source，部门名称2_8 和 部门名称2_11

graph BT
    2_3((2_3)) --> 1_1((1_1))
    2_4((2_4)) --> 1_1((1_1))
    2_7((2_7)) --> 1_1((1_1))
    2_1((2_1)) --> 1_4((1_4))
    2_6((2_6)) --> 1_4((1_4))
    2_9((2_9)) --> 1_7((1_7))
    2_1((2_1)) --> 1_7((1_7))
    2_2((2_2)) --> 1_9((1_9))
    2_8((2_8)) --> 1_10((1_10))
    2_11((2_11)) --> 1_11((1_11))
    2_2((2_2)) --> 1_12((1_12))
    3_6((3_6)) --> 2_3((2_3))
    3_4((3_4)) --> 2_2((2_2))
    3_5((3_5)) --> 2_8((2_8))
    3_9((3_9)) --> 2_8((2_8))
    3_9((3_9)) --> 2_11((2_11))
    classDef cur fill:#9370DB,color:#fff
    class 3_9,2_8,2_11,1_10,1_11 cur

所以这里再给个广搜遍历所有能到达的 source

const sourcesMap = linkData.reduce((map, { source, target }) => ((map[target] ??= []).push(source), map), {})

const bfs = target => {
  if (!sourcesMap[target]) return [target]
  const res = new Set([target])
  let cur = [...sourcesMap[target]]
  do {
    const pre = cur
    cur = []
    for (const source of pre) {
      if (!res.has(source)) {
        res.add(source)
        if (sourcesMap[source])
          cur.push(...sourcesMap[source])
      }
    }
  } while (cur.length)
  return [...res]
}

bfs('部门名称3_9')
// ['部门名称3_9', '部门名称2_8', '部门名称2_11', '部门名称1_10', '部门名称1_11']

Answer 2

递归，伪代码。找到了就用source继续找，找不到就算结束。

deepFind(value = '3_9'){
    const result = list.find(value);
    if(result){
        return [result, ...deepFind(result.source)];
    }else {
        return [];
    }
}

Answer 3

补充代码

// 循环解法
function getPath(list, targetName) {
    const result = [];
    let target = `部门名称${targetName}`;
    while (target) {
        const it = list.find(it => it.target === target);
        if (it) { result.unshift(it); }
        target = it?.source;
    }
    return result;
}

// 递归解法
function getPathRecurse(list, targetName) {
    var it = list.find(it => it.target === targetName);
    return it ? [...getPathRecurse(list, it.source), it] : [];
}

console.log(getPath(linkData, "3_9"));
console.log(getPathRecurse(linkData, "部门名称3_9"));

顺便提一下，存在两个 target 是 3_9 的，应该是有误吧。如果存在多条路径，这个问题处理起来可就麻烦多了。

---

下面的原回答，代码就是个意思

方法一，递归

function find(list, target, result = []) {
    var it = list.find(it => it.target === `部门名称${target}`);
    return it ? result : find(list, it.target, [it, ...result]);
}

const result = find(linkData, "3_9");

方法二，循环

const result = [];
let target = "3_9";
while (target) {
    const it = list.find(it => it.target === `部门名称${target}`);
    if (it) { result.unshift(it); }
    target = it;
}

都是伪代码，没验证，懒得自己去做数据。下次问问题记得到数据以代码（文本）的形式贴出来。

Answer 4

function deepFind(linkData, value = '部门名称3_9', arr = []){
      const result = linkData.filter(item => item.target === value);
      
      if (result.length) {
        return result.reduce((acc, curr) => {
          arr.push(curr.target)
          deepFind(linkData, curr.source, acc)
          return arr
        }, arr)
      } else {
        arr.push(value)
        return arr
      }
    }

    let  res = deepFind(linkData)
    console.log([...new Set(res)]);