1. Bit operation
 Shift left <<
 Shift right >>: can be used to take the middle value in the dichotomy algorithm , such as13>>1
2. Bitwise operation
 Bitwise and&: Every bit is 1, the result is 1
 Bitwise or: One of them is 1, the result is 1
 Bitwise exclusive or^: Every bit is different, the result is 1
3. Stack
 Features: Last In First Out (LIFO)
 The basic idea of the algorithm: Because data can only be pushed from the top of the stack and data can only be popped from the top of the stack, it can be implemented with a singly linked list. Because it only operates on the top element of the stack, borrowing the head of the singly linked list allows all operations to be completed in O(1) time
 Scenario: When solving the problem, only care about the last operation. After the last operation is processed, the previous operation can be found in O(1) time. For example, leecode20 questions (valid brackets), 739 questions (daily temperature)
 Use stacks to solve maze problems
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]//Current node if(curNode[0]==x2&&curNode[1]==y2){ //At the end for(P in stack){ console.log(p) } return true } //x,y four directions x1,y; x+1,y; x,y1; x,y+1 for(dir in dirs){ nextNode=dir(curNode[0],curNode[1]) //If the next node can go if(maze[nextNode[0][nextNode[1]]]==0){ stack.append(nextNode) maze[nextNode[0]][nextNode[1]]==2//2 means that you have passed break } } maza[nextNode[0][nextNode[1]]==2 stack.pop() }else{ console.log('No way') return false } } Copy code
4. Queue
 Features: Firstinfirstout (FIFO), view and add data at the end of the line, view and delete data at the head of the line
 Realization: use doublelinked list
 Scenario: When processing data in a certain order and the data is constantly changing, such as breadth first search .
The idea of breadthfirst search is: (1) Starting from a node, looking for all the points that can continue to go, continue to search until an exit is found (2) Use a queue to store the node currently under consideration
(1)
Circular queue: when the queue tail pointer
front==Maxsize+1, It will automatically go to 0 if it advances one more position
 The head of the team moves forward by 1:front=(front+1)% Maxsize
 The tail pointer advances by 1:rear=(rear+1)% Maxsize
 Team empty conditions:rear==front
 Team full conditions:(rear+1)% Maxsize==front
Queue(){ function init(self,size=100){ self.queue=[0,size.random()] self.size=size self.rear=0//Team tail pointer self.front=0//Head of the team pointer } 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 } } Copy code
(2) Doubleended queue:
 Can use a doubly linked list
 The head and tail ends of the queue can view, add and delete data in O(1) time
 Scenario: Realize a window or continuous interval whose length changes dynamically. Leecode239 title (maximum sliding window)
(3) Priority queue:
 Different from ordinary queues: ensure that the elements taken out each time are the highest priority in the queue, and the priority level can be customized
 The most commonly used scenario: Filter data in a certain order (or priority) from the chaotic data
 Essence: The structure of a binary heap, which is called Binary Heap in English, uses an array structure to realize a complete binary tree
 Features: the first element in the arrayarray[0]Has the highest priority
 Given a subscript
i, Then for the elementarray[i]In terms of The element index corresponding to the parent node is
(i1)/2 The element index corresponding to the left child node is
2*i+1 The element index corresponding to the child node on the right is
2*i+2 The priority of each element in the array must be higher than the child nodes on both sides of it
 Basic operation: filter up, filter down
 time complexity:O(logk)
 Initialize a heap of size n, the time complexity isO(n). Leetcode347 questions
5. Sort
The time complexity of bubble sort, selection sort, and insertion sort is O(n*n)
 Bubble sort : start from the first element and compare the size with the next index element. If the current element is large, swap positions and repeat the operation until the last element. Then the last element at this time is the largest number in the array. Repeat the above operations in the next round, but at this time the last element is already the largest number , so there is no need to compare the last element, just compare tolength2s position
 Time complexity is O(n*n)
//Use double loop to sort. The outer loop controls all rounds, and the inner loop represents each round of bubbling processing. The elements are compared first, and then the elements are exchanged. function sort(array){ let tmp = 0; for(let i = 0; i <array.length; i++){ for(let j = 0; j <array.lengthi1; 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); Copy code
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=i1 while(j>=0 && tmp<li[j]){//When these two conditions are met, it means that the card insertion position suitable for drawing has not been found li[j+1] =li[j] j=j1 } li[j+1]=tmp//When j<0 or tmp>li[j], insert the card into position j+1 } return li } Copy code
 Select sort : Traverse the array and set the index of the minimum value to 0. If the retrieved value is smaller than the current minimum value, replace the minimum value index. After the traversal is completed, exchange the value of the first element and the minimum value index. After the above operation, the first element is the minimum value in the array, and the above operation can be repeated from index 1 in the next traversal. such as:[3,38,5,47,36,26]
 Time complexity is O(n*n)
//Because each traversal can get the minimum value of the disordered area, the area where the exchanged value is located is the ordered area, and the remaining position is in the disordered area (using i as the dividing line) function select_sort(li){ for (var i in li.length1){ let min_loc = i//The position of the smallest element, first assume that it is the first place in the disordered area for(var j;j>=i+1 && j<li.length;j++){//The disordered area traverses the smallest element, and j starts from i+1 to reduce the number of comparisons between i and itself. if(li[j]<li[min_loc]){ min_loc=j } } li[i]=li[min_loc]//Swap the position of the first and smallest element in the disordered area li[min_loc]=li[i] } return li } Copy code
Merge sort, quick sort, heap sortthe time complexity of the three sorting algorithms is O(nlogn)
 In general, in terms of running time: quick sort <merge sort <heap sort
 The disadvantages of the three sorting algorithms:
 Quick sort: low sorting efficiency in extreme cases
 Merge sort: additional memory overhead is required
 Heap sort: relatively slow in fast sorting algorithms
 Merging and sorting : the array is first divided into multiple arrays of two elements, and then combined into a large array in order
 Time complexity is O(N*logN), space complexity is O(n)
 step
 Decomposition: Divide the list into smaller and smaller pieces, until it is divided into one element
 Termination condition: an element is ordered
 Merge: merge two ordered lists, the list is getting bigger and bigger
function merge(li,low,mid,high){ let i=low, j=mid+1 ltmp=[] while(i<=mid&&j<=high){//As long as there are numbers on both sides if(li[i]<=li[j]){ ltmp.append(li[i]) i+=1 }else{ ltmp.append(li[j]) j+=1 } } //After the while is executed, there must be a part that is not counted, and only one of the two while below will be executed 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) } } Copy code
 Fast sorting : first take out a reference value, place the value larger than the reference value on the right, and place the value smaller than the reference value on the left. After the comparison is completed, the reference value and the first value larger than the reference value are exchanged, and then the array is set to the reference value The position is divided into two parts, and the above operations are continued recursively .
The general time complexity of quick sort is nlogn, and the worst time complexity is n*n (when each recursion, only one more value of the ordered area can be added, that is, only one value can be sorted at a time)
function partition(li,left,right){ let tmp=li[left] while(left <right){ while(left<right && li[right]>=tmp){//Find the number smaller than tmp from the right right=1//Go one step to the left } li[left]=li[right]//Write the value on the right to the left space while(left<right && li[right]<=tmp){ left+=1 } li[right]=li[left]//Write the value on the left to the space on the right } li[left]=tmp//return tmp return left } function quick_sort(li,left,right){ if(left<right){//list has at least two elements mid=partition(li,left,right) quick_sort(li,left,mid1) quick_sort(li,mid+1,right) } } Copy code
 Heap sorting : first traverse the maximum value and put it at the beginning of the array, then swap the first and last positions of the array and reduce the length of the array by one, and then repeat the above operation to get a big root heap (all child nodes of a node have a value greater than He is small)
 Build heap
 Get the top element of the heap, which is the largest element
 Remove the top of the pile and put the last element of the pile on the top of the pile. At this time, you can adjust the pile again to order
 The top element is the second largest element
 Repeat step 3 until the heap becomes empty
The downward adjustment properties of the heap: 1. Assuming that the left and right subtrees of the root node are all heaps, but the root node does not satisfy the nature of the heap; 2. It can be turned into a heap through a downward adjustment. Time complexity
nlogn
//Create a big root heap function sift(data,low,high){ let i=low,//i initially points to the root node j=2*i+1,//j is the left child of the root node at the beginning tmp=data[i]//Save the top of the heap while(j<=high){//As long as there is a number at position j if(j<high&&data[j]<data[j+1]){//If there is a right child and is relatively large j+=1//j points to the right child } if(temp<data[j]){ data[i]=data[j] i=j//Look down one layer j=2*i+1 }else{//tmp is bigger, put tmp in the position of i break } } data[i]=tmp//Put tmp on the leaf node } function heap_sort(data){ let n=data.length for(let i in range(n/21,1,1)){ sift(data,i,n1)//i represents the subscript of the root of the adjusted part when building the heap } //The construction of the above part is completed for(let j in range(n1,1,1)){ //i points to the last element of the current heap data[0]=data[i] data[i]=data[0] sift(data,0,i1)//i1 is the new high } } Copy code
Extension: topK problem: now there are n numbers, the design algorithm gets the top k number (k<n) (such as Weibo hot search)
 Solutions
 Take the first k elements of the list to build a small root heap. The top of the heap is the current kth largest number
 Traverse the original list backwards in turn. For an element in the list, if it is less than the top of the heap, the element is ignored; if it is greater than the top of the heap, the top of the heap is replaced with this element, and the heap is adjusted once
 After traversing all the elements in the list, pop the top of the heap in reverse order
 Solution
 Slice after sorting O(nlogn)
 Bubble sort, selection sort, insertion sort O(kn)
 Heap sorting ideas O(nlogk)
 Slice after sorting
//Create a small root heap function sift(data,low,high){ let i=low,//i initially points to the root node j=2*i+1,//j is the left child of the root node at the beginning tmp=data[i]//Save the top of the heap while(j<=high){//As long as there is a number at position j if(j<high&&data[j]>data[j+1]){ j+=1//j points to the right child } if(temp>data[j]){ data[i]=data[j] i=j//Look down one layer j=2*i+1 }else{ break } } data[i]=tmp//Put tmp on the leaf node } function topk(li,k){ let heap=li[0,k] for(let i in range((k2/2),1,1)){ sift(heap,i,k1) } //1. Build a heap for(let i in range(k,li.length1)){ if(li[i]>heap[0]){ heap[0]=li[i] sift(heap,0,k1) } } //2. Traverse for(let i in range(k1,1,1)){ heap[0],heap[i]=heap[i],heap[0] sift(heap,0,i1) } //3. Out return heap } Copy code
6. Linked list
 A linked list is a collection of elements composed of a series of nodes. Each node contains two parts, the data fielditemAnd a pointer to the next nodenext. Through the mutual connection between the nodes, the series is finally connected into a linked list
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]) Copy code
 Create a linked list: first interpolation method, tail interpolation method
 Insertion and deletion of linked list nodes
 insert:
p.next=curNode.next curNode.next=p Copy code
 delete
p=curNode.next curNode.next=curNode.next.next del p Copy code
 Doublelinked list: each node of the doublelinked list has two pointers: one points to the next node, and the other points to the previous node
 Insertion of Double Linked List Node
p.next=curNode.next curNode.next.prior=p p.prior=curNode curNode.next=p Copy code
 Deletion of doubly linked list nodes
p=curNode.next curNode.next=p.next p.next.prior=curNode del p Copy code

Linked List and Sequence List
 Linked lists are significantly faster than sequential lists in insert and delete operations
 The memory of the linked list can be allocated more flexibly (try using the linked list to reallocate the stack and queue)
 The data structure of the chain storage of the linked list is very inspiring for the structure of the tree and graph.

What is the difference between an array and a linked list, and what are the characteristics of a linked list?
 Array statically allocates memory, and linked list dynamically allocates memory;
 The array is continuous in the memory, and the linked list is not continuous;
 The array elements are in the stack area, and the linked list elements are in the heap area;
 Arrays can be quickly located according to the subscript, the time complexity is O(1), and the time complexity of locating elements in the linked list is O(n) (because the pointer needs to be moved to access the elements in the linked list);
 The time complexity of inserting or deleting elements of the array is O(n) (because a large number of elements need to be moved), and the time complexity of the linked list is O(1) (because only the pointer needs to be modified).
Reference link: javascript implements linked list data structure and reverse single linked list method
function myReverse (linkedList) { //1 Get the head of the parameter list var head = linkedList.head //2 Boundary judgment If the head node is empty or there is only one node, then what else is it reversed? if(head === null  head.next === null) return linkedList //3 uses three pointers var current = head var pre = null var next = null #Judge whether the current node is empty #If it is not empty, get the next node of the current node first #Then set the next of the current node to the previous node #Then set current to the next node and pre to the current node while(current != null) { next = current.next current.next = pre pre = current current = next } linkedList.head = pre } Copy code
Extension: Get the kth node from the bottom of the linked list, the intermediate node of the linked list and determine whether the linked list has a ring blog.csdn.net/qq_40608516...
7. Tree
 A tree is a data structure, such as: directory structure
 A tree is a data structure that can be defined recursively
 A tree is a collection of n nodes: if n=0, then this is an empty tree; if n>0, then there is 1 node as the root node of the tree, and other nodes can be divided into m sets, each The collection itself is a tree
 The degree of the tree: the maximum number of forks of a node in the tree is the degree of the tree
 Commonness of the tree: intuitive structure, through the tree problem to examine the proficiency of the recursive algorithm
 The shapes of trees often tested in interviews are: ordinary binary tree, balanced binary tree, complete binary tree, binary search tree, quad tree, multibranch tree
Special trees: redblack trees, selfbalancing binary search trees
(1) Binary tree
First understand what a binary tree is
 Binary tree
 Binary tree: a tree whose degree does not exceed 2
 Each node has at most two child nodes
 The two child nodes are divided into left child nodes and right child nodes
 Full binary tree: a binary tree, if the node tree of each layer reaches the maximum value, the binary tree is a full binary tree
 Complete binary tree: a binary tree where leaf nodes can only appear in the lowermost layer and the next lower layer, and the nodes of the lowermost layer are concentrated in the leftmost positions of the layer.
 Big root heap: a complete binary tree, satisfying that any node is larger than the other child nodes
 Small root heap: a complete binary tree, satisfying that any node is smaller than its child node
The storage mode of the binary tree (representation mode)
 Chained storage method: Define the node of the binary tree as an object, and the nodes are connected by a link method similar to a linked list
 Sequential storage method (using list)
Preorder, middleorder, and postorder traversal of binary tree
 Preorder traversal means visiting the root node first, then the left node, and finally the right node: application scenario (search in the tree or create a new tree)
 Inorder traversal means visiting the left node first, then the root node, and finally the right node: application scenario (binary search tree: the root node is larger than the left and smaller than the right, generally no duplicate values appear), leetcode question 230
 Postorder traversal means visiting the left node first, then the right node, and finally the root node: such as leetcode250
Specific introduction reference: Binary tree traversal (preorder, middleorder, postorder)
The predecessor and successor nodes of the middleorder traversal:
Predecessor node: it is the relative previous successor node in the middleorder traversal sorting: it is the relatively last node in the middleorder traversal sort
Tree depth
(2) Prefix tree (also known as dictionary tree): This data structure is widely used in dictionary lookups
What is a dictionary lookup? For example/; Given a series of strings that make up a dictionary, it is required to find all strings starting with "ABC" in the dictionary

 Method 1: Brute force search method
Time complexity: O(M*N) starts with length M
 Method two: prefix tree
Time complexity: O(M)
 Application scenarios:
 Enter the search text in the search box and list the related searches starting with the search term
 Chinese Pinyin Input Method
 Important properties:
 Each node contains at least two basic attributes
 children: array or collection, listing all the characters contained in each branch
 isEnd: Boolean value, indicating whether the node is the end of a string
 The root node is empty
 Except for the root node, all other nodes may be the end of a word, and the leaf nodes must be the end of a word
4. The most basic operation
 Created by
 Traverse the input string once, and traverse the characters of each string
 Starting from the root node of the prefix tree, add each character to the node s children character set
 If the character set already contains this character, skip
 If the current character is the last of the string, mark the isEnd of the current node as true
 Search by
 Starting from the root node of the prefix tree, match the entered prefix characters one by one
 If encountered, continue to search for the next level
 If not encountered, return immediately
Leetcode212 questions (the depthfirst algorithm can be used)
(3) Line segment tree
Suppose you find the sum (or average) of the elements in any interval of the array
 Method 1: Traverse the array once: the time complexity is O(n)
 Method 2: Line segment tree: time complexity is O(logn)depends on the height of the tree
What is a segment tree? A structure that stores data in the form of a binary tree. Each node stores the sum of a certain segment in the array. For example
(4) Tree array
8. Recursion and backtracking
 Recursion: Topdown leetcode 247 questions (center symmetric tree)
 Backtracking: Leetcode 39 questions (combination sum)
Can be used in the following algorithms:
 Definition and traversal of binary tree
 Merge sort, quick sort
 Dynamic programming
 Binary search
Extension 1: What are the advantages and disadvantages of recursion
Advantages: The code is concise. Easy to understand
Disadvantages:
 The time and space consumption is relatively large:
Recursion is because the function calls itself, and the function call consumes time and space. Every function call needs to allocate space in the memory stack to save parameters, return values and temporary variables. It also takes time to push and pop data into the stack, which reduces efficiency.
 Repeated calculation:
Many calculations in recursion are repeated. The essence of recursion is to decompose a problem into two or more problems, and multiple problems have overlapping parts, that is, there are repeated calculations. Such as the recursive realization of the Fibonacci sequence.
 Stack overflow:
Recursion may have a stack overflow, and space will be allocated in the memory stack every time it is called. The capacity of the stack space is limited. When the number of calls is too many, the capacity of the stack may be exceeded, causing the call stack to overflow
Extension 2: Find the number of occurrences of a certain number from the ordered array:
 Binary search
 Direct comparison
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; } Copy code
9. Dynamic programming
There are three important concepts in dynamic programming:
 Optimal substructure
 boundary
 State transition formula
The essence of dynamic programming is actually two points: 1. Decompose the subproblems from the bottom up 2. Store the calculated solutions through variables
 The dynamic programming idea of Fibonacci sequence:
 The Fibonacci sequence starts from 0 and 1, then this is the bottom of this subproblem
 Store the value of the Fibonacci sequence corresponding to each bit through an array
 01 knapsack problem: refer to the algorithm problem of dynamic programming01 knapsack problem
10.Hash table
Hash table is a data structure that uses a hash function to calculate the storage location of the data. It usually supports the following operations:
 insert(key, value): Insert keyvalue pair (key, value)
 get(key): If there is a keyvalue pair whose key is key, return its value, otherwise return a null value
 delete(key): delete the keyvalue pair whose key is key
 There are 100,000 data in the array. What is the time difference between the first element and the 100,000th element?
JavaScriptThere is no real array, all arrays are actually objects, and their "indexes" look like numbers, but they are actually converted into strings as the property name (the object'skey) To use. So whether it is the first or the first1010.thousand elements are usedkeyThe process of accurately looking up the hash table takes approximately the same time.
 Given two arrays, write a method to calculate their intersection
The idea of changing space for time is to use a Hash table to store the elements of array 1 and the number of occurrences (here you need to traverse n times, and store an nlevel space).
Traverse array 2 and find that there is a value in the Hash table in array 2 and store it in the Result array, and reduce the number of times the value in the Hash table by one (delete after 0). If it does not exist in the Hash table, skip it. So the time complexity is (m+n)
Another method has two arrays m and n. When traversing n, determine whether the value is in m. If it is, push the value in m into the Result array, and delete the value from the m array (using splice). In this way, no additional space is needed, but the time complexity is increased.
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 } Copy code
 Continuous numerical simplification
Please write a function to complete the following functions: Input '1, 2, 3, 5, 7, 8, 10' Output '1~3, 5, 7~8, 10' Enter description Enter '1, 2, 3, 5, 7, 8, 10' Output description Output '1~3, 5, 7~8, 10' Example 1 enter 1,2,3,5,7,8,10 Output 1~3,5,7~8,10 Copy code
answer:
function transformStr(str) { let arr = str.split(',') let i = 0 let ret = [] for (let j = 1; j <= arr.length; j++) { if (arr[j]arr[j1] !== 1) { ret.push(ji === 1? arr[i]: `${arr[i]}~${arr[j1]}`) i = j } } return ret.join(',') } or 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; } Copy code
 Data conversion
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:'Guangdong Province', children: [ { id: '11', name:'Shenzhen', children: [ { id: '111', name:'Nanshan District' }, { id: '112', name:'Futian District' } ] } ] } ] commonSearch(aa,112) Copy code
leetcodecn.com/explore/int...
11. Figure
The most basic knowledge points:
 Degree, degree (out degree, in degree)
 Tree, forest, ring
 Directed graph, undirected graph, fully directed graph, completely undirected graph
 Connected graph, connected component
 Graph storage and expression: adjacency matrix, adjacency linked list
Algorithms around the graph:
 Graph traversal: depth first, breadth first
 Ring detection: directed graph, undirected graph
 Topological sort
 Shortest path algorithm
 Connectivity related algorithms
 Coloring of graphs, traveling salesman problem, etc.
Knowledge points that must be mastered:
 Graph storage and expression: adjacency matrix, adjacency linked list
 Graph traversal : depth first, breadth first
 Bipartite graph detection, tree detection, ring detection: directed graph, undirected graph
 Topological sort
 Joint search algorithm
 Shortest path