✨longest path

find longest path in an undirected graph

// 「因數倍數」關係
function isConnected(a, b) {
    return a != b && (a % b == 0 || b % a == 0);
}

// 生成 1 ... N 的「因數倍數」連結圖
function generateGraph(N) {
    // 剛開始是一個空的 dictionary (key: 1 ... N, value: 該數的「因數或倍數」)
    let graph = {};
    // 找出 1 ... N 每個數的「因數或倍數」
    for (let i = 1; i <= N; i++) {
        let neighbors = [];
        for (let j = 1; j <= N; j++) {
            if (isConnected(i, j)) neighbors.push(j + '');  // int -> string
        }
        graph[i] = neighbors;
    }
    // 回傳 dictionary
    return graph;
}

// 找出 1 ... N 的最長「因數倍數數列」
function longestPath(N, {debug = false}={}) {

    // 紀錄執行開始時間
    const startTime = Date.now();

    // 生成「因數倍數」連結圖
    const neighbors = generateGraph(N);

    // 初始設定
    let maxPathLength = 0;    // 最長路徑長度
    let result = [];          // 最長路徑

    // 深度優先搜尋(depth-first-search)
    function dfs(node, currentLength, visited) {

        // 標記「當前節點」為「已訪問」
        visited.add(node);
        // 更新當前路徑長度
        currentLength++;

        // 更新最長路徑長度
        if (currentLength > maxPathLength) {
            maxPathLength = currentLength;
            result = Array.from(visited).map(x => +x);
            if (debug) console.log('當前長度：', result.length, '，當前路徑：', result + '');
        }

        // 對當前節點的每個鄰居進行深度優先搜尋
        for (let neighbor of neighbors[node]) {
            if (!visited.has(neighbor)) dfs(neighbor, currentLength, visited);
        }
        
        // 回溯前将當前節點標記為「未訪問」
        visited.delete(node);
    }

    // 對每個節點進行深度優先搜尋
    for (let node in neighbors) {
        dfs(node, 0, new Set());
    }

    console.log('N =', N);
    console.log('最長長度:', maxPathLength);
    console.log('最長路徑:', result + '');
    console.log('執行時間：', Date.now() - startTime, 'ms');
}

// run
longestPath(15, {debug: true});
Previousknapsack problemNextparadigm

Last updated

Was this helpful?