数据结构学习笔记
1.位运算
左移<<
右移>> :可以用在二分算法中取中间值,比如
13>>1
2.按位操作
按位与
&
:每一位都为1,结果才为1按位或
|
:其中一位为1,结果就是1按位异或
^
:每一位都不同,结果才为1
3.栈
特点:后进先出(LIFO)
算法基本思想:因为只能从栈的顶部压入数据也只能从栈的顶部弹出数据,所以可以用一个单链表实现。因为只针对栈顶元素操作,所以借用单链表的头可以让所有的操作在O(1)的时间内完成
场景:在解决问题时,只关心上一次的操作,处理完上一次的操作后,能在O(1)时间内查找到更前一次的操作。比如leecode20题(有效的括号)、739题(每日温度)
使用栈解决迷宫问题
let maze=[ [1,1,1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,0,0,1,1,0,0,1], [1,0,1,1,1,0,0,0,0,1], [1,0,0,0,1,0,0,0,0,1], [1,0,1,0,0,0,1,0,0,1], [1,0,1,1,1,0,1,1,0,1], [1,1,0,0,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1] ] function maza_path(){ let stack=[],nextNode stack.append((x1,y1)) while(stack.length>0){ let curNode=stack[-1] //当前的节点 if(curNode[0]==x2&&curNode[1]==y2){ //走到终点了 for(P in stack){ console.log(p) } return true } //x,y四个方向 x-1,y; x+1,y; x,y-1; x,y+1 for(dir in dirs){ nextNode=dir(curNode[0],curNode[1]) //如果下一个节点能走 if(maze[nextNode[0][nextNode[1]]]==0){ stack.append(nextNode) maze[nextNode[0]][nextNode[1]]==2 //2表示为已经走过 break } } maza[nextNode[0][nextNode[1]]==2 stack.pop() }else{ console.log('没有路') return false } }复制代码
4.队列
特点:先进先出(FIFO),在队尾查看和添加数据,在队头查看和删除数据
实现:用双链表
场景:按照一定顺序处理数据且数据不断变化时,比如广度优先搜索。
广度优先搜索的思路是:(1)从一个节点开始,寻找所有接下来能继续走的点,继续不断寻找,直到找到出口(2)使用队列存储当前正在考虑的节点
(1)队列的实现方式--环形队列
环形队列:当队尾指针
front==Maxsize+1
时,再前进一个位置就自动到0
队首指针前进1:
front=(front+1)% Maxsize
队尾指针前进1:
rear=(rear+1)% Maxsize
队空条件:
rear==front
队满条件:
(rear+1)% Maxsize==front
Queue(){ function init(self,size=100){ self.queue=[0,size.random()] self.size=size self.rear=0 //队尾指针 self.front=0 //队首指针 } function push(self,element){ self.rear=(self.rear+1)%self.size self.queue[self.rear]=element } function pop(self){ if(!self.isEmpty()){ self.front=(self.front+1) % self.size return self.queue[self.front] }else{ console.log('error') } } function isEmpty(self){ return self.rear==self.front } function isFilled(self){ return (self.rear+1)%self.size==self.front } }复制代码
(2)双端队列:
可以利用一个双链表
队列的头尾两端能在O(1)的时间内进行数据的查看、添加和删除
场景:实现一个长度动态变化的窗口或者连续区间。leecode239题(滑动窗口最大值)
(3)优先队列:
与普通队列区别:保证每次取出的元素是队列中优先级最高的、优先级别可自定义
最常用的场景:从杂乱无章的数据中按照一定顺序(或者优先级)筛选数据
本质:二叉堆的结构,堆在英文里叫Binary Heap,利用一个数组结构来实现完全二叉树
特性:数组里的第一个元素
array[0]
拥有最高优先级
给定一个下标
i
,那么对于元素array[i]
而言父节点对应的元素下标是
(i-1)/2
左侧子节点对应的元素下标是
2*i+1
右侧子节点对应的元素下标是
2*i+2
数组中每个元素的优先级都必须高于它两侧子节点
基本操作:向上筛选、向下筛选
时间复杂度:
O(logk)
初始化一个大小为n的堆,时间复杂度为
O(n)
。leetcode347题
5.排序
冒泡排序、选择排序、插入排序的时间复杂度都为O(n*n)
冒泡排序:从第一个元素开始,和下一个索引元素比较大小。如果当前元素大就交换位置,重复操作直到最后一个元素。那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作,但是此时最后一个元素已经是最大数了,所以不需要再比较最后一个元素,只需要比较到
length-2
的位置时间复杂度为O(n*n)
//使用双循环来进行排序。外部循环控制所有的回合,内部循 环代表每一轮的冒泡处理,先进行元素比较,再进行元素交换 function sort(array){ let tmp = 0; for(let i = 0; i < array.length; i++){ for(let j = 0; j < array.length - i - 1; j++){ if(array[j] > array[j+1]){ tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } } return array } let array =[5,8,6,3,9,2,1,7]; sort(array); 复制代码
优化: 如果我们能判断出数列已经有序,并且做出标记(使 用一个变量判断),剩下的几轮排序就可以不必执行,提早结 束工作
function sort(array){ let tmp = 0; for(let i = 0; i < array.length; i++) { //有序标记,每一轮的初始是true let isSorted = true; for(let j = 0; j < array.length - i - 1; j++) { if(array[j] > array[j+1]){ tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; isSorted = false; //有元素交换,所以不是有序,标记变为 false } } if(isSorted){ break; } } } let array = [5,8,6,3,9,2,1,7]; sort(array); 复制代码
如果数组中后部分是有序的,可以这样优化 * 设置一个无序序列的边界,每次排序到这里就停止
function sort(array){ let tmp = 0; let lastExchangeIndex = 0; //记录最后一次交换的位置 let sortBorder = array.length - 1; //无序数列的边界,每次比较只需要比到这里为止 for(let i = 0; i < array.length; i++){ let isSorted = true; //有序标记,每一轮的初始是true for(let j = 0; j < sortBorder; j++){ if(array[j] > array[j+1]){ tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; isSorted = false; //有元素交换,所以不是有序,标记变 为false lastExchangeIndex = j; //把无序数列的边界更新为最后一次交 换元素的位置 } } sortBorder = lastExchangeIndex; if(isSorted){ break; } } } let array = [3,4,2,1,5,6,7,8]; sort(array); 复制代码
插入排序:第一个元素默认是已排序元素,取出下一个元素和当前元素比较,如果当前元素大就交换位置。那么此时第一个元素就是当前最小数,所以下次取出操作从第三个元素开始,向前对比,重复之前的操作。比如:
[3,38,5,47,36,26]
时间复杂度为O(n*n):leetcode 147题
//可以想象要插入的值为从别的地方抽取的牌,与手里的牌做比较 function insert_sort(li){ for (var i in (1, li.length)){ let tmp=li[i] j=i-1 while(j>=0 && tmp<li[j]){ //当满足这两个条件时,说明还没找到适合抽取的牌插入的位置 li[j+1] =li[j] j=j-1 } li[j+1]=tmp //当j<0或者tmp>li[j]时把牌插入j+1的位置 } return li }复制代码
选择排序:遍历数组,设置最小值的索引为0,如果取出的值比当前最小值小,就替换最小值索引,遍历完成后,将第一个元素和最小值索引上的值交换。如上操作后,第一个元素就是数组中的最小值,下次遍历就可以从索引1开始重复上述操作。比如:
[3,38,5,47,36,26]
时间复杂度为O(n*n)
//因为每次遍历都能得到无序区的最小值,所以交换后的值所在的区域为有序区,剩余的位置在无序区(以i为划分线) function select_sort(li){ for (var i in li.length-1){ let min_loc= i //最小元素的位置,首先假设它在无序区的第一位 for(var j;j>=i+1 && j<li.length;j++){ //无序区遍历出最小元素,j从i+1开始算可以减少一次i和自身比较的次数 if(li[j]<li[min_loc]){ min_loc=j } } li[i]=li[min_loc] //无序区第一位和最小元素所在的位置交换 li[min_loc]=li[i] } return li }复制代码
归并排序,快速排序,堆排序 ----三种排序算法的时间复杂度都是O(nlogn)
一般情况下,就运行时间而言:快速排序<归并排序<堆排序
三种排序算法的缺点:
快速排序:极端情况下排序效率低
归并排序:需要额外的内存开销
堆排序:在快的排序算法中相对较慢
归并排序:数组先切分成两个元素一组的多个数组,再按顺序合成一个大数组
时间复杂度为O(N*logN),空间复杂度O(n)
步骤
function merge(li,low,mid,high){ let i=low, j=mid+1 ltmp=[] while(i<=mid&&j<=high){ //只要左右两边都有数 if(li[i]<=li[j]){ ltmp.append(li[i]) i+=1 }else{ ltmp.append(li[j]) j+=1 } } //while执行完,肯定有一部分没数了,下边的两个while,只会执行其中一个 while(i<=mid){ ltmp.append(li[i]) i+=1 } while(j<=high){ ltmp.append(li[j]) j+=1 } li[low,high+1]=ltmp } function mergesort(li,low,high){ if(low<high){ mid=(low+high)/2 mergesort(li,low,mid) mergesort(li,mid+1,high) merge(li,low,mid,high) } }复制代码
分解:将列表越分越小,至分成一个元素
终止条件:一个元素是有序的
合并:将两个有序列表归并,列表越来越大
快排:先取出一个基准值,比基准值大的放右边,比基准值小的放左边,对比完成后将基准值和第一个比基准值大的值交换位置,然后将数组以基准值的位置分为两部分,继续递归以上操作。
快速排序一般时间复杂度为nlogn,最坏时间复杂度为n*n(当每次递归时只能多增加一个有序区的值即每次只能为一个值排序)
function partition(li,left,right){ let tmp=li[left] while(left < right){ while(left<right && li[right]>=tmp){//从右边找比tmp小的数 right-=1 //往左走一步 } li[left]=li[right] //把右边的值写到左边空位上 while(left<right && li[right]<=tmp){ left+=1 } li[right]=li[left] //把左边的值写到右边空位上 } li[left]=tmp //把tmp归位 return left } function quick_sort(li,left,right){ if(left<right){ //列表至少有两个元素 mid=partition(li,left,right) quick_sort(li,left,mid-1) quick_sort(li,mid+1,right) } }复制代码
堆排序:先遍历出最大值放到数组的首位,然后将数组首位和末尾交换位置并将数组长度减一,然后重复以上操作,得到一个大根堆(某个节点的所有子节点的值都比他小)
建立堆
得到堆顶元素,为最大元素
去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整重新使堆有序
堆顶元素为第二大元素
重复步骤3,直到堆变空
堆的向下调整性质:1.假设根节点的左右子树都是堆,但根节点不满足堆的性质;2.可以通过一次向下调整来将其变成一个堆 时间复杂度
nlogn
//创建一个大根堆 function sift(data,low,high){ let i=low, //i最开始指向根节点 j=2*i+1, //j最开始是根节点的左孩子 tmp=data[i] //把堆顶存起来 while(j<=high){ //只要j位置有数 if(j<high&&data[j]<data[j+1]){ //如果有右孩子并且比较大 j+=1 //j指向右孩子 } if(temp<data[j]){ data[i]=data[j] i=j //往下看一层 j=2*i+1 }else{ //tmp更大,把tmp放到i的位置上 break } } data[i]=tmp //把tmp放到叶子节点上 } function heap_sort(data){ let n=data.length for(let i in range(n/2-1,-1,-1)){ sift(data,i,n-1) //i表示建堆的时候调整的部分的根的下标 } // 以上部分建堆完成 for(let j in range(n-1,-1,-1)){ //i指向当前堆的最后一个元素 data[0]=data[i] data[i]=data[0] sift(data,0,i-1) //i-1是新的high } }复制代码
延伸:topK问题:现在有n个数,设计算法得到前k大的数(k<n)(比如微博热搜)
解决思路
取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数
依次向后遍历原列表,对于列表中的元素,如果小于堆顶,则忽略该元素;如果大于堆顶,则将堆顶更换为该元素,并且对堆进行一次调整
遍历列表所有元素后,倒序弹出堆顶
解决方法
排序后切片
O(nlogn)
冒泡排序、选择排序、插入排序
O(kn)
堆排序思路
O(nlogk)
//创建一个小根堆 function sift(data,low,high){ let i=low, //i最开始指向根节点 j=2*i+1, //j最开始是根节点的左孩子 tmp=data[i] //把堆顶存起来 while(j<=high){ //只要j位置有数 if(j<high&&data[j]>data[j+1]){ j+=1 //j指向右孩子 } if(temp>data[j]){ data[i]=data[j] i=j //往下看一层 j=2*i+1 }else{ break } } data[i]=tmp //把tmp放到叶子节点上 } function topk(li,k){ let heap=li[0,k] for(let i in range((k-2/2),-1,-1)){ sift(heap,i,k-1) } //1.建堆 for(let i in range(k,li.length-1)){ if(li[i]>heap[0]){ heap[0]=li[i] sift(heap,0,k-1) } } //2.遍历 for(let i in range(k-1,-1,-1)){ heap[0],heap[i]=heap[i],heap[0] sift(heap,0,i-1) } //3.出数 return heap }复制代码
总结:
6.链表
链表是由一系列节点组成的元素集合。每个节点包含两部分,数据域
item
和指向下一个节点的指针next
。通过节点之间的相互连接,最终串联成一个链表
class Node(object){ function init(self,item){ self.item=item self.next=None } } function create_linklist(li){ let head=Node(li[0]) for(element in li){ node=Node(element) node.next=head head=node } return head } function create_linklist_tail(li){ let head=Node(li[0]), tail=head for(element in li){ node=Node(element) tail.next=node tail=node } return head } lk=create_linklist_tail([1,2,3,5,6])复制代码
创建链表:头插法,尾插法
链表节点的插入、删除
p.next=curNode.next curNode.next=p复制代码
插入:
删除
p=curNode.next curNode.next=curNode.next.next del p复制代码
双链表:双链表的每个节点有两个指针:一个指向后一个节点,另一个指向前一个节点
双链表节点的插入
p.next=curNode.next curNode.next.prior=p p.prior=curNode curNode.next=p复制代码
双链表节点的删除
p=curNode.next curNode.next=p.next p.next.prior=curNode del p复制代码
链表与顺序表
链表在插入和删除的操作上明显快于顺序表
链表的内存可以更灵活的分配(试利用链表重新分配栈和队列)
链表这种链式存储的数据结构对树和图的结构有很大的启发性
数组和链表有什么区别,链表有什么特点?
数组静态分配内存,链表动态分配内存;
数组在内存中连续,链表不连续;
数组元素在栈区,链表元素在堆区;
数组可以根据下标进行快速定位,时间复杂度为O(1),链表定位元素时间复杂度O(n)(因为链表访问元素需要移动指针);
数组插入或删除元素的时间复杂度O(n)(因为需要移动大量的元素),链表的时间复杂度O(1)(因为只需要修改指针即可)。
参考链接:javascript实现链表数据结构和反转单链表方法
function myReverse (linkedList) { // 1 拿到传参链表的head var head = linkedList.head // 2 边界判断 如果头结点是空 或者只有一个结点 那还反转个啥 if(head === null || head.next === null) return linkedList // 3 用三个指针 var current = head var pre = null var next = null #判断当前节点是否为空 #不为空就先获取当前节点的下一节点 #然后把当前节点的next设为上一个节点 #然后把current设为下一个节点,pre设为当前节点 while(current != null) { next = current.next current.next = pre pre = current current = next } linkedList.head = pre }复制代码
引申:获取链表倒数第k个节点、链表中间节点及判断链表是否有环blog.csdn.net/qq_40608516…
7.树
树是一种数据结构,比如:目录结构
树是一种可以递归定义的数据结构
树是由n个节点组成的集合:如果n=0,那这是一颗空树;如果n>0,那存在1个节点作为树的根节点,其他节点可以分为m个集合,每个集合本身又是一棵树
树的度:树中某个节点最多叉的个数为树的度
树的共性:结构直观、通过树问题来考察递归算法掌握的熟练程度
面试中常考的树的形状有:普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树、多叉树
特殊的树:红黑树、自平衡二叉搜索树
(1)二叉树
首先了解下什么是二叉树
二叉树
二叉树:度不超过2的树
每个节点最多有两个孩子节点
两个孩子节点被区分为左孩子节点和右孩子节点
满二叉树:一个二叉树,如果每一个层的节点树都达到最大值,则这个二叉树就是满二叉树
完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的节点都集中在该层最左边的若干位置的二叉树
大根堆:一棵完全二叉树,满足任一节点都比其他孩子节点大
小根堆:一棵完全二叉树,满足任一节点都比其孩子节点小
二叉树的存储方式(表示方式)
链式存储方式:将二叉树的节点定义为一个对象,节点之间通过类似链表的链接方式来连接
顺序存储方式(用列表)
二叉树的先序,中序,后序遍历
先序遍历表示先访问根节点,然后访问左节点,最后访问右节点:应用场景(在树里搜索或创建一颗新树)
中序遍历表示先访问左节点,然后访问根节点,最后访问右节点:应用场景(二叉搜索树:根节点大于左边小于右边,一般不出现重复的值),leetcode第230题
后序遍历表示先访问左节点,然后访问右节点,最后访问根节点:比如leetcode250题
具体介绍参考:二叉树遍历(先序、中序、后序)
中序遍历的前驱后继节点:
前驱节点:就是中序遍历排序中相对的前一个 后继节点:就是中序遍历排序中相对的后一个
树的深度
(2)前缀树(也称字典树):这种数据结构被广泛地运用在字典查找当中
什么是字典查找?例如/;给定一系列构成字典的字符串,要求在字典当中找出所有以“ABC”开头的字符串
时间复杂度:O(M*N )开头长度为M
时间复杂度:O(M)
方法二:前缀树
方法一:暴力搜索法
应用场景:
搜索框输入搜索文字,回罗列以搜索词开头的相关搜索
汉语拼音输入法
重要性质:
每个节点至少包含两个基本属性
children:数组或者集合,罗列出每个分支当中包含的所有字符
isEnd:布尔值,表示该节点是否为某字符串的结尾
根节点是空的
除了根节点,其他所有节点都可能是单词的结尾,叶子节点一定都是单词的结尾
4.最基本的操作
创建 ,方法为
遍历一遍输入的字符串,对每个字符串的字符进行遍历
从前缀树的根节点开始,将每个字符加入到节点的children字符集当中
如果字符集已经包含了这个字符,跳过
如果当前字符是字符串的最后一个,把当前节点的isEnd标记为真
搜索,方法为
从前缀树的根节点出发,逐个匹配输入的前缀字符
如果遇到了,继续往下一层搜索
如果没遇到,立即返回
leetcode212题(可以使用深度优先算法)
(3)线段树
假设求数组任意一段区间里元素的总和(或者平均值)
方法一:遍历一遍数组:时间复杂度为O(n)
方法二:线段树:时间复杂度为O(logn)---依赖于树的高度
线段树是什么?一种按照二叉树的形式存储数据的结构,每个节点保存的都是数组里某一段的总和 例如
(4)树状数组
8.递归和回溯
递归:自顶向下 leetcode 247题(中心对称树)
回溯: leetcode 39题(组合总和)
可以用在下列算法中:
二叉树的定义和遍历
归并排序、快速排序
动态规划
二分搜索
引申1:递归有什么优缺点
优点: 代码简洁。 易于理解
缺点:
时间和空间的消耗比较大:
递归由于是函数调用自身,而函数调用是消耗时间和空间的。每一次函数调用,都需要在内存栈中分配空间以保存参数,返回值和临时变量。而往栈中压入和弹出数据也都需要时间,所以降低了效率。
重复计算:
递归中又很多计算都是重复的,递归的本质时把一个问题分解成两个或多个问题,多个问题存在重叠的部分,即存在重复计算。如斐波那契数列的递归实现。
栈溢出:
递归可能存在栈溢出,每次调用时都会在内存栈中分配空间。而栈空间的容量是有限的,当调用的次数太多,就可能会超出栈的容量,造成调用栈溢出
引申2:从有序数组中找出某个数出现的次数:
可以使用二分查找
直接比较
int findCount(int a[],int len ,int key) { int i,count = 0; for(i=0;i<len;i++) { if(key==a[i]) count++; } return count; }复制代码
9.动态规划
动态规划当中包含三个重要的概念:
最优子结构
边界
状态转移公式
动态规划的本质其实就是两点: 1.自底向上分解子问题 2.通过变量存储已经计算过的解
斐波那契数列的动态规划思路:
斐波那契数列从0和1开始,那么这就是这个子问题的最底层
通过数组来存储每一位所对应的斐波那契数列的值
0-1背包问题:参考算法题之动态规划-01背包问题
10.哈希表
哈希表一个通过哈希函数来计算数据存储位置的数据结构,通常支持如下操作:
insert(key,value):插入键值对(key,value)
get(key):如果存在键为key的键值对则返回其value,否则返回空值
delete(key):删除键为key的键值对
数组里面有10万个数据,取第一个元素和第10万个元素的时间相差多少
JavaScript
没有真正意义上的数组,所有的数组其实是对象,其“索引”看起来是数字,其实会被转换成字符串,作为属性名(对象的key
)来使用。所以无论是取第 1 个还是取第10
万个元素,都是用key
精确查找哈希表的过程,其消耗时间大致相同。给定两个数组,写一个方法来计算它们的交集
空间换时间的思路是用个Hash表来存数组1的元素以及出现的个数(此处需要遍历n次,并存一个n级别的空间)。
遍历数组2,发现数组2里有Hash表里的值就存到Result数组里,并把Hash表内该值次数减一(为0之后就Delete)。如果不存在Hash表里,就跳过。这样时间复杂度就是(m+n)
另一个方法有两个数组m,n。遍历n的时候,判断值在不在m里,如果在,把m里的该值push到Result数组里,并将该值从m数组里删掉(用splice)。这样就是不用额外空间,但是提高了时间复杂度。
const intersect = (nums1, nums2) => { const map = {} const res = [] for (let n of nums1) { if (map[n]) { map[n]++ } else { map[n] = 1 } } for (let n of nums2) { if (map[n] > 0) { res.push(n) map[n]-- } } return res }复制代码
连续数值简化
请写一个函数,完成以下功能: 输入 '1, 2, 3, 5, 7, 8, 10' 输出 '1~3, 5, 7~8, 10' 输入描述 输入'1, 2, 3, 5, 7, 8, 10' 输出描述 输出'1~3, 5, 7~8, 10' 示例1 输入 1,2,3,5,7,8,10 输出 1~3,5,7~8,10复制代码
答案:
function transformStr(str) { let arr = str.split(',') let i = 0 let ret = [] for (let j = 1; j <= arr.length; j++) { if (arr[j] - arr[j - 1] !== 1) { ret.push(j - i === 1 ? arr[i] : `${arr[i]}~${arr[j - 1]}`) i = j } } return ret.join(',') } 或者 function simplifyStr(num) { var result = []; var temp = num[0] num.forEach((value, index) => { if (value + 1 !== num[index + 1]) { if (temp !== value) { result.push(`${temp}~${value}`) } else { result.push(`${value}`) } temp = num[index + 1] } }) return result; }复制代码
数据转换
function commonSearch(target, id, mode) { const staskOrQuene = [...target] do { const current = staskOrQuene[mode === 'dfs' ? 'pop' : 'shift']() if (current.children) { staskOrQuene.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id }))) } if (current.id === id) { return current } } while(staskOrQuene.length) return undefined } var aa = [ { id: 1, name: '广东省', children: [ { id: '11', name: '深圳市', children: [ { id: '111', name: '南山区' }, { id: '112', name: '福田区' } ] } ] } ] commonSearch(aa,112)复制代码
leetcode-cn.com/explore/int…
11.图
最基本知识点:
阶、度(出度、入度)
树、森林、环
有向图、无向图、完全有向图、完全无向图
连通图、连通分量
图的存储和表达方式:邻接矩阵、邻接链表
围绕图的算法:
图的遍历:深度优先、广度优先
环的检测:有向图、无向图
拓扑排序
最短路径算法
连通性相关算法
图的着色、旅行商问题等
必须掌握的知识点:
图的存储和表达方式:邻接矩阵、邻接链表
图的遍历:深度优先、广度优先
二部图的检测、树的检测、环的检测:有向图、无向图
拓扑排序
联合查找算法
最短路径
作者:kakayuii
链接:https://juejin.cn/post/6973183420516007973