可以由给定的广告对形成更小的广告序列

Question

最近我做了Flipkart Online评估，我被一个问题卡住了很长一段时间。问题是这样的。一家广告公司有一系列广告对，每个广告都应该一个接一个地播放。如果给予“ABC”广告，对公司来说是有利的。我们必须找到所有广告播放一次的顺序。如果可能有多种这样的方式，请按字典顺序给出较小的一种。

例如：

4 
"XYZ", "IOP" 
"QWE", "XYZ" 
"ABC", "TUV" 
"TUV", "QWE"

可能的顺序是从“ABC”->“TUV”->“QWE”->“XYZ”->“IOP”开始

在规定的时间内我无法想出办法。经过我的思考，这与查找从源开始连通图是否可能是相似的，然后查看最小的顺序。

如果其他方法也可行，有人可以帮助我吗？或者这是推论的正确方法吗？

Answer 1

您收到的输入对是有向图的边。字符串是该图的顶点。 “ABC”就是这样的顶点之一。问题是在该图中找到一条从顶点“ABC”开始的路径，该路径恰好访问每个顶点一次。这就是寻找 汉密尔顿路径 选择字典序较小的路径的问题。

这是一个 NP 问题，因此没有已知的具有多项式时间复杂度的解决方案。

这是一个简单的深度优先搜索算法（在 JavaScript 可运行片段中）来查找这样的汉密尔顿路径。它首先为图创建一个邻接列表，对该邻接列表中的每个列表进行排序（以保证我们首先获得字典顺序），然后启动 DFS：

function hamilton(pairs, start) {
    // Build an adjacency list
    const adj = {}; 
    for (const [src, dst] of pairs) {
        adj[src] ??= []; // Create vertex if not yet exists
        adj[dst] ??= []; // Create vertex if not yet exists
        adj[src].push(dst); // dst is a neighbor of src
    }
    // For each vertex, sort the list of neighbors lexically
    for (const neighbors of Object.values(adj)) {
        neighbors.sort();
    }
    const n = Object.keys(adj).length;    

    // Apply a naive DFS algorithm
    const visited = new Set; // Ordered Set (insertion order)
    
    function dfs(node) {
        if (visited.has(node)) {
            return false; // Made a cycle
        }
        visited.add(node);
        if (visited.size === n) { // Solution!
            return true;
        }
        for (const neighbor of adj[node]) {
            if (dfs(neighbor)) {
                return true; // Success
            }
        }
        visited.delete(node); // Backtrack
    }
    
    // Start DFS search
    if (dfs(start)) { // Success
        // Convert ordered Set to array
        return Array.from(visited);
    }
}

// Example run
const pairs = [
    ["XYZ", "IOP"],
    ["QWE", "XYZ"],
    ["ABC", "TUV"], 
    ["TUV", "QWE"],
];

const path = hamilton(pairs, "ABC");
console.log(...path); // ABC TUV QWE XYZ IOP