js的数组不是真正意义上的数组;
数组:再内存中用一串连续的区域来存放一些值。
数组是相同类型数据元素的集合(js的数组可以存储不同类型);
而且一般数组的容量是不会自动变化的
数组内存地址是连续的,但是js中的内存地址是不连续,原因是数据类型可以是任意类型导致的
数组的优点:
数组的缺点:
内存区域:栈区
单片机:压栈
数据结构中有一个同名的数据结构,栈
内存中的堆栈和数据结构中的堆栈不是一个概念,内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象数据存储结构
栈:是一种受限制的线性表,LIFO
其限制是仅允许再表的一端进行插入和删除运算,这一端被称为栈顶,相对的,把另一端称为栈底
向一个栈插入新元素被称为进栈,入栈,压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素
从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素
栈的应用:十进制转二进制
8.png
当时js中有内置api实现,但是此处只是说明一个应用场景
class Stack {
constructor() {
this.items = [];
}
push(ele) {
this.items.push(ele);
}
pop() {
return this.items.pop();
}
//返回栈顶元素
peek() {
return this.items[this.items.length - 1];
}
//判断栈中元素是否为空
isEmpty(){
return this.items.length==0;
}
size() {
return this.items.length;
}
clear() {
this.items=[];
}
}
const binary = number => {
let stack = new Stack();
let remainder = 0;
let top = '';
while (number > 0) {
//除以2取余数
remainder = number % 2;
stack.push(remainder);
//向下取整
number=Math.floor(number/2);
}
//不为空的时候
while (!stack.isEmpty()) {
//栈顶元素
top+=stack.top();
}
return top;
}
前置说明:
1 JavaScript 是一门单线程的语言,这意味着它只有一个调用栈,因此,它同一时间只能做一件事。
2 内存堆:这是内存分配发生的地方.
3 调用栈:这是你的代码执行时的地方
定义:调用栈是解释器(就像浏览器中的javascript解释器)追踪函数执行流的一种机制。当执行环境中调用了多个函数时,通过这种机制,我们能够追踪到哪个函数正在执行,执行的函数体中又调用了哪个函数。
1. 每调用一个函数,解释器就会把该函数添加进调用栈并开始执行。
2 正在调用栈中执行的函数还调用了其它函数,那么新函数也将会被添加进调用栈,一旦这个函数被调用,便会立即执行。
3 当前函数执行完毕后,解释器将其清出调用栈,继续执行当前执行环境下的剩余的代码。
4 当分配的调用栈空间被占满时,会引发“堆栈溢出”
函数的调用本质:"压栈和出栈操作",但是函数在调用栈里面有一个特例,叫做递归
递归:自己调用自己,先进栈,如果不出栈,就会导致:栈溢出
斐波那契数列:从第三项开始,每一项都等于前两项的和1 1 2 3 5 8 13
当数值很大的时候,计算斐波那契数列会出现计算慢(因为有重复计算,函数多同时也会导致调用栈过多)调用栈溢出,解决方案是尾递归优化
尾调用自身就是尾递归
//函数b的尾部调用a函数,被称为尾调用
function a(x) {}
function b(x){
return a(x);
}
b(x);
实际上就是调用a(x);
可以看成没有外部调用帧
如果a就是b本身的话,即使有很多层调用,因为尾递归优化,实际上不会像常规调用一样,帧一层套一层;
总共只有一个调用帧,避免了调用栈溢出
const factor=(n,total)=>{
if (n==1) {
return total;
}
return factor(n-1,n*total);
}
优化斐波那契数列
//原始案例
const Fibonacci = (n) => {
if (n <= 1) {
return 1;
}
return Fibonacci(n - 1)+Fibonacci(n-2);
}
//优化案例
//把前面两位数当作参数传递进来
//此处没有利用常规缓存函数计算结果,而是直接缓存上次总体计算结果;实际上也是利用了缓存
//递归需要同时保存成百上千个调用帧,很容易发生栈溢出,而且因为尾递归优化,只有一个调用栈,永远不会栈溢出
const Fibonacci = (n, ac1 = 1, ac2 = 2) => {
if (n <= 1) {
return ac2;
}
return Fibonacci(n - 1, ac2, ac1 + ac2);
}
console.log(Fibonacci(50,1,1));
9.png
class Quenue{
constructor(){
this.items= [];
}
//入队
enqueue(item){
this.items.push(item);
}
//出队操作
dequeue(){
return this.items.shift();
}
//查看队首元素
front() {
return this.items[0];
}
//查看对尾
rear() {
return this.items[this.items.length-1];
}
//是否为空
isEmpty(){
return this.items.length===0;
}
size(){
return this.items.length;
}
clear(){
this.items=[];
}
}
Promise补充:必须查看 https://segmentfault.com/a/1190000020980101
new Promise((resolve, reject) =>{
resolve();
}).then(() =>{
})
Promise.resolve()
https://segmentfault.com/a/1190000020980101
任务队列:存在着两个队列,一个宏任务一个微任务队列
主线程:同步任务->微任务->宏任务
promise.then catch finally process.nexttick是微任务,
I/O,定时器,ajax,事件绑定是宏任务
例如原型链
10.png
链表就可以解决这样的问题
11.png
class Node {
constructor(element){
this.element = element;
this.next=null;
}
}
//链表
class LinkedList{
constructor(){
//链表头
this.head=null;
//链表长度
this.length=0;
}
//1.链表的尾部追加元素
append(element){
let node=new Node(element);
//如果链表空的
if (this.length===0){
this.head=node;
}else{
//通过head找到后面的节点
let current=this.head;
//遍历,是否是最后一个节点,next为空就是最后一个
while (current.next){
current=current.next;
}
//while执行完毕之后,current就已经是最后一个节点了
}
current.next=node;
this.length+=1;
}
getHead(){
return this.head;
}
toString(){
let current=this.head;
let linkString='';
while(current){
linkString+=','+current.element;
current=current.next;
}
return linkString.slice(1);
}
//任意位置插入元素
insert(element,positon){
//位置不能实负数
if (positon<0||position>this.length) {
return false;
}
let index=0;
let current=this.head;
let previous=null;
let node=new Node(element);
//判断插入的是不是第一个
if (position===0) {
node.text=this.head;
this.head=node;
}else{
while (index<positon) {
previous=current;
current=current.next;
index++;
}
node.next=current;
previous.next=node;
}
this.length+=1;
return true;
}
get(positon){
if (positon<0||positon>this.length) {
return null
}
let current=this.head;
let index=0;
while (index<positon) {
current=current.next;
index++;
}
return current.element;
}
// ......实际上还有代码,此处省略
}
//构造函数
function Teacher(name, habby) {
this.name = name;
this.habby = habby;
this.show = function () {
console.log(1111);
}
}
var t1 = new Teacher('t1', '哈哈哈哈');
var t2 = new Teacher('t2', '呵呵呵呵');
/**
* Teacher它就是一个普通函数但是这个函数的作用:构造对象
* 这种构造对象的方式:工厂方式
*/
//这样new多少次show就有多少个
console.log(t1.show === t2.show);//false
//构造函数
function Teacher(name, habby) {
this.name = name;
this.habby = habby;
this.show = fun
}
function fun() {
console.log(1111);
}
var t1 = new Teacher('t1', '哈哈哈哈');
var t2 = new Teacher('t2', '呵呵呵呵');
console.log(t1.show === t2.show);//true
// 这样存在问题,容易导致全局作用域的污染,并且数据是不安全的容易被覆盖,例如后面还有一个同名的fun函数
//如下
function Teacher(name, habby) {
this.name = name;
this.habby = habby;
}
//Teacher就是构造函数,其内部有prototype属性,而__proto__又会指向构造函数的prototype属性
//Teacher.prototype是一个普通对象,这个对象的构造函数是Object
Teacher.prototype.show = function(){
console.log(1111);
}
console.log(Teacher.prototype.__proto__===Object.prototype);//true
12.png
function Teacher(name, habby) {
this.name = name;
this.habby = habby;
this.show = function () {
console.log(1111);
}
}
//构造方法是空的
function Tt() {}
Tt.prototype = new Teacher('t1', '哈哈哈哈');
var t=new Tt();
t.show();
MD5是目前应用最广泛的Hash算法,但是并不是唯一的算法
13.png
14.png
15.png
16.png
class HashTable {
constructor() {
this.table = [];//哈希表
}
//哈希函数:这只是一个很简化版的
loseloseHashCode(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key[i].charCodeAt();//计算key unicode码
}
//取模
return hash % 37;//37是质数,可以很大程度上避免碰撞
}
//新增元素
put(key, value) {
//获取key
const position = this.loseloseHashCode(key);
this.table[position] = value;
}
//移除元素
remove(key) {
this.table[this.loseloseHashCode(key)]=undefined;
}
//获取元素
get(key) {
return this.table[this.loseloseHashCode(key)];
}
}
const a=new HashTable();
a.put('zq',"zq@qq.com");
console.log(a);//HashTable { table: [ <13 empty items>, 'zq@qq.com' ] }
//由上面输出可知,有很多空项,是因为此时索引不是数字的,所以前面可能存在空项
console.log(a.get('zq'));
数组里面,如果数组的下标相同,后边添加的就会覆盖前面的,这个叫覆盖;
哈希表:冲突,碰撞,对于不同的要存储的数据经过哈希函数得到的索引有可能相同
const arr = [];
arr[1] = 'zq';
arr[1] = 'zq1';
//数组会覆盖
console.log(arr); //[ <1 empty item>, 'zq1' ]
const loseloseHashCode = (key) => {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key[i].charCodeAt();
}
return hash % 37;
}
console.log(loseloseHashCode('money'));//34
console.log(loseloseHashCode('oxgbx'));//34
class HashTable {
constructor() {
this.table = [];//哈希表
}
//哈希函数:这只是一个很简化版的
loseloseHashCode(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key[i].charCodeAt();//计算key unicode码
}
//取模
return hash % 37;//37是质数,可以很大程度上避免碰撞
}
//新增元素
put(key, value) {
//获取key
const position = this.loseloseHashCode(key);
this.table[position] = value;
}
//移除元素
remove(key) {
this.table[this.loseloseHashCode(key)]=undefined;
}
//获取元素
get(key) {
return this.table[this.loseloseHashCode(key)];
}
}
const a=new HashTable();
a.put('money',"money@qq.com");
a.put('oxgbx',"oxgbx@qq.com");
console.log(a.get('money')); //oxgbx@qq.com
17.png
35%10结果是5,发现5上面有数据,就会向后找,发现6没有放数据就会放在6里面;
线性探测法在数据聚集的时候会影响hash表的性能,无论是插入/删除/查询
18.png
因为链表是元素本身和指向下一个元素的指针;所以首先哈希运算取得对应索引(例如:1,2,3这种);然后后面是链表而且是多个,可以再利用元素本身和链表中元素进行比较
例如:dom树,linux系统的层级结构
19.png
20.png
21.png
22.png
顺序表=》数组,从树的根节点开始,使用数组依次存储树的各个结点,需要注意的是,孩子表示法会被各个结点配备一个链表,用于存储各结点的孩子结点位于数组中的位置,如果说,结点没有子结点(叶子结点),则该结点的链表为空链表。
23.png
25.png
24.png
二叉树:其实所有的树的本质都是可以使用二叉树进行模拟出来的,所以二叉树很重要;二叉树的存储方式有数组和链表,最合适的方式是链表;从上到下从左至右
26.png
满二叉树:在一颗二叉树中,如果所有的分支结点都存在于左子树和右子树,并且所有的叶子都在同一层,这样的二叉树就是满二叉树;叶子只能出现在最下一层,出现在其他层,不可能达成平衡;非叶子结点的度一定是2
27.png
完全二叉树:满二叉树一定是完全二叉树,反之则不是;设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1)
的结点数都达到最大个数(其实就是2,因为完全二叉树就是满二叉树分支最多两个),
第 h 层所有的结点都连续集中在最左边
28.png
左斜树
29.png
右斜树
30.png
二叉搜索树其实就是普通二叉树加上了一些限制
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(key) { // 插入数据
var newNode = new Node(key);
if (this.root == null) {
this.root = newNode;
} else {
var current = this.root;
while (true) {
if (key < current.key) {
if (current.left) {
current = current.left;
} else {
current.left = newNode;
break;
}
} else if (key > current.key) {
if (current.right) {
current = current.right;
} else {
current.right = newNode;
break;
}
}
}
}
}
centerSort(node, arr = []) { // 中序排列
if (node) {
this.centerSort(node.left, arr);
arr.push(node.key);
this.centerSort(node.right, arr);
}
return arr;
}
prevSort(node, arr = []) { // 前序排列
if (node) {
arr.push(node.key);
this.prevSort(node.left, arr);
this.prevSort(node.right, arr);
}
return arr;
}
nextSort(node, arr = []) { // 后续排列
if (node) {
this.nextSort(node.left, arr);
this.nextSort(node.right, arr);
arr.push(node.key);
}
return arr;
}
getMin(node) { // 获取二叉树的最小值
node = node || this.root;
while (node.left != null) {
node = node.left;
}
return node.key;
}
getMax(node) { //获取二叉树最大值
node = node || this.root;
while (node.right != null) {
node = node.right;
}
return node.key;
}
find(key) { // 查找 给定的值
var node = this.root;
while (node != null) {
if (key < node.key) {
node = node.left;
} else if (key > node.key) {
node = node.right;
} else {
return node;
}
}
return null;
}
remove(key) { // 删除给定的值
this.root = this.removeNode(this.root, key);
}
removeNode(node, key) { // 真正删除的函数
if (node == null) {
return null;
}
if (key < node.key) {
node.left = this.removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = this.removeNode(node.right, key);
return node;
} else {
if (node.left == null && node.right == null) {
node = null;
return node;
} else if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
var minNode = this.getMin(node.right);
node.key = minNode.key;
node.count = minNode.count;
node.right = this.removeNode(node.right, minNode.key);
return node;
}
}
}
}
先序遍历,中序遍历,后序遍历(用的少,也叫层次遍历)
31.png
32.png
33.png
删除:
34.png
35.png
36.png
37.png
二叉搜索树的优点:作为数据存储的结构有重要的意义,可以快速的找到给定的关键字的数据项,并且可以快速的插入和删除数据
二叉搜索树的缺点:具有局限性,同样的数据(但是顺序不同的情况下),可以对应不同的二叉搜索树,主要就是因为左大右小的规则
38.png
如上图:二叉搜索树可能退化成一个链表的,二叉搜索树的操作速度和高度是相关的,如果出现这种右斜树类型的链表,则效率高也就成了一句空话
好的二叉搜索树的结构:左右分布均匀,但是我们插入连续的数据的时候,会导致数据分布不均匀,就把分布不均匀的树称为非平衡树(如上图右边)
平衡树:AVL(不常用,整体效率低于红黑树),红黑树
39.png
下图只是说明平衡因子计算规则,而不是平衡二叉树
39-1.png
40.png
41.png
42.png
43.png
AVL树相对于红黑树,它的插入/删除操作效率不高。
红黑树是一种自平衡的二叉搜索树,以前叫做平衡二叉B树;红黑树之所以效率高就是因为平衡,平衡则层级少,则性能高
红黑树增加的一些特性
这几条规定:保证从根节点到叶子结点的最长路径不大于最短路径的2倍
红黑树插入数据的时候,会先去遍历数据应该插入到哪个位置,插入的数据一定是红色的,因为插入黑色会破坏平衡
通过旋转(左旋转,右旋转)变色
等满足上述五条性质;
44.png
const RED = true;
const BLACK = false;
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
this.color = RED;
}
}
class RBT {
constructor() {
this.root = null;
this.size = 0;
}
isRed(node) {
if (!node) return BLACK;
return node.color;
}
// 左旋 右红左黑
leftRotate(node) {
let tmp = node.right;
node.right = tmp.left;
tmp.left = node;
tmp.color = node.color;
node.color = RED;
return tmp;
}
// 右旋转 左红左子红
rightRoate(node) {
let tmp = node.left;
node.left = tmp.right;
tmp.right = node;
tmp.color = node.color;
node.color = RED;
return tmp;
}
// 颜色翻转
flipColors(node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
add(key, value) {
this.root = this.addRoot(this.root, key, value);
this.root.color = BLACK; // 根节点始终是黑色
}
addRoot(node, key, value) {
if (!node) {
this.size++;
return new Node(key, value);
}
if (key < node.key) {
node.left = this.addRoot(node.left, key, value);
} else if (key > node.key) {
node.right = this.addRoot(node.right, key, value);
} else {
node.value = value;
}
if (this.isRed(node.right) && !this.isRed((node.left))) {
node = this.leftRotate(node);
}
if (this.isRed(node.left) && this.isRed((node.left.left))) {
node = this.rightRoate(node);
}
if (this.isRed(node.left) && this.isRed(node.right)) {
this.flipColors(node);
}
return node;
}
isEmpty() {
return this.size == 0 ? true : false;
}
getSize() {
return this.size;
}
contains(key) {
let ans = '';
!(function getNode(node, key) {
if (!node || key == node.key) {
ans = node;
return node;
} else if (key > node.key) {
return getNode(node.right, key);
} else {
return getNode(node.right, key);
}
})(this.root, key);
return !!ans;
}
// bst前序遍历(递归版本)
preOrder(node = this.root) {
if (node == null) return;
console.log(node.key);
this.preOrder(node.left);
this.preOrder(node.right);
}
preOrderNR() {
if (this.root == null) return;
let stack = [];
stack.push(this.root);
while (stack.length > 0) {
let curNode = stack.pop();
console.log(curNode.key);
if (curNode.right != null) stack.push(curNode.right);
if (curNode.left != null) curNode.push(curNode.left);
}
}
// bst中序遍历
inOrder(node = this.root) {
if (node == null) return;
this.inOrder(node.left);
console.log(node.key);
this.inOrder(node.right);
}
// bst后续遍历
postOrder(node = this.root) {
if (node == null) return;
this.postOrder(node.left);
this.postOrder(node.right);
console.log(node.key);
}
// bsf + 队列的方式实现层次遍历
generateDepthString1() {
let queue = [];
queue.unshift(this.root);
while (queue.length > 0) {
let tmpqueue = []; let ans = [];
queue.forEach(item => {
ans.push(item.key);
item.left ? tmpqueue.push(item.left) : '';
item.right ? tmpqueue.push(item.right) : '';
});
console.log(...ans);
queue = tmpqueue;
}
}
minmun(node = this.root) {
if (node.left == null) return node;
return this.minmun(node.left);
}
maximum(node = this.root) {
if (node.right == null) return node;
return this.maximum(node.right);
}
}
let btins = new RBT();
let ary = [5, 3, 6, 8, 4, 2];
ary.forEach(value => btins.add(value));
btins.generateDepthString1();
// ///////////////
// 5 //
// / \ //
// 3 8 //
// / \ / //
// 2 4 6 //
// ///////////////
console.log(btins.minmun()); // 2
console.log(btins.maximum()); // 8
树的深度:从根结点开始,自顶向下逐层累加
树的高度:自底向上逐层累加
例如微信中,许多的用户组成了一个多对多的朋友关系网,这个关系网就是数据结构当中的图(Graph)
还有导航的最优路径:耗时最短的路径等
45.png
自环:即一条链接一个顶点和自身的边
平行边:连接同一对顶点的两条边
52.png
46.png
47.png
48.png
欧拉开创了新的学科:图论
49.png
图是由顶点和边构成的,所以在图里边,要存储的图形结构的信息,无非就是存储图的顶点和图的边;
顶点可以直接用数组去存储
1,2,3,4=》1,2,3,4
边存储起来就麻烦一些
50.png
51.png
优先横向遍历图,广度优先的思想,从图中的某个顶点V出发,在访问V之后,依次去访问V的各个未曾访问过的邻结点,然后分别从这些邻结点出发,依次访问他们的邻结点。
注意:图没有横向和纵向的概念
53.png
深度优先有递归的概念
54.png
55.png
let scanf = require('scanf');
//定义邻接矩阵
let Arr2 = [
[0, 1, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 1, 0, 1],
[0, 1, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0, 1, 1, 1],
[0, 0, 0, 1, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 1, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0, 0, 0, 0],
]
let numVertexes = 9, //定义顶点数
numEdges = 14; //定义边数
// 定义图结构
function MGraph() {
this.vexs = []; //顶点表
this.arc = []; // 邻接矩阵,可看作边表
this.numVertexes = null; //图中当前的顶点数
this.numEdges = null; //图中当前的边数
}
let G = new MGraph(); //创建图使用
//创建图
function createMGraph() {
G.numVertexes = numVertexes; //设置顶点数
G.numEdges = numEdges; //设置边数
//录入顶点信息
for (let i = 0; i < G.numVertexes; i++) {
G.vexs[i] = scanf('%s'); //String.fromCharCode(i + 65); ascii码转字符
}
console.log(G.vexs) //打印顶点
//邻接矩阵初始化
for (let i = 0; i < G.numVertexes; i++) {
G.arc[i] = [];
for (j = 0; j < G.numVertexes; j++) {
G.arc[i][j] = Arr2[i][j]; //INFINITY;
}
}
/**以下是手动录入的方式 */
// for (let k = 0; k < G.numEdges; k++) {
// console.log('输入边(vi,vj)上的下标i,下标j和权w:');
// let rlt = scanf('%d,%d,%d');
// let i = rlt[0], j = rlt[1], w = rlt[2];
// G.arc[i][j] = w;
// G.arc[j][i] = G.arc[i][j]; //无向图,矩阵对称
// }
console.log(G.arc); //打印邻接矩阵
}
let visited = []; //访问标志数组,遍历时使用
//邻接矩阵的深度优先递归算法
function DFS(i) {
visited[i] = true;
console.log('打印顶点:', G.vexs[i]) //打印顶点 ,也可以其他操作
for (let j = 0; j < G.numVertexes; j++) {
if (G.arc[i][j] == 1 && !visited[j]) {
console.log(G.vexs[i], '->', G.vexs[j])
DFS(j) //对未访问的顶点进行递归
}
}
}
//邻接矩阵的深度遍历操作
function DFSTraverse() {
for (let i = 0; i < G.numVertexes; i++) {
visited[i] = false;
}
for (let i = 0; i < G.numVertexes; i++) {
if (!visited[i])
DFS(i)
}
}
//邻接矩阵的广度遍历算法
function BFSTraverse() {
let queue = []; //初始化队列
for (let i = 0; i < G.numVertexes; i++) {
visited[i] = false;
}
for (let i = 0; i < G.numVertexes; i++) { //对每一个顶点做循环
if (!visited[i]) { //如果没有访问过就处理
visited[i] = true;
console.log('打印顶点:', G.vexs[i]) //也可以是其他操作
queue.push(i); //将此顶点入队列
while (queue.length != 0) { //当前队列不为空
queue.shift();
for (let j = 0; j < G.numVertexes; j++) {
//判断其他顶点若与当前顶点存在边且未访问过
if (G.arc[i][j] == 1 && !visited[j]) {
visited[j] = true;
console.log(G.vexs[i], '->', G.vexs[j])
console.log('打印顶点:', G.vexs[j])
queue.push(j) //将此顶点放入队列
}
}
}
}
}
}
* 寻找最短路径,所谓路径指的是:如果从图中的某一个顶点(起点,圆点)到达另外一个顶点(终点)路径步可能只有一条,如何找到一条路径使得沿这个路径边上的权值总和(路径长度)达到最小回溯点
* 回溯点是离上一个顶点`最近的顶点`。A的回溯电是null,B的回溯点是:A,E的回溯点是B 回溯路径(所有回溯点组成)undefined通过回溯点可以查找到最短路径
56.png
const prev={
'A':null,
'B':'A',
'E':'B'
}
有了回溯点,但是实际上通过回溯点计算最短路径的算法有多种
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。