โœจ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});

Last updated