## JavaScript algorithm 1_ 4 union find algorithm

Be at ease when you meet him 2021-01-22 19:14:45
javascript algorithm 1_ union algorithm

``````/**
* quick-find Algorithm , find It's very fast , find Just go back to id[X],
* But it can't deal with big problems , Because it's every time union Scan the entire array when you do
*/
const inquirer = require("inquirer");
class UF{
constructor(N) {
// count Represents the number of components
let count = N;
// id Representative component id, Index by contacts ;
// The contents of the array created in this way are all empty , Out of commission map
let id = new Array(N);
for (let i = 0; i < N; i++) {
id[i] = i;
}
this.getId = ()=>id;
// Method area
// Get private variables , The number of connected components
this.getCount = ()=> count;
// If p and q If it exists in the same component, it returns true
this.connected = (p,q ) => this.find(p) === this.find(q);
// find p The identifier of the component in which it is located
// quick-find Algorithm
this.find = p => id[p];
// stay p and q Add a connection between
this.union = (p, q) => {
const pID = this.find(p);
const qID = this.find(q);
if(pID === qID) return;
id = id.map(value => {
if (value === pID){
return qID;
}else {
return value;
}
})
count--;
}
}
}
const uf = new UF(10);
// install npm install inquirer, Provides a good solution for receiving input from the command line
const question1 = {
type: 'number',
name: 'count',
message: " How many contacts are there ? \n"
}
const question2 = {
type: 'input',
name: 'points',
filter(input){
return input.split(' ').map(value => Number(value))
},
}
// Enter the number of tentacles
const prompt1 = inquirer.createPromptModule();
// Connection location
const prompt2 = inquirer.createPromptModule();
prompt1(question1)
console.log(` The contacts are \${answers.count} individual `)
autoInput();
})
.catch(e =>{
console.error(e)
});
// Enter the connection location
function autoInput(){
prompt2(question2)
console.log(p, q)
if(!uf.connected(p, q)) {
uf.union(p, q);
}
autoInput();
}else {
console.log(uf.getId(), 'id')
console.log(uf.getCount(), ' base ');
console.log(uf.connected(5, 0), '5 and 0 Is it connected ')
console.log(uf.connected(5, 2), '5 and 2 Is it connected ')
}
})
.catch(e => {
console.log(e);
})
}
``````

https://javamana.com/2021/01/20210122191354317f.html