Data structure study notes

Data structure study notes

1. Bit operation

  • Shift left <<
  • Shift right >>: can be used to take the middle value in the dichotomy algorithm , such as

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 x-1,y; x+1,y; x,y-1; 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: First-in-first-out (FIFO), view and add data at the end of the line, view and delete data at the head of the line
  • Realization: use double-linked list
  • Scenario: When processing data in a certain order and the data is constantly changing, such as breadth first search .

The idea of breadth-first 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


Queue implementation mode-circular queue

Circular queue: when the queue tail pointer

, 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:
  • 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) Double-ended 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 array
    Has the highest priority
  • Given a subscript
    , Then for the element
    In terms of
  • The element index corresponding to the parent node is
  • The element index corresponding to the left child node is
  • The element index corresponding to the child node on the right is
  • 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:
  • Initialize a heap of size n, the time complexity is
    . Leetcode347 questions

5. Sort

The time complexity of bubble sort, selection sort, and insertion sort is O(n*n)

  1. 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 to
    s 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.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); 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);
  1. [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]){//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=j-1 } li[j+1]=tmp//When j<0 or tmp>li[j], insert the card into position j+1 } return li } Copy code
  1. 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:
    • 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.length-1){ 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 sort-the 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:
    1. Quick sort: low sorting efficiency in extreme cases
    2. Merge sort: additional memory overhead is required
    3. Heap sort: relatively slow in fast sorting algorithms
  1. 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
      1. Decomposition: Divide the list into smaller and smaller pieces, until it is divided into one element
      2. Termination condition: an element is ordered
      3. 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
  2. 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,mid-1) quick_sort(li,mid+1,right) } } Copy code
  1. 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


//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/2-1,-1,-1)){ sift(data,i,n-1)//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(n-1,-1,-1)){ //i points to the last element of the current heap data[0]=data[i] data[i]=data[0] sift(data,0,i-1)//i-1 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
    1. Take the first k elements of the list to build a small root heap. The top of the heap is the current k-th largest number
    2. 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
    3. After traversing all the elements in the list, pop the top of the heap in reverse order
  • Solution
    1. Slice after sorting
    2. Bubble sort, selection sort, insertion sort
    3. Heap sorting ideas
//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((k-2/2),-1,-1)){ sift(heap,i,k-1) } //1. Build a heap for(let i in range(k,li.length-1)){ if(li[i]>heap[0]){ heap[0]=li[i] sift(heap,0,k-1) } } //2. Traverse for(let i in range(k-1,-1,-1)){ heap[0],heap[i]=heap[i],heap[0] sift(heap,0,i-1) } //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 field
    And a pointer to the next node
    . 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 } } function create_linklist(li){ let head=Node(li[0]) for(element in li){ node=Node(element) head=node } return head } function create_linklist_tail(li){ let head=Node(li[0]), tail=head for(element in li){ node=Node(element) 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: Copy code

  • delete del p Copy code

  • Double-linked list: each node of the double-linked 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.prior=curNode Copy code

  • Deletion of doubly linked list nodes 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 || === 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 = = 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

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, multi-branch tree

Special trees: red-black trees, self-balancing binary search trees

(1) Binary tree

First understand what a binary tree is

  1. 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
  2. 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
  3. 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)

  1. 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
  2. Sequential storage method (using list)

Pre-order, middle-order, and post-order traversal of binary tree

  • Pre-order 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)
  • In-order 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
  • Post-order 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 (pre-order, middle-order, post-order)

The predecessor and successor nodes of the middle-order traversal:

Predecessor node: it is the relative previous successor node in the middle-order traversal sorting: it is the relatively last node in the middle-order 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)

  1. Application scenarios:
  • Enter the search text in the search box and list the related searches starting with the search term
  • Chinese Pinyin Input Method
  1. 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 depth-first 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: Top-down 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


  1. 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.

  1. 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.

  1. 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 sub-problems 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 sub-problem
    • Store the value of the Fibonacci sequence corresponding to each bit through an array
  • 0-1 knapsack problem: refer to the algorithm problem of dynamic programming-01 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 key-value pair (key, value)
  • get(key): If there is a key-value pair whose key is key, return its value, otherwise return a null value
  • delete(key): delete the key-value pair whose key is key
  1. There are 100,000 data in the array. What is the time difference between the first element and the 100,000th element?

    There 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's
    ) To use. So whether it is the first or the first
    10.thousand elements are used
    The process of accurately looking up the hash table takes approximately the same time.

  2. 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 n-level 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
  1. 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


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(',') } 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
  1. Data conversion
function commonSearch(target, id, mode) { const staskOrQuene = [] do { const current = staskOrQuene[mode ==='dfs'?'pop':'shift']() if (current.children) { staskOrQuene.push( => ({ ...x, path: (current.path || +'-' + }))) } if ( === 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

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