排序算法/排序算法=排序算法

Question

let a = [ { name: 'a' }, { name: 'b' }, { name: 'a-b' }, { name: 'b-x', }, { name: 'x' }, { name: 'g' }, { name: 'x-g' }] 
let result = [ { name: 'a' }, { name: 'a-b' }, { name: 'b' }, { name: 'b-x', }, { name: 'x' }, { name: 'x-g' }, { name: 'g' }]

求一个 算法， 从 a数组 能得出 result 数组， 每个元素的相邻元素都是根据名称连接关系的顺序

Answer 1

let a = [ { name: 'a' }, { name: 'b' }, { name: 'a-b' }, { name: 'b-x', }, { name: 'x' }, { name: 'g' }, { name: 'x-g' }]

// 创建图
let graph = {};
for (let i = 0; i < a.length; i++) {
    graph[a[i].name] = [];
}
for (let i = 0; i < a.length - 1; i++) {
    let node1 = a[i].name;
    let node2 = a[i + 1].name;
    if (!node2.startsWith(node1)) {
        graph[node1].push(node2);
    }
}

// 拓扑排序
function topologicalSort(graph) {
    let result = [];
    let visited = {};
    for (let node in graph) {
        if (!visited[node]) {
            dfs(graph, node, visited, result);
        }
    }
    return result;
}

function dfs(graph, node, visited, result) {
    visited[node] = true;
    for (let neighbor of graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited, result);
        }
    }
    result.unshift(node);
}

let result = topologicalSort(graph);
console.log(result);