グラフ・DFSメニュー【閉路の出力・グラフの閉路の総数・通れない頂点が存在する(閉路・閉路の総数)・ハミルトン閉路の出力・オイラー閉路の出力】
【閉路の出力】コード 1/2
reader.on('close', () => {
const dfs = (now, seen) => {
const nexts = list[now];
for (const next of nexts) {
if (next === s - 1 && seen.length > 2) {
seen.push(next);
return seen;
}
if (!seen.includes(next)) {
return dfs(next, [...seen, next]);
}
}
};
const [n, s] = lines.shift().split(' ').map(Number);
const list = new Array(n).fill().map(e => []);
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
const cycle = dfs(s - 1, [s - 1]);
console.log(cycle ? cycle.map(e => e + 1).join(' ') : -1);
});
閉路… s を出発して s に戻る経路。 同じ頂点を 2 回以上通らない。
【閉路の出力】コード 2/2
reader.on('close', () => {
const dfs = (now, seen) => {
const nexts = list[now];
for (const next of nexts) {
if (next === s - 1 && seen.length > 2) {
cycle.push([...seen, next]);
} else if (seen.includes(next) === false && cycle.length === 0) {
dfs(next, [...seen, next]);
}
}
};
const [n, s] = lines.shift().split(' ').map(Number);
const list = new Array(n).fill().map(e => []);
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
const cycle = [];
if (list[s - 1].length === 1) {
console.log(-1);
} else {
dfs(s - 1, [s - 1]);
console.log(cycle[0] ? cycle[0].map(e => e + 1).join(' ') : -1);
}
});
閉路… s を出発して s に戻る経路。 同じ頂点を 2 回以上通らない。
【グラフの閉路の総数】コード
reader.on('close', () => {
const dfs = (now, seen) => {
const nexts = list[now];
for (const next of nexts) {
if (next === s - 1 && seen.length > 2) {
total_num++;
} else if (seen.includes(next) === false) {
dfs(next, [...seen, next]);
}
}
};
const [n, s] = lines.shift().split(' ').map(Number);
const list = new Array(n).fill().map(e => []);
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
let total_num = 0;
if (list[s - 1].length === 1) {
console.log(0);
} else {
dfs(s - 1, [s - 1]);
console.log(total_num / 2);
}
});
閉路… s を出発して s に戻る経路。 同じ頂点を 2 回以上通らない。
【閉路の出力 2】コード
reader.on('close', () => {
const dfs = (now, seen) => {
const nexts = list[now];
for (const next of nexts) {
if (next === e1 - 1 && seen.length > 2) {
cycle.push([...seen, next]);
}
if (!seen.includes(next) && cycle.length === 0) {
dfs(next, [...seen, next]);
}
}
};
const [n, e1, e2] = lines.shift().split(' ').map(Number);
const list = new Array(n).fill().map(e => []);
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
const cycle = [];
if (!list[e1 - 1].includes(e2 - 1) || list[e1 - 1].length < 2) {
console.log(-1);
} else {
dfs(e2 - 1, [e1 - 1, e2 - 1]);
console.log(cycle[0] ? cycle[0].map(e => e + 1).join(' ') : -1);
}
});
dfs() を呼び出す段階で 枝 e を通過済みとしてマークしました。
【グラフの閉路の総数 2】コード
reader.on('close', () => {
const dfs = (now, seen) => {
const nexts = list[now];
for (const next of nexts) {
if (next === e1 - 1 && seen.length > 2) {
total_num++;
} else if (!seen.includes(next)) {
dfs(next, [...seen, next]);
}
}
};
const [n, e1, e2] = lines.shift().split(' ').map(Number);
const list = new Array(n).fill().map(e => []);
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
let total_num = 0;
if (!list[e1 - 1].includes(e2 - 1) || list[e1 - 1].length < 2) {
console.log(0);
} else {
dfs(e2 - 1, [e1 - 1, e2 - 1]);
console.log(total_num);
}
});
dfs() を呼び出す段階で 枝 e を通過済みとしてマークしました。
【通れない頂点が存在する閉路】コード
reader.on('close', () => {
const dfs = (now, seen) => {
const nexts = list[now];
for (const next of nexts) {
if (next === t - 1 && seen.length > 2) {
cycle.push([...seen, next]);
}
if (!seen.includes(next) && !s.includes(next) && cycle.length === 0) {
dfs(next, [...seen, next]);
}
}
};
const [n, t] = lines.shift().split(' ').map(Number);
const k = Number(lines.shift());
const s = lines.shift().split(' ').map(e => e - 1);
const list = new Array(n).fill().map(e => []);
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
const cycle = [];
if (list[t - 1].length < 2) {
console.log(-1);
} else {
dfs(t - 1, [t - 1]);
console.log(cycle[0] ? cycle[0].map(e => e + 1).join(' ') : -1);
}
});
再起関数を呼び出す条件は…
- next が通過済みの頂点に含まれない。
- next が s に含まれない。
- cycle が空要素。
1〜 3 が全て true の場合になります。
【通れない頂点が存在する閉路の総数】コード
reader.on('close', () => {
const dfs = (now, seen) => {
const nexts = list[now];
for (const next of nexts) {
if (next === t - 1 && seen.length > 2 + k) {
total_num++;
}
if (!seen.includes(next)) {
dfs(next, [...seen, next]);
}
}
};
const [n, t] = lines.shift().split(' ').map(Number);
const k = Number(lines.shift());
const s = lines.shift().split(' ').map(e => e - 1);
const list = new Array(n).fill().map(e => []);
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
let total_num = 0;
if (list[t - 1].length < 2) {
console.log(0);
} else {
dfs(t - 1, [t - 1, ...s]);
console.log(total_num / 2);
}
});
dfs() を呼び出す段階で 頂点集合 s の要素 を通過済みとしてマークしました。
【ハミルトン閉路の出力】コード
reader.on('close', () => {
const dfs = (now, seen) => {
const nexts = list[now];
for (const next of nexts) {
if (next === s - 1 && seen.length === n) {
Hamilton_cycle.push([...seen, next]);
} else if (!seen.includes(next) && Hamilton_cycle.length === 0) {
dfs(next, [...seen, next]);
}
}
};
const [n, s] = lines.shift().split(' ').map(Number);
const list = new Array(n).fill().map(e => []);
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
const Hamilton_cycle = [];
if (list[s - 1].length === 1) {
console.log(-1);
} else {
dfs(s - 1, [s - 1]);
console.log(Hamilton_cycle[0]? Hamilton_cycle[0].map(e => e + 1).join(' ') : -1);
}
});
ハミルトン閉路…ある頂点を出発後 残りの全ての頂点を 1 回ずつ通って出発した頂点に戻ってくる経路。
【オイラー閉路の出力】コード
reader.on('close', () => {
const dfs = (now, cycle, edges) => {
const nexts = list[now];
for (const next of nexts) {
const edge = Math.max(next, now) * 10 + Math.min(next, now);
if (!edges.includes(edge)) { // 枝 (now,next) が通過済みでないならば
if (next === s - 1 && cycle.length === V / 2) {
Euler_cycle.push([...cycle, next]);
}
if(Euler_cycle.length === 0){
dfs(next, [...cycle, next], [...edges, edge]);
}
}
}
};
const [n, s] = lines.shift().split(' ').map(Number);
const list = new Array(n);
let V = 0;
for (let i = 0; i < n; i++) {
const v = Number(lines.shift());
V += v;
const a = lines.shift().split(' ').map(e => e - 1);
list[i] = a;
}
const Euler_cycle = [];
dfs(s - 1, [s - 1], []);
console.log(Euler_cycle[0].map(e => e + 1).join(' '));
});
オイラー閉路…ある頂点を出発後 残りの全ての枝を 1 回ずつ通って出発した頂点に戻ってくるトレイル。
コメント