โจ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