数据结构
原创
数组
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;}JS 调用栈：
前置说明：
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));队列
- 是一种受限的线性表，FIFO
- 受限之处：它只允许表的前端进行删除操作，在表的后端进行增加操作
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=[]; }}- JS的异步队列undefinedjs为什么是单线程：完成与用户交互以及dom操作；一个线程添加dom一个删除dom，浏览器听谁的，避免复杂性所以直接单线程
- 主线程执行完毕之后，从事件队列中读取任务队列的过程，称之为事件循环(EventLoop)
- Promise是同步的，then和catch是异步的
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
- 插入删除：链表的性能好undefined链表没有大小限制，支持动态扩容，因为链表的每个节点都需要存储前驱/后驱节点的指针，内存消耗会翻倍
- 查询修改：数组性能好
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; }// ......实际上还有代码，此处省略}prototype和 proto
- 所有的引用类型(数组，函数，对象)可以自由的扩展属性(null除外)
- 所有的引用类型都有一个 proto 属性(隐式原型，它其实就是一个普通的对象)
- 所有的函数都有一个prototype属性(显式原型，也是一个普通对)
- 所有的引用类型的 proto 属性都指向它的构造函数的prototype属性
- 当试图得到一个对象的属性时，如果这个对象的本身不存在这个属性，那么就会去它的 proto 属性中找(去它的构造函数的prototype属性中去寻找)
- 当调用这个对象本身并不存在的属性或者方法时，它会一层层的往上找，一直找到null为止，null表示空的对象{}
案例
- 案例一
//构造函数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是一个普通对象，这个对象的构造函数是ObjectTeacher.prototype.show = function(){ console.log(1111);}console.log(Teacher.prototype.__proto__===Object.prototype);//true12.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'));//34console.log(loseloseHashCode('oxgbx'));//34class 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
树的术语
- 结点的度：结点所拥有的子树的个数
- 树的度：树中节点度的最大值
- 叶子(终端结点): 度为0的结点
- 分支结点(非终端结点)：度不为0的结点。除根节点之外的分支结点统称为：内部结点。根节点我们又称为：开始结点
- 结点的层：根节点层：1；其余结点的层数等于父结点的层数+1
- 树的深度：树中所有节点层数的最大值
- 森林：拥有N颗树，就被称为森林
树的存储结构
- 计算机只能是顺序存储或者链式存储，所以树这样的结构是不能够直接存储的，要将其转换为顺序或者链式存储
- 双亲表示法：采用数组存储普通的树，其核心思想：顺序存储每个结点的同时，给各个结点附加一个记录其父结点位置的变量，存储父结点的下标。undefined实际操作的时候，就是从上到下，顺序去遍历一棵树，并为相应的域赋值。undefined优点：可以快速的获取任意结点的父结点位置。undefined缺点：如果要获取某个结点的子结点就要遍历了
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
二叉搜索树(BST)
二叉搜索树其实就是普通二叉树加上了一些限制
- 非空左子树的所有键值都小于其根节点的键值
- 非空右子树的所有键值都大于其根节点的键值
- 左右子树本身也都是二叉搜索树undefined总结：相对较小的值总保存在左子结点上，相对较大的值总是保存在右子结点上
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
红黑树(R-B tree)
AVL树相对于红黑树，它的插入/删除操作效率不高。
红黑树是一种自平衡的二叉搜索树，以前叫做平衡二叉B树;红黑树之所以效率高就是因为平衡，平衡则层级少，则性能高
红黑树增加的一些特性
- 结点是红色或者黑色(结点上有一个color属性)
- 根节点是黑色
- 叶子结点都是黑色，且为null
- 链接红色结点的两个子结点都是黑色，红色结点的父结点都是黑色，红色结点的子结点都是黑色
- 从任意的结点出发，到其每个叶子结点的路径中包含相同数据的黑色结点
这几条规定：保证从根节点到叶子结点的最长路径不大于最短路径的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()); // 2console.log(btins.maximum()); // 8树的应用
- 组织索引，mysql中用的B+树
- JDK1.8的hashmap在单链表冲突之后会使用红黑树
树的深度：从根结点开始，自顶向下逐层累加
树的高度：自底向上逐层累加
图(image)
- 集合只有同属于一个集合的关系
- 线性结构存在一对一的关系
- 树形结构一对多的关系
- 图形结构，多对多的关系
例如微信中，许多的用户组成了一个多对多的朋友关系网，这个关系网就是数据结构当中的图(Graph)
还有导航的最优路径：耗时最短的路径等
45.png
自环：即一条链接一个顶点和自身的边
平行边：连接同一对顶点的两条边
52.png
图的分类
- 无向图: 边没有方向的图称为无向图，边的作用仅仅是连接两个顶点，没有其他含义
- 有向图: 边不仅连接两个顶点，并且具有方向性，可能单向/双向
- 带权图: 边可以带权重
46.png
47.png
图的术语
- 相邻顶点：当两个顶点通过一条边相连时候，我们称这两个顶点是相连的，并且是依附于这两个顶点的
- 度：某个顶点的度：是依附于这个顶点的边的个数
- 子图:一幅图中，所有边的子集组成的图，包含这些边的依附的顶点
- 路径：是由边顺序链接的一系列的顶点组成
- 环：至少含有一条边，且终点和起来相同的路径
- 连通图：如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称为连通图
- 连通子图：组成连通图的非连通图
48.png
欧拉七桥
欧拉开创了新的学科：图论
49.png
图的存储结构
图是由顶点和边构成的，所以在图里边，要存储的图形结构的信息，无非就是存储图的顶点和图的边；
顶点可以直接用数组去存储
1，2，3，4=》1,2,3,4
边存储起来就麻烦一些
存储结构：
- 邻接矩阵
- 矩阵是一个按照长方阵列的负数或者实数集合
- N*M数据的集合(类似九宫格)；可以用1表示顶点与顶点有直接的关系，用0表示没有连接
- 优点：表示明确，例如有向图A->D:1 D->A:0
- 缺点：消耗内存大，存储了太多的0；但是删除会很麻烦，需要一个个置为0；下面的邻接表就可以解决这个问题
50.png
- 邻接表
- 由图中的每个顶点以及和顶点相邻的顶点列表组成。数组/链表/字典
51.png
图的遍历
- 遍历：从某个结点出发，按照一定的搜索路线，依次访问数据结构中的全部结点，而且每个结点访问一次
- 广度优先遍历(BFS)
优先横向遍历图，广度优先的思想，从图中的某个顶点V出发，在访问V之后，依次去访问V的各个未曾访问过的邻结点，然后分别从这些邻结点出发，依次访问他们的邻结点。
注意：图没有横向和纵向的概念
53.png
- 深度优先遍历(LFS)
深度优先有递归的概念
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'}- 常见得求最短路径得算法
有了回溯点，但是实际上通过回溯点计算最短路径的算法有多种
- 迪杰斯拉特算法，是贪心算法的一个应用，用来解决单元点到其余顶点的最短路径的问题
- Floyd算法，经典的动态规划算法
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
作者已关闭评论
推荐阅读
目录
腾讯云开发者
