✨longest path

find longest path in an undirected graph

replit ⟩ Multiple-Factor Sequence (longest path problem)

// 「因數倍數」關係
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 problem Nextparadigm

Last updated 1 year ago

Was this helpful?

// 「因數倍數」關係 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});