JavaScript

Question

我必须展示一组相互依赖的图像。例如

 Image A depends on no one
 Image B depends on A
 Image C depends on A and B
 Image D depends on F
 Image E depends on D and C
 Image F depends on no one

我有一个像这样的 javascript 对象：

const imageDependencies = {
    A: [],
    B: ['A'],
    C: ['A', 'B'],
    D: ['F'],
    E: ['D', 'C'],
    F: []
}

我需要按依赖项对我所有的图像名称进行排序。此示例的结果可能是以下任何一个：

//   so first yo get the value of A. Once you have it you can get the value of B. Once you have the value of A and B you can get C, and so on

result_1 = [A, B, C, F, D, E] 

// this could be another correct result
result_2 = [A, F, D, B, C, E]

我试过像这样使用 Array.sort() 函数：

let names = Object.keys(imageDependencies);
names.sort((a,b) => {
    if(imageDependencies [a].includes(b)) return 1
    else return -1
})

但无法正常工作。

如何做到这一点？

Answer 1

您可以为添加的键取 Set 并检查实际依赖项是否已将所有元素添加到集合中。然后添加这个键，否则继续。继续直到数组中没有更多的项目。

var dependencies = { A: [], B: ['A'], C: ['A', 'B'], D: ['F'], E: ['D', 'C'], F: [], G: ['H'], H: ['G'] },
    keys = Object.keys(dependencies),
    used = new Set,
    result = [],
    i, item, length;
    
do {
    length = keys.length;
    i = 0;
    while (i < keys.length) {
        if (dependencies[keys[i]].every(Set.prototype.has, used)) {
            item = keys.splice(i, 1)[0];
            result.push(item);
            used.add(item);
            continue;
        }
        i++;
    }
} while (keys.length && keys.length !== length)

console.log('circle', ...keys);
result.push(...keys);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

为了优先获取没有依赖项的项目，您可以过滤键并直接取值。

var dependencies = { A: [], B: ['A'], C: ['A', 'B'], D: ['F'], E: ['D', 'C'], F: [], G: ['H'], H: ['G'] },
    keys = Object.keys(dependencies),
    used = new Set,
    result = [],
    items, length;
    
do {
    length = keys.length;
    items = [];
    keys = keys.filter(k => {
        if (!dependencies[k].every(Set.prototype.has, used)) return true;
        items.push(k);
    });
    result.push(...items);
    items.forEach(Set.prototype.add, used);
} while (keys.length && keys.length !== length)

console.log('circle', ...keys);
result.push(...keys);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

这里你要的是拓扑排序

(https://en.wikipedia.org/wiki/Topological_sorting).

我用了这个例子

https://gist.github.com/shinout/1232505#file-tsort-js-L9

作者Shin Suzuki

https://gist.github.com/shinout

const imageDependencies = {
    A: [],
    B: ['A'],
    C: ['A', 'B'],
    D: ['F'],
    E: ['D', 'C'],
    F: []
}

function tsort(edges) {
    let nodes = {}, sorted = [], visited = {};

    let Node = function (id) {
        this.id = id;
        this.afters = [];
    }

    edges.forEach( (v)=> {
        let from = v[0], to = v[1];
        if (!nodes[from]) nodes[from] = new Node(from);
        if (!nodes[to]) nodes[to] = new Node(to);
        nodes[from].afters.push(to);
    });

    Object.keys(nodes).forEach(function visit(idstr, ancestors) {
        let node = nodes[idstr],id = node.id;

        if (visited[idstr]) return;
        if (!Array.isArray(ancestors)) ancestors = [];

        ancestors.push(id);
        visited[idstr] = true;
        node.afters.forEach(function (afterID) {
            if (ancestors.indexOf(afterID) >= 0)  
                throw new Error('closed chain : ' + afterID + ' is in ' + id);
            visit(afterID.toString(), ancestors.map(function (v) { return v })); 
        });
        sorted.unshift(id);
    });

    return sorted;
}


const createEdges = (dep) => {
    let result = []
    Object.keys(dep).forEach(key => {
        dep[key].forEach(n => {
            result.push([n, key])
        })
    })
    return result
}

const list = createEdges(imageDependencies)
console.log(tsort(list))

Answer 3

这是我的做法：

const imageDependencies = {
  A: [],
  B: ["A"],
  C: ["A", "B"],
  D: ["F"],
  E: ["D", "C"],
  F: []
};
let keys = Object.keys(imageDependencies), // ["A","B","C","D","E","F"]
  output = [];

while (keys.length) {
  for (let i in keys) {
    let key = keys[i], // "A"
        dependencies = imageDependencies[key]; // []

    if (dependencies.every(dependency => output.includes(dependency))) { // If all dependencies are already in the output array
      output.push(key); // Pushing "A" to the output
      keys.splice(i, 1); // Removing "A" from the keys
    }
  }
}

console.log("output = ", output);

Answer 4

这是另一个使用 Array.prototype.reduce()

的破解方法

const imageDependencies = {
    A: [],
    B: ['A'],
    C: ['A', 'B'],
    D: ['F'],
    E: ['D', 'C'],
    F: []
}
const imageDependenciesBad = {
    A: ["X"],
    B: ['A'],
    C: ['A', 'B'],
    D: ['F'],
    E: ['D', 'C'],
    F: []
}

const sort = (names, obj, start, depth = 0) => {
  const processed = names.reduce((a,b,i) => {
    if (obj[b].every(Array.prototype.includes, a)) a.push(b)
    return  a
  }, start)
  const nextNames = names.filter(n => !processed.includes(n)),
    goAgain = nextNames.length && depth <= names.length
  return goAgain ? sort(nextNames, obj, processed, depth + 1) : processed
}

console.log(sort(Object.keys(imageDependencies), imageDependencies, []).join(","))
console.log(sort(Object.keys(imageDependenciesBad), imageDependenciesBad, []).join(","))

Answer 5

toposort 是一个很好的库 https://github.com/marcelklehr/toposort

const toposort = require("toposort")
const imageDependencies = {
    A: [],
    B: ['A'],
    C: ['A', 'B'],
    D: ['F'],
    E: ['D', 'C'],
    F: []
}

// split dependencies into pairs for toposort
let deps = []
Object.keys(imageDependencies).forEach(k => {
    imageDependencies[k].forEach(d => {
        deps.push([d,k])
    })
})

toposort.array(Object.keys(imageDependencies), deps)
// -> ["A", "B", "C", "F", "D", "E"]

JavaScript - 根据依赖树排序

JavaScript - Sort depending on dependency tree

arrays

sorting

topological-sort

typescript