// 无序图
function Graph() {
// this.nodes = n; // 一共几个节点
this.edges = {}; // 每个节点的边
// 为节点添加边
this.link = (v, m) => {
this.edges[v] = this.edges[v] ? [...this.edges[v], m] : [m];
this.edges[m] = this.edges[m] ? [...this.edges[m], v] : [v];
}
}
/** 广度遍历 /
Graph.prototype.eachByLevel = function (v) {
const pipe = [v]; // 管道，先进先出
const marked = [] // 已被遍历节点
while (pipe.length > 0) {
const node = pipe.shift();
if (!marked.includes(node)) {
marked.push(node)
pipe.push(...(this.edges[node] || []))
}
}
console.log('广度遍历：', marked) // , this.edges
}
/* 最短路径 */
Graph.prototype.shortest = function (v, w) {
const pipe = [v]; // 管道，先进先出
const marked = []; // 已被遍历节点
const edgeTo = {}; // 遍历时反向记录节点间关系
while (pipe.length > 0) {
const node = pipe.shift();
if (!marked.includes(node)) {
marked.push(node)
const edges = this.edges[node] || []
pipe.push(...edges)
// 相邻节点为key，当前节点为value，存入edgeTo
edges.forEach(e => {
edgeTo[e] = edgeTo[e] === undefined ? node : edgeTo[e]
})
}
}
console.log('edgeTo：', edgeTo)
// 从终点反向找起点
const paths = [w]
while (edgeTo[w] !== v) {
w = edgeTo[w]
paths.push(w)
}
paths.push(v)
console.log('reverse shortest path:', paths)
}
/** 深度遍历 */
Graph.prototype.eachByDeep = function (v) {
const marked = []
const recursion = (v) => {
if (marked.includes(v)) return;
else marked.push(v);
const nodes = this.edges[v] || [];
nodes.forEach(n => recursion(n));
}
recursion(v)
console.log('深度遍历：', marked) // , this.edges
}
const graph = new Graph(5)
graph.link(0, 1)
graph.link(0, 2)
// graph.link(0, 4)
graph.link(1, 3)
graph.link(2, 3)
graph.link(5, 3)
graph.link(5, 4)
graph.shortest(0, 5)
// - 广度遍历 比 深度遍历 耗时
// 二叉树
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
show() {
console.log('data:', this.data)
}
}
class Bst {
constructor(root) {
this.root = root;
this.current = root;
}
insert(node) {
this.current = this.root;
while (true) {
if (node.data < this.current.data) {
if (this.current.left) this.current = this.current.left;
else {
this.current.left = node;
break;
}
} else {
if (this.current.right) this.current = this.current.right;
else {
this.current.right = node;
break;
}
}
}
this.current = this.root;
}
show(current) {
current = current ? current : this.root;
const left = current.left ? this.show(current.left) : [];
const right = current.right ? this.show(current.right) : [];
return [...left, current.data, ...right];
}
/** 先序遍历 先访问根节点，然后以同样方式访问左子树和右子树 /
showBefore(current) {
current = current ? current : this.root;
const left = current.left ? this.showBefore(current.left) : [];
const right = current.right ? this.showBefore(current.right) : [];
return [current.data, ...left, ...right];
}
/* 后序遍历 先访问叶子节点，从左子树到右子树，再到根节点 */
showAfter(current) {
current = current ? current : this.root;
const left = current.left ? this.showAfter(current.left) : [];
const right = current.right ? this.showAfter(current.right) : [];
return [...left, ...right, current.data];
}
find(data, current) {
current = current ? current : this.root;
if (data === current.data) return current;
if (data < current.data) {
current = current.left
} else {
current = current.right
}
if (!current) return 'not find'
return this.find(data, current)
}
findParent(node) {
let current = this.root;
let attr = ''
while (current) {
attr = node.data < current.data ? 'left' : 'right'
if (current[attr] === node) break;
else current = current[attr];
}
return { node: current, attr };
}
delete(data) {
const node = this.find(data);
if (node.left === null || node.right === null) {
// 删除根节点
const newnode = node.left || node.right;
if (this.root === node) this.root = newnode;
const parent = this.findParent(node)
parent.node[parent.attr] = newnode;
} else {
let newnode = node.right;
while (newnode.left) {
newnode = newnode.left;
}
newnode = newnode.data;
this.delete(newnode);
node.data = newnode;
}
}
// 练习1
count() {
return this.show().length
}
max() {
let max = this.root;
while (max.right) {
max = max.right;
}
return max.data
}
}
var root = new Node(23)
var bst = new Bst(root)
bst.insert(new Node(45))
bst.insert(new Node(16))
bst.insert(new Node(37))
bst.insert(new Node(3))
bst.insert(new Node(99))
bst.insert(new Node(22))
// console.log('BST:', bst.show())
// console.log('BST bf:', bst.showBefore())
// console.log('BST af:', bst.showAfter())
// console.log('find 3:', bst.find(3))
// console.log('find 3:', bst.find(4))
console.log('BST:', bst.root)
// bst.delete(99)
bst.delete(23)
console.log('2 BST:', bst.root)
console.log('BST count:', bst.count(), 'max:', bst.max())
/**
// 链表
function Node(data) {
this.ele = data;
this.next = null;
}
function LinkList() {
this.head = new Node("head");
this.head.next = this.head;
this.current = this.head;
this.length = 0;
this.push = function (data) {
const newNode = new Node(data);
newNode.next = this.current.next;
this.current.next = newNode;
this.current = newNode;
this.length++;
};
this.delete = function () {
prev.next = this.current.next;
this.current = prev;
this.next();
this.length--;
};
let prev = this.head;
this.next = function () {
prev = this.current;
this.current = this.current.next;
if (this.current == this.head) this.next();
};
this.show = function () {
return this.head;
};
}
// 杀人
function kill(link, number) {
link.current = link.head;
link.next();
while (link.length > 1) {
link.next();
link.next();
console.log(link.current);
link.delete(); //01234 0134 034
}
return link.head;
}
let link = new LinkList();
for (let i = 0; i < 5; i++) link.push(i);
// console.log(link.show()); // 1-29
console.log(kill(link, 3));
// 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29
// 1,2,,4,5,,7,8,,10,11,,13,14,,16,17,,19,20,,22,23,,25,26,,28,29
// ,2,,4,,,7,8,,,11,,13,,,16,17,,,20,,22,,,25,26,,,29
// ,2,,,,,7,8,,,,,13,,,16,,,,20,,22,,,,26,,,29
// ,,,,,,7,8,,,,,,,,16,,,,20,,,,,,26,,,29
// ,,,,,,,,,,,,,,,16,,,,,,,,,,26,,,
// function lastRemaining(n, m) {
// let k = 0;
// for (let i = 2; i <= n; i++) {
// k = (k + m) % i;
// }
// return k;
// }
// console.log(lastRemaining(5000, 3));
*/
网友评论