This article introduces the basics of data structures and algorithms, covering the logical structure of data (linear and nonlinear structures), storage structures (sequential storage, linked storage, indexed storage, hash storage), as well as the basic concepts and efficiency measurement methods of algorithms. It also discusses in detail the sequential and linked representations of linear lists (including singly linked lists, doubly linked lists, circular linked lists, and static linked lists) and the sequential and linked storage structures of stacks.

Introduction

Logical Structure of Data

The logical structure of data refers to the relationships between data elements, i.e., describing data from a logical perspective. It is independent of data storage and is computer-independent.

• Linear Structure
  • Linear List
    • Array
    • Stack
    • Queue
• Non-linear structure
  • Set
  • Tree structure
    • General tree
    • Binary tree
  • Graph structure
    • Directed graph
    • Undirected graph

Storage structure of data

Storage structure refers to the representation of data structures in a computer, also known as physical structure

• Sequential storage

Sequential storage means storing logically adjacent elements in storage units that are also physically adjacent;

• Linked storage

Linked storage uses pointers indicating the storage addresses of elements to represent the logical relationships between elements.

• Index storage

Index storage refers to establishing an additional index table while storing element information. Each entry in the index table is called an index item, and the general form of an index item is (key, address).

• Hash storage

Hash storage directly calculates the storage address of an element based on its key, also known as hash storage.

Basic concepts of algorithms

• Finiteness

Finiteness means that an algorithm must always terminate after a finite number of steps, and each step must be completed within finite time.

• Definiteness

Definiteness means that each instruction in an algorithm must have an unambiguous meaning, and for the same input, it must produce the same output.

• Feasibility

Feasibility means that the operations described in an algorithm can be implemented by executing already implemented basic operations a finite number of times.

• Input

Input means that an algorithm has zero or more inputs, which are taken from a specific set of objects.

• Output

Output means that an algorithm has one or more outputs, which are quantities that have a specific relationship with the inputs.

Measurement of algorithm efficiency

Time complexity

$$T(n) = O(f(n))$$

Addition rule:

$$T(n) = T_1(n)+T_2(n)=O(f(n)) + O(g(n)) = O(max(f(n),g(n)))$$

Common asymptotic time complexities

$$O(1) < O(log_2^n) < O(n) < O(nlog^n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$

Space complexity

$$S(n) = O(g(n))$$

Data structure

Linear list

Definition: A linear list is a finite sequence ofthe same data typen (n>=0) data elements.

A linear list is generally represented as:

$$L = (a_1,a_2,a_3,...,a_i,a_{i+1}, ..., a_n)$$

Sequential representation of a linear list

The sequential storage of a linear list is also called a sequential list, characterized by the logical order of elements being the same as their physical order. A linear list is aRandom AccessStorage Structure

• C Language Description

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// Static Allocation
#define MAX_SIZE 50
typedef struct{
  ElemType data[MaxSize];
  int length;
}SqList;

// Dynamic Allocation
#define InitSize 100
typedef struct{
    ElemType *data;
    int capacity;
    int length;
}SeqList;

• C++ Description

Generally use the standard library vector, or you can customize it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

template <typename T>
class LinearList {
private:
    T *data;  
    int length;
    int capacity;

    void resize(size_t new_capacity) {
        T* new_data = new T[new_capacity];
        for (size_t i = 0; i < size; i++) {
            new_data[i] = data[i];
        }
        delete[] data;
        data = new_data;
        capacity = new_capacity;
    }

public:
    SeqList() : data(nullptr), size(0), capacity(0) {}

    ~SeqList() {
        delete[] data;
    }
};

• Rust Description

In Rust, generally use the standard library Vec; writing your own requires many unsafe APIs

Basic Operation Time Complexity

Linked representation of linear list

Singly linked list

The linked storage of linear list is also called singly linked list.

• C language description

1
2
3
4

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

The effect of this C language definition is

• C++ description

TODO

• Rust description

TODO

head node

usually usehead pointerto identify a singly linked list; when the head pointer is NULL, it indicates an empty list. Additionally, for operational convenience, a node is added before the first node of the singly linked list, calledhead node。

• the data field of the head node can be left empty or can store information such as the length of the list.

• introducing a head node brings two advantages:

  • since the position of the first data node is stored in the pointer field of the head node, operations at the first position of the linked list are consistent with those at other positions, requiring no special handling
  • regardless of whether the linked list is empty, its head pointer always points to the head node as a non-null pointer (in an empty list, the pointer field of the head node is NULL), thus unifying the handling of empty and non-empty lists.

creating a singly linked list using head insertion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

typedef struct LNode {
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;

// creating a singly linked list using head insertion
LinkList LinkListInit_HeadInsert(void) {
  LinkList L;
  LNode *node;
  int x;

  L = (LNode *)malloc(sizeof(LNode));
  L->next = NULL;

  while (scanf("%d", &x) != EOF) {
    node = (LNode *)malloc(sizeof(LNode));
    node->data = x;
    node->next = L->next;
    L->next = node;
  }
  return L;
}

creating a singly linked list using tail insertion

TODO

doubly linked list

in a singly linked list, there is only one pointer to the successor, allowing traversal only sequentially from the head node. In a doubly linked list, each node has two pointers, prior and next, pointing to the predecessor and successor nodes respectively.

• C language description

1
2
3
4

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinkList;

• C++ description

TODO

• Rust description

TODO

Circular Linked List

Circular Singly Linked List

The difference between a circular singly linked list and a singly linked list is that the pointer of the last node in the list is not NULL, but instead points to the head node, thus forming a ring.

• C Language Description

• C++ Description

• Rust Description

Circular Doubly Linked List

Compared to a circular singly linked list, the prior pointer of the head node in a circular doubly linked list points to the tail node.

• C Language Description

• C++ Description

• Rust Description

Static Linked List

A static linked list uses an array to describe the chained storage structure of a linear list. Nodes also have a data field and a pointer field next. Unlike the pointers in previous linked lists, the pointer here is the relative address (array index) of the node, also known as a cursor. Similar to a sequential list, a static linked list also requires pre-allocating a contiguous block of memory address space.

For example:

1
2
3
4
5
6
7
8
9
10

主链表部分：
┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐
│ idx=1│ data │ next │ ---> │ idx=2│  10  │ next │ ---> │ idx=3│  20  │ next │ ---> [idx=5│ 30 │ -1│]
└──────┴──────┴──────┘      └──────┴──────┴──────┘      └──────┴──────┴──────┘

空闲链表部分：
┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐
│ idx=0│  —   │  4   │ ---> │ idx=4│  —   │  6   │ ---> [idx=6│ — │ -1│]
└──────┴──────┴──────┘      └──────┴──────┴──────┘

C language description

1
2
3
4
5

#define MaxSize 50
typedef struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];

C++ description

Rust description

stack

stack (Stack)is only alloweda linear list that allows insertion or deletion only at one end。

• **top of stack (Top)**the end of the linear list where insertion and deletion are allowed
• **bottom of stack (Bottom)**fixed. The other end where insertion and deletion are not allowed

the characteristics of the stack can be clearly summarized asLast In First Out (LIFO)

mathematical properties of the stack:

The number of possible pop sequences for n distinct elements pushed onto a stack is the nth Catalan number.

The formula is:

$$C_n = \frac{1}{n+1} C_{2n}^n = \frac{(2n)!}{n! (n+1)!}$$

Sequential storage structure of a stack

• C language description

1
2
3
4
5
6

#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
    // Stack top pointer
	int top;
}SqStack;

• C++ description

TODO

• Rust description

TODO

Shared stack

By utilizing the property that the bottom positions of stacks are relatively fixed, two sequential stacks can share a one-dimensional array space, with the bottoms of the two stacks set at opposite ends of the shared space, and the tops extending toward the middle.

1
2
3
4
5
6
7
8
9

下标:   0   1   2   3   4   5   6   7   8   9
        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
Stack1→ │10 │20 │30 │   │   │   │   │   │40 │50 │ ←Stack2
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
         ↑                   ↑                   ↑
       base1                mid                base2
         ↑                                       ↑
       top1=2                               top2=8

The shared stack is designed to utilize address space more efficiently. Stack overflow occurs if and only if the two stacks are adjacent.

Linked storage structure of a stack

A stack using linked storage is called alinked stack，Linked stackadvantages

• Facilitates multiple stacks sharing storage space and improving efficiency
• No stack overflow situation exists

Linked stacks are typically implemented using a singly linked list, with all operations performed at the head of the list.

• C language description

Here it is specified that the linked stack has no head node

1
2
3
4

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}*LiStack;

• C++ description

TODO

• Rust description

TODO

Classic applications

Bracket matching

Expression evaluation

Converting recursion to stack implementation

Queue

QueueIt is also a linear list with restricted operations, allowing insertion only at one end and deletion only at the other end.

• FrontThe end that allows deletion, also known asFront

• RearThe end that allows insertion

• EnQueueInsert an element at the rear

• DeQueueDelete an element from the front

The characteristics of a queue can be simply summarized asFirst In First Out (FIFO)

Sequential storage structure of a queue

• C language description

1
2
3
4
5

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

• C++ description

TODO

• Rust description

Check if the queue is empty

Q.rear == Q.front==0

Determine if the queue is full

Because:

• Enqueue operation: when the queue is not full, first assign the value to the tail element, then increment the tail pointer by 1
• Dequeue operation: when the queue is not empty, first retrieve the head element value, then increment the head pointer by 1

Therefore, it is not possible to use “Q.rear==MaxSize” as the condition for a full queue; the entire problem is solved using a circular queue

Circular queue

The sequential queue is conceived as a circular space, that is, the table storing queue elements is logically regarded as a ring, calledcircular queue

• When the head pointerQ.front == MaxSize -1after that, advance one more position to 0

• Initialization:Q.front = Q.rear = 0

• Head pointer increments by 1:Q.front = (Q.front + 1) % MaxSize

• Tail pointer increments by 1:Q.rear = (Q.rear + 1) % MaxSize

• Three ways to determine if the queue is full

  • Sacrificing one unit to distinguish between empty and full queues, using one less queue unit when enqueuing, is a common practice. The convention is to treat ‘the front pointer being at the next position of the rear pointer as the full queue flag’.

    • Full queue condition : (Q.rear + 1) % MaxSize == Q.front
    • Empty queue condition: (Q.front == Q.rear)
    • Number of elements in the queue: (Q.rear - Q.front + MaxSize) % MaxSize

  • Add a data member to represent the number of elementssize, so that both empty and full queue conditions haveQ.rear == Q.front

    • Full queue condition : Q.size == MaxSize
    • Empty queue condition: Q.size = 0
    • Number of elements in the queue: size

  • Addtagdata member. When tag is 0, it indicates that a deletion was performed most recently; when tag is 1, it indicates that an insertion was performed most recently.

    • Full queue condition: Whentagequals 0, if due to deletionQ.front == Q.rearthen the queue is empty;
    • Queue empty condition: Whentagequals 1, due to insertionQ.front == Q.rearthen the queue is full;
    • Number of elements in the queue

    $$\text{队列中元素个数} = \begin{cases} 0, & \text{if } (front == rear \text{ and } tag == 0) \\ MaxSize, & \text{if } (front == rear \text{ and } tag == 1) \\ (rear - front + MaxSize) \% MaxSize, & \text{otherwise} \end{cases}$$

Linked storage structure of queue

Usually, a linked queue is designed as asingly linked list with a head node.

• C language description

1
2
3
4
5
6
7
8

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}*LinkQueue;

• C++ description

TODO

• Rust description

TODO

Deque

A deque is a queue that allows enqueue and dequeue operations at both ends. The two ends of the queue are called the front and the rear.

Input-restricted deque

Insertion and deletion are allowed at one end, but only insertion is allowed at the other end.

Output-restricted deque

Insertion and deletion are allowed at one end, but only deletion is allowed at the other end.

Priority queue (heap)

A heap is a one-dimensional array maintained using the structure of a complete binary tree.

Heaps can be divided intomax heapandmin heap。

• Max heap: The value of each node is greater than or equal to the values of its left and right child nodes.

• Min heap: The value of each node is less than or equal to the values of its left and right child nodes.

Taking the max heap as an example:

The construction process of a max heap starts from the last non-leaf node and adjusts from bottom to top.

When using an array to represent the sequence to be sorted, the position of the last non-leaf node is:Array length / 2 - 1

Compare the value of the current node with that of the left subtree. If the current node is smaller than the left subtree, swap the current node and the left subtree; after swapping, check whether the left subtree still satisfies the max-heap property, and if not, readjust the subtree structure.

Then compare the value of the current node with that of the right subtree. If the current node is smaller than the right subtree, swap the current node and the right subtree; after swapping, check whether the right subtree still satisfies the max-heap property, and if not, readjust the subtree structure.

When no swapping or adjustment is needed, the max-heap construction is complete.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <vector>
using std::vector;

void heapify(vector<int> &vec, int curr, int n)
{
        int left = curr * 2 + 1;
        int right = curr * 2 + 2;
        int largest = curr;

        if (left < n && vec[left] > vec[largest]) {
                largest = left;
        }

        if (right < n && vec[right] > vec[largest]) {
                largest = right;
        }

        if (largest != curr) {
                std::swap(vec[largest], vec[curr]);
                //Since the parent node and child node have been swapped, it may affect the subtree of the child node, so the subtree of the child node needs to be adjusted.
                heapify(vec, largest, n);
        }
}

void buildMaxHeap(vector<int> &vec)
{
        int n = vec.size();
        // The position of the last node is n-1, so the position of the parent node is (n-1-1)/2.
        for (int i = (n - 2) / 2; i >= 0; i--) {
                heapify(vec, i, n);
        }
}

#include <stdio.h>

int main()
{
        vector<int> nums = { 9, 8, 2, 1, 5, 3, 0, 10, 22, 5 };
        int n = nums.size();
        buildMaxHeap(nums);

        for (int i = 0; i < n; i++) {
                // pop
                std::swap(nums[0], nums[n - i - 1]);
                heapify(nums, 0, n - i - 1); // Heap length is n-i-1
        }
        // Output the sorted array
        for (int i = 0; i < n; i++)
                printf("%d ", nums[i]);
        printf("\n");
}

Classic applications

Level-order traversal

Arrays and special matrices

Array

Most languages provide an array data type.

Compression of special matrices

Symmetric Matrix

• Property: Matrix$A = [a_{ij}]$satisfies$a_{ij} = a_{ji}$。
• Compression method: Only store theupper or lower triangular part, for example, store the elements of the upper triangle (including the diagonal).

If the matrix is$n \times n$, store the upper triangle row by row:

$$\text{存储顺序： } a_{11}, a_{12}, \dots, a_{1n}, a_{22}, a_{23}, \dots, a_{2n}, \dots, a_{nn}$$

• Index mapping formula(stored in a one-dimensional arrayB[k]）：

$$k = \frac{i(i-1)}{2} + j - 1 \quad (i \le j)$$

where$i, j$starts counting from 1.

• Storage space：$\frac{n(n+1)}{2}$elements.

Triangular Matrix

• Properties：
  • Upper triangular matrix: all elements$a_{ij} = 0$when$i > j$
  • Lower triangular matrix: all elements$a_{ij} = 0$when$i < j$
• Compression method: store only the non-zero triangular part.

Row-major storage formula for upper triangular matrix:

$$k = \frac{i(i-1)}{2} + j - 1 \quad (i \le j)$$

Row-major storage formula for lower triangular matrix:

$$k = \frac{i(2n-i+1)}{2} + (j-i) \quad (i \ge j)$$

• Storage space：$\frac{n(n+1)}{2}$elements.

Tridiagonal / Banded Matrix

• Properties: The matrix has non-zero elements only on the main diagonal, super-diagonal, and sub-diagonal, with the rest being 0.

$$A = \begin{bmatrix} a_1 & b_1 & 0 & \dots & 0 \\ c_1 & a_2 & b_2 & \dots & 0 \\ 0 & c_2 & a_3 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & b_{n-1} \\ 0 & 0 & 0 & c_{n-1} & a_n \end{bmatrix}$$

• Compression method: Store three one-dimensional arrays:
  • A[1..n]stores the main diagonal$a_i$
  • B[1..n-1]stores the super-diagonal$b_i$
  • C[1..n-1]stores the sub-diagonal$c_i$
• Access formula：

$$a_{i,i} = A[i], \quad a_{i,i+1} = B[i], \quad a_{i+1,i} = C[i]$$

• Storage space：$3n - 2$elements, compared to a regular$n^2$significantly saves space.

Sparse matrix

The number of non-zero elements t in the matrix is very small relative to the total number of matrix elements s, i.e.,$s \gg t$matrix is called asparse matrix。

Storing a sparse matrix using conventional methods is quite wasteful of space, so only the non-zero elements are stored. However, the distribution of non-zero elements is usually very irregular, so the row and column of each non-zero element must also be stored.

Therefore, the non-zero elements along with their corresponding rows and columns form a triple.

$$(\text 行标, 列标, 值)$$

Then store this triple according to a certain rule.After compressed storage, the sparse matrix loses the characteristic of random access.。

The triple of a sparse matrix can be stored usingarray storage,or it can usethe orthogonal linked list methodfor storage.

Triple sequential list (array storage)

• Store the non-zero elements in a sparse matrix as triples in row-major or column-major order.(行标, 列标, 值)。
• Common orders:
  • Row-major: Store by rows from top to bottom, and within each row from left to right.
  • Column-major: Store by columns from left to right, and within each column from top to bottom.
• Suitable for cases where non-zero elements of the matrix are not frequently modified.

Cross Linked List / Orthogonal List storage

• More suitable for dynamically modified sparse matrices.
• Each non-zero element node contains:
  • Value
  • Row index
  • Column index
  • Row pointer (points to the next non-zero element in the same row)
  • Column pointer (points to the next non-zero element in the same column)
• Enables fast traversal of rows and columns, suitable for operations like matrix multiplication and transposition.

Disjoint Set Union (DSU)

Disjoint Set Union，DSU / Union-Find

Disjoint Set Union is adata structure that dynamically maintains several disjoint setsand supports two main operations:

Data Structure Definition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <vector>
#include <algorithm>

using std::vector;

class DSU {
    public:
	vector<int> parent; // Parent Node of Each Node
	vector<int> rank; // (Optional) Used for Union by Rank or Recording Set Size

	DSU(int n)
	{
		parent.resize(n);
		rank.resize(n, 0);
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
	}

	int find(int x)
	{
		// Path Compression, Making Find Complexity Close to O(1)
		if (parent[x] != x) {
			parent[x] = find(parent[x]);
		}
		return parent[x];
	}

	void join(int x, int y)
	{
		// Union by Rank
		int rootX = find(x);
		int rootY = find(y);
		if (rootX == rootY) {
			return;
		}

		if (rank[rootX] < rank[rootY]) { //The Larger Rank of the Two Sets Becomes rootX
			std::swap(rootX, rootY);
		}

		parent[rootY] = rootX;//The Set with Smaller Rank is Attached Under the One with Larger Rank

		if (rank[rootX] == rank[rootY]) { //If the Ranks of Two Sets Are Equal, the Rank of the Merged Set Increases by 1
			rank[rootX]++;
		}
	}

	bool connected(int x, int y)
	{
		return find(x) == find(y);
	}
};

Tip:

Time Complexity

Strictly speaking, it is O(α(n)), but α(n) ≤ 5 for any practical size of n.

String

String pattern matching

The positioning operation of a substring is usually called stringpattern matching, which finds the position of a substring (usually called the pattern string) in the main string.

Naive pattern matching algorithm

Pattern stringpand main strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

S: a b a b c a b c a c b a b
P: a b c a c
   ↑ 从这里开始和主串对齐

步骤1：
S: a b a b c a b c a c b a b
P: a b c a c
   a = a ✅
     b ≠ a ❌ 失配 → 模式右移一位

步骤2：
S: a b a b c a b c a c b a b
  P: a b c a c
     a ≠ b ❌ → 继续右移一位

步骤3：
S: a b a b c a b c a c b a b
    P: a b c a c
       a = a ✅
         b = b ✅
           c = a ❌ → 右移一位

步骤4：
S: a b a b c a b c a c b a b
      P: a b c a c
         b ≠ a ❌ → 右移一位

步骤5：
S: a b a b c a b c a c b a b
        P: a b c a c
           c = a ❌ → 右移一位

步骤6：
S: a b a b c a b c a c b a b
          P: a b c a c
             a = a ✅
               b = b ✅
                 c = c ✅
                   a = a ✅
                     c = c ✅ ✅ 匹配成功！

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>
#include <string.h>

int naive_match(const char *s, const char *p) {
    int i=0,j=0;
    int s_len = strlen(s);
    int p_len = strlen(p);

	while(i<s_len && j<p_len){
        if(s[i]==p[j]){
            i++;
            j++;
        }else{
            i = i - j + 1;//Go back and rematch
            j = 0;
        }
    }
    if(j == p_len){
        return i - j;
    }
    return -1; 
}

Worst case：$O(n \cdot m)$, where$n$is the length of the main string,$m$is the length of the pattern string.

• For example, the main string"aaaaaaab"and the pattern string"aaaab", each match failure requires backtracking multiple characters.

Average case: usually less than the worst case, but may still approach$O(n \cdot m)$。

KMP algorithm

Recommended excellent explanatory article:

Thorough understanding from start to finishKMP

https://www.cnblogs.com/JoBlg/p/4087230.html?tdsourcetag=s_pctim_aiomsg

In the naive pattern matching algorithm, each match failure shifts the pattern string (the substring to be matched) one position to the right and starts comparing from the beginning.

Several concepts:

• Prefix: all substrings that include the first character but not the last character
• Suffix: All substrings that include the last letter but not the first letter
• **PM(Partial Match)**Partial match values, i.e., the table below

Below, take “ABCDABD” as the substring to be matched as an example:

Then the PM table is

• Given the text string “BBC ABCDAB ABCDABCDABDE” and the pattern string “ABCDABD”, now match the pattern string against the text string as shown in the figure below:

• 1. Since character A in the pattern string does not match characters B, B, C, and space in the text string from the start, there is no need to consider the conclusion; simply shift the pattern string right by one position repeatedly until character A in the pattern string matches the 5th character A in the text string:

• 2. Continue matching forward. When the last character D of the pattern string mismatches during matching with the text string, it is obvious that the pattern string needs to be shifted right. But how many positions to shift right? Since the number of matched characters at this point is 6 (ABCDAB), and according to thePMtable, the length value corresponding to character B, which is the previous character of the mismatched character D, is 2. Therefore, based on the previous conclusion, it is known that it needs to be shifted right by 6 - 2 = 4 positions, fromPM[i] = 2That is, restart matching from index 2

We can define anextarray: when the j-th (starting from 0) character of the pattern string fails to match, continue matching from the next[j]-th character of the pattern string.

The next array in KMPThere are two ways to write it:

PM table = prefix function π(i)(also calledlps array，Longest Prefix Suffix）。

• In some textbooks, next is equal to PM (lps)

• In some textbooks, next is a variant of PM

  • next[0] = -1(indicating a complete restart of matching)

  • next[i] = PM[i-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <string.h>

void GetNext(char *p, int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1) {
		//p[k] represents the prefix, p[j] represents the suffix
		if (k == -1 || p[j] == p[k]) {
			++k;
			++j;
			next[j] = k;
		} else {
			k = next[k];
		}
	}
}

int KmpSearch(char *s, char *p, int next[])
{
	int i = 0;
	int j = 0;
	int sLen = strlen(s);
	int pLen = strlen(p);
	while (i < sLen && j < pLen) {
		//If j = -1, or the current characters match successfully (i.e., S[i] == P[j]), then increment both i and j
		if (j == -1 || s[i] == p[j]) {
			i++;
			j++;
		} else {
			//If j != -1, and the current characters fail to match (i.e., S[i] != P[j]), then keep i unchanged and set j = next[j]
			//next[j] is the next value corresponding to j
			j = next[j];
		}
	}
	if (j == pLen)
		return i - j;
	else
		return -1;
}

Trees and Binary Trees

Terminology

graph TD
    A[A] --> B[B]
    A --> C[C]
    B --> D[D]
    B --> E[E]
    C --> F[F]
    C --> G[G]
    E --> H[H]
    E --> I[I]

    style A fill:#f9f,stroke:#333,stroke-width:2px
    style D fill:#9f9,stroke:#333
    style F fill:#9f9,stroke:#333
    style G fill:#9f9,stroke:#333
    style H fill:#9f9,stroke:#333
    style I fill:#9f9,stroke:#333

• Classification of Nodes

  • Root Node

    • The topmost node of a tree.

    • Example:Ais the root node.

  • Parent

    • The immediate upper-level node of a node.

    • Example:B’s parent node isA。

  • Sibling

    • Nodes sharing the same parent node are siblings.

    • Example:DandEare siblings,FandGare siblings.

  • Child Node

    • Child Node: A node directly connected to a parent node.
    • Example:D、EisB’s child node.

  • Descendant

    • All descendants of a node, including child nodes.
    • Example:H、IisB’s descendant.

  • Internal Node

    • A node that has child nodes.
    • Example:A、B、C、Eare all branch nodes.

  • Leaf Node

    • A node with no children.
    • Example:D、F、G、H、Iare leaf nodes.

• Node Properties

  • Depth of a Node

    • The length (number of edges) of the path from the root node to this node. (Top-down)

    • Example:Adepth 0,Bdepth 1,Ddepth 2.

  • Height of a Node

    • The length of the longest path from this node to the deepest leaf node. (Bottom-up)

    • Example:BHeight 2 (longest path B→E→H or B→E→I).

    • Level of a Node

      • Level = Depth + 1

      • Example: Root node A is level 1, B is level 2.

    • Degree

      • The number of child nodes a node has.
      • Example:Bhas degree 2 (D、E）。

• Classification of Trees

  • Tree of degree m

    • The degree of any node is not greater than m
    • At least one node has degree m
    • Must be a non-empty tree, thus has at least m+1 nodes

  • m-ary tree

    • The degree of any node is not greater than m
    • Can be an empty tree

  • Ordered Tree / Unordered Tree

    • Ordered Tree: The subtrees of nodes in the tree are ordered from left to right and cannot be swapped, meaning child nodes have a fixed order.

    • Unordered Tree: The order of child nodes is not important.

  • Forest

    • A collection of multiple disjoint trees.

    • If the root node A is removed, two trees, tree B and tree C, are formed, constituting a forest.

• Other Concepts

  • Path
    • The sequence of nodes traversed from one node to another.
    • Example: A→B→E→H is a path.
  • Path Length
    • The number of edges on the path.
    • Example: A→B→E→H, path length = 3.

Properties of Trees

1. The number of nodes in a tree equals the sum of all node degrees plus 1.

   • The proof is simple: except for the root node, every other node has an edge above it.

2. A tree of degree$m$has at most$i$nodes on the$m^{i-1}$-th level ($i \ge 1$)

3. A$h$-ary tree of height$m$has at most $\frac{m^h-1}{m-1}$ nodes

4. A$n$-ary tree with$m$nodes has a minimum height of $\lceil \log_m (n(m-1)+1) \rceil$

   • Proof: Under the condition of minimum height, try to make each node have$m$children, then:
   • $\frac{m^{h-1}-1}{m-1} < n \le \frac{m^h-1}{m-1}$

Binary Tree

A binary tree is an ordered tree

Terminology

• Full Binary Tree

  graph TD
      style A fill:#f9f,stroke:#333,stroke-width:2px
      style B fill:#9cf,stroke:#333,stroke-width:1px
      style C fill:#9cf,stroke:#333,stroke-width:1px
      style D fill:#9cf,stroke:#333,stroke-width:1px
      style E fill:#9cf,stroke:#333,stroke-width:1px
      style F fill:#9cf,stroke:#333,stroke-width:1px
      style G fill:#9cf,stroke:#333,stroke-width:1px
      style H fill:#9f9,stroke:#333,stroke-width:1px
      style I fill:#9f9,stroke:#333,stroke-width:1px
      style J fill:#9f9,stroke:#333,stroke-width:1px
      style K fill:#9f9,stroke:#333,stroke-width:1px
      style L fill:#9f9,stroke:#333,stroke-width:1px
      style M fill:#9f9,stroke:#333,stroke-width:1px
      style N fill:#9f9,stroke:#333,stroke-width:1px
      style O fill:#9f9,stroke:#333,stroke-width:1px
  
      A((1)) --> B((2))
      A --> C((3))
      B --> D((4))
      B --> E((5))
      C --> F((6))
      C --> G((7))
      D --> H((8))
      D --> I((9))
      E --> J((10))
      E --> K((11))
      F --> L((12))
      F --> M((13))
      G --> N((14))
      G --> O((15))
  

  • Height$h$, and a binary tree containing $2^h-1$ nodes is called a full binary tree

  • In a full binary tree, every node except leaf nodes has degree 2

  • A full binary tree can be numbered in level order, for a node numbered$i$:

    • Left child number:$2i$

    • Right child number:$2i+1$

    • Parent node number:$\lfloor i/2 \rfloor$

• complete binary tree

  graph TD
      style A fill:#f9f,stroke:#333,stroke-width:2px
      style B fill:#9cf,stroke:#333,stroke-width:1px
      style C fill:#9cf,stroke:#333,stroke-width:1px
      style D fill:#9cf,stroke:#333,stroke-width:1px
      style E fill:#9cf,stroke:#333,stroke-width:1px
      style F fill:#9cf,stroke:#333,stroke-width:1px
      style G fill:#9cf,stroke:#333,stroke-width:1px
      style H fill:#9f9,stroke:#333,stroke-width:1px
      style I fill:#9f9,stroke:#333,stroke-width:1px
      style J fill:#9f9,stroke:#333,stroke-width:1px
      style K fill:#9f9,stroke:#333,stroke-width:1px
      style L fill:#9f9,stroke:#333,stroke-width:1px
  
      A((1)) --> B((2))
      A --> C((3))
      B --> D((4))
      B --> E((5))
      C --> F((6))
      C --> G((7))
      D --> H((8))
      D --> I((9))
      E --> J((10))
      E --> K((11))
      F --> L((12))
  

  • with height$h$, having$n$a binary tree with nodes, if and only if each of its nodes corresponds one-to-one with nodes numbered 1 to n in a full binary tree of height$h$, it is called a complete binary tree
  • If $i \le \lfloor \frac{n}{2} \rfloor$, then node$i$is a branch node
  • Leaf nodes can only appear in the two largest levels, and for the largest level, leaf nodes are all arranged in the leftmost positions of that level.
  • If there is a node with degree 1, there can be at most one, and that node has only a left child and no right child.
  • After numbering by level order, once a node (numbered$i$) is a leaf node or has only a left child, then nodes with numbers greater than$i$are all leaf nodes
  • If$n$is odd, then every branch node has both left and right children; if$n$is even, then the branch node with the largest number (numbered$\frac{n}{2}$) only has a left child, no right child; the remaining nodes have both left and right children
  • Of the two subtrees of a complete binary tree (the left and right subtrees of the root node), at least one is a full binary tree

• Binary Search Tree

  • All keys in the left subtree are less than the root node’s key, and all keys in the right subtree are greater than the root node’s key; both the left and right subtrees are themselves binary search trees.

• Balanced Binary Tree

  • On the treeThe difference in depth between the left subtree and right subtree of any node does not exceed 1

Properties

1. The number of leaf nodes in a non-empty binary tree equals the number of nodes with degree 2 plus 1, i.e., $n_0 = n_2+1$

2. On a non-empty binary tree, the $k$-th level has at most$2^{(k-1)}$nodes ($k \ge 1$)

3. A binary tree of height$h$has at most$2^h-1$nodes ($h\ge1$）

4. with$n$nodescomplete binary treehas height $\lceil \log_2^{(n+1)} \rceil$ or $\lfloor \log_2^n \rfloor + 1$

5. forcomplete binary treenode numbering, the following relationships hold

Storage structure

• Sequential storage structure

Array storage, stored in the manner of a complete binary tree, using 0 or -1 to represent empty nodes.

• Linked storage

It is easy to verify that in a binary linked list containing$n$nodes, there are$n+1$null pointer fields

n nodes, 2n pointer fields, n-1 nodes have a pointer pointing to themselves, so there are n+1 null pointer fields

binary tree traversal

preorder traversal

visit the root node first, then traverse the left subtree, then traverse the right subtree

recursive implementation

1
2
3
4
5
6
7

void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

non-recursive implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void PreOrder(BiTree T){
	Stack *S;
    InitStack(S);
    BiTree p = T;
    while(p || !isEmpty(S)){//loop while the stack is not empty or p is not empty
        if(p){
            visit(p);
            Push(S, p);
            p = p->lchild;
        }else{
            Pop(S, p);
            p = p->rchild;
        }
        
    }
    DestroyStack(S);
}

description in Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}


use std::cell::RefCell;
use std::rc::Rc;

pub fn preorder(root: &mut Option<Rc<RefCell<TreeNode>>>, visit:  &impl Fn(&mut Rc<RefCell<TreeNode>>)) {
    // preorder traversal
    let mut stack = Vec::new();
    let mut p = root.clone();

    // preorder traversal
    while let Some(node) = p {
        visit(node);
        // push the right child onto the stack
        if let Some(right) = node.borrow().right.clone() {
            stack.push(right);
        }
        // push the left child onto the stack; if the left child is null, pop the stack; otherwise, p = Some(left)
        if let Some(left) = node.borrow().left.clone() {
            p = Some(left);
        } else {
            p = stack.pop();
        }
    }
}

inorder traversal

visit the left subtree first, then the root node, then the right subtree

Recursive approach

1
2
3
4
5
6
7

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

Non-recursive approach

1. Push the left children of the root node onto the stack in sequence until the left child is null, indicating that a node ready to be output has been found
2. Pop and visit the top element of the stack; if it has a right child, continue with step 1; otherwise, continue with step 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void InOrder(BiTree T){
	Stack *S;
    InitStack(S);
    BiTree p = T;
    while(p || !isEmpty(S)){//Loop while the stack is not empty or p is not null
        if(p){
            Push(S, p);
            p = p->lchild;
        }else{
            Pop(S, p);
            visit(p);
            p = p->rchild;
        }
        
    }
    DestroyStack(S);
}

Post-order traversal

Visit the left subtree first, then the right subtree, then the root node

Recursive approach

1
2
3
4
5
6
7

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

Non-recursive approach

1. Push the left children of the root onto the stack in sequence until the left child is null
2. Read the top element of the stack: if its right child is not null and has not been visited, perform step 1 on the right subtree; otherwise, pop and visit the top element

For the top element to be popped and visited, either its right subtree is null or its right subtree has already been visited (at which point the left subtree has long been visited). Therefore, we need an auxiliary pointer to indicate the most recently visited node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void PostOrder(BiTree T){
	Stack *S;
    InitStack(S);
    BiTNode *p = T;
    BiTNode *r= NULL;
    while(p || !isEmpty(S)){//Loop while the stack is not empty or p is not null
        if(p){
            Push(S, p);
            p = p->lchild;
        }else{
            GetTop(S,p);
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                Pop(S, p);
            	visit(p);
                r = p;
            	p = NULL;
            }
        }
        
    }
    DestroyStack(S);
}

In post-order traversal, when a node is about to be visited, the nodes in the stack are all the nodes on the path from the root to the current node

Non-recursive approaches for three traversals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <vector>
#include <stack>
using std::vector;
using std::stack;

struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode()
                : val(0)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x)
                : val(x)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x, TreeNode *left, TreeNode *right)
                : val(x)
                , left(left)
                , right(right)
        {
        }
};

vector<struct TreeNode *> preorder_traverse(struct TreeNode *root)
{
        stack<struct TreeNode *> stk;
        TreeNode *p = root;
        vector<struct TreeNode *> ret;

        while (p || !stk.empty()) {
                if (p) {
                        ret.push_back(p); // visit p
                        stk.push(p);
                        p = p->left;
                } else {
                        p = stk.top();
                        stk.pop();
                        p = p->right;
                }
        }
        return ret;
}

vector<struct TreeNode *> inorder_traverse(struct TreeNode *root)
{
        stack<struct TreeNode *> stk;
        TreeNode *p = root;
        vector<struct TreeNode *> ret;

        while (p || !stk.empty()) {
                if (p) {
                        stk.push(p);
                        p = p->left;
                } else {
                        p = stk.top();
                        stk.pop();
                        ret.push_back(p); // visit p
                        p = p->right;
                }
        }
        return ret;
}

vector<struct TreeNode *> postorder_traverse(struct TreeNode *root)
{
        stack<struct TreeNode *> stk;

        TreeNode *p = root, *last = nullptr;
        vector<struct TreeNode *> ret;

        while (p || !stk.empty()) {
                if (p) {
                        stk.push(p);
                        p = p->left;
                } else {
                        p = stk.top();
                        if (p->right != nullptr && p->right != last) {
                                p = p->right;
                        } else {
                                stk.pop();
                                ret.push_back(p); // visit p
                                last = p;
                                p = nullptr;
                        }
                }
        }

        return ret;
}

Level-order traversal

Traverse from the first layer to the last layer, from left to right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void LevelOrder(BiTree T){
    Queue *Q;
    InitQueue(Q);
    EnQueue(Q, T);
    while(!isEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL){
            EnQueue(Q, p->lchild);
        }
        if(p->rchild!=NULL){
            EnQueue(Q, p->rchild);
        }
    }
    DestroyQueue(Q);
}

If you need to record or perform some operations when each layer is fully visited:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/**
 * Definition for a binary tree node.
 **/
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode()
		: val(0)
		, left(nullptr)
		, right(nullptr)
	{
	}
	TreeNode(int x)
		: val(x)
		, left(nullptr)
		, right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right)
		: val(x)
		, left(left)
		, right(right)
	{
	}
};
#include <vector>
#include <queue>
using std::vector;
using std::queue;

class Solution {
    public:
	vector<int> rightSideView(TreeNode *root)
	{
		int i, n;
		vector<int> res;
		queue<TreeNode *> que;
		TreeNode *p;
		if (root == nullptr) {
			return res;
		}
		que.push(root);

		while (!que.empty()) {
			n = que.size();
			res.push_back(que.back()->val);
			for (i = 0; i < n; i++) {
				p = que.front();
				if (p->left) {
					que.push(p->left);
				}
				if (p->right){
				que.push(p->right);
				}
				que.pop();
			}
		}
		return res;
	}
};

Morris traversal

Morris traversal uses the idea of threaded binary trees. In the Morris method, there is no need to allocate additional pointers for each node to point to its predecessor and successor; it only needs to utilizethe left and right null pointers in leaf nodesto point to the predecessor or successor node under a certain order traversal.

graph TD

    subgraph 图2
        B1[1]
        B2[2]
        B3[3]
        B4[4]
        B5[5]
        B6[6]
        B7[7]
        
        B1 --> B2
        B1 --> B3
        B2 --> B4
        B2 --> B5
        B3 --> B6
        B3 --> B7
        
        B4 -.-> B2:::cur2
        B5 -.-> B1:::cur1
        B6 -.-> B3:::curn
        
    end
    
    subgraph 图1
        A1[1] --> A2[2]
        A1 --> A3[3]
        A2 --> A4[4]
        A2 --> A5[5]
        A3 --> A6[6]
        A3 --> A7[7]
    end

The overall idea of Morris is to start from a certain root node,find the rightmost node of its left subtree, and then connect it to this root node

We can see from Figure 2 that after such connection, the cur pointer can traverse from one node to the next completely, traversing the entire tree until node 7 has no right pointer. Code example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

/**
 * Definition for a binary tree node.
 **/
struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode()
                : val(0)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x)
                : val(x)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x, TreeNode *left, TreeNode *right)
                : val(x)
                , left(left)
                , right(right)
        {
        }
};

extern void visit(TreeNode *root);

class Solution {
    private:
    public:
        void preOrderMorris(TreeNode *root)
        {
                if (root == nullptr)
                        return;

                TreeNode *curr = root; // Current node
                TreeNode *curr_left = nullptr; // Root node of the left subtree of the current node

                while (curr != nullptr) {
                        curr_left = curr->left;

                        if (curr_left == nullptr) {
                                visit(curr);
                                curr = curr->right; // Continuously move right during the phase of returning to the upper level
                        } else {
                                // Find the rightmost node of the current left subtree, and cannot return to the upper level along the connection
                                while (curr_left->right != nullptr && curr_left->right != curr)
                                        curr_left = curr_left->right;
                                // The right pointer of the rightmost node does not point to the root node; create a connection and proceed to connect to the root node of the next left subtree
                                if (curr_left->right == nullptr) {
                                        visit(curr);
                                        curr_left->right = curr;
                                        curr = curr->left;
                                } else {
                                        // When the rightmost node of the left subtree points to the root node, it indicates that we have entered the phase of returning to the upper level,
                                        // no longer the initial connection establishment phase. At the same time, when returning to the root node, we should have already processed the lower-level nodes, so we can simply disconnect the link.
                                        curr_left->right = nullptr;
                                        curr = curr->right; // In the phase of returning to the upper level, we keep moving to the right.
                                }
                        }
                }
        }
};

#include <iostream>
using std::cout;
void visit(TreeNode *root)
{
        cout << root->val << " ";
}

int main()
{
        /*
            4
           / \
          2   6
         / \ / \
        1  3 5  7
       */

        TreeNode *n1 = new TreeNode(1);
        TreeNode *n3 = new TreeNode(3);
        TreeNode *n5 = new TreeNode(5);
        TreeNode *n7 = new TreeNode(7);

        TreeNode *n2 = new TreeNode(2, n1, n3);
        TreeNode *n6 = new TreeNode(6, n5, n7);

        TreeNode *root = new TreeNode(4, n2, n6);

        Solution sol;

        cout << "Morris Preorder Traversal: ";
        sol.preOrderMorris(root);
        cout << '\n';

        return 0;
}

Graph

Terminology

Basic Concepts

Classification by Edge Structure

Special Graphs

Graph Connectivity

Tree-related

Properties of vertices and edges

Path and Distance

Storage

Adjacency matrix method

Undirected graph：

• Ifiandjhave an edge:Edge[i][j] = Edge[j][i] = 1
• If no edge:Edge[i][j] = Edge[j][i] = 0

Directed graph：

• If there isi → j’s edge:Edge[i][j] = 1
• If not:Edge[i][j] = 0

Network (weighted graph)：

• Ifi → j’s weight isw, thenEdge[i][j] = w

• When there is no edge, it is generally set to∞(or a very large number)

• C language description

1
2
3
4
5
6
7

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType Vex[MaxVertexNum];              // vertex table
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; //adjacency matrix
}MGraph;

• C++ description

1
2
3
4
5
6
7
8
9

#include <unordered_map>
#include <vector>
using std::unordered_map;
using std::vector;

// node index range indefinite
unordered_map<int, vector<int>> graph;
// node index range definite
vector<vector<int>> graph;

adjacency list method

• C language description

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#define MaxVertexNum 100
typedef struct ArcNode{//edge table node
    int adjvex; //vertex pointed to by this arc
    struct ArcNode *next;
    // InfoType info // edge weight
}ArchNode;

typedef struct VNode{//vertex table node
    VertexType data; // vertex information
    ArchNode *first; //pointer to the first arc incident to this vertex
}VNode,AdjList[MaxVertexNum];

typedef struct{
    AdjList vertices;/// adjacency list
    int vexnum, arcnum;
}ALGraph;

• C++ Description

Orthogonal List Method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#define MaxVertexNum 100

typedef struct ArcNode {
    int tailvex;             // Arc Tail (Starting Point)
    int headvex;             // Arc Head (End Point)
    struct ArcNode *hlink;   // Points to the next arc with the same arc head
    struct ArcNode *tlink;   // Points to the next arc with the same arc tail
    int info;                // Weight (Optional)
} ArcNode;

typedef struct VexNode {
    char data;               // Vertex Information
    ArcNode *firstin;        // Points to the first incoming arc
    ArcNode *firstout;       // Points to the first outgoing arc
} VexNode;

typedef struct {
    VexNode xlist[MaxVertexNum]; // Vertex Table
    int vexnum, arcnum;          // Number of Vertices, Number of Arcs
} OLGraph; // Orthogonal List Graph

Adjacency Multilist

The adjacency multilist is another linked storage structure for undirected graphs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef struct ENode {
    int ivex, jvex;                 // Vertex Numbers of the Edge
    struct ENode *ilink, *jlink;   // Point to the next edge connecting ivex and jvex respectively
} ENode;

typedef struct VNode {
    char data;                     // Vertex information
    ENode *firstedge;             // First edge incident to this vertex
} VNode;

typedef struct {
    VNode adjList[MaxVertexNum];
    int vexnum, edgenum;
} AMLGraph;  // Adjacency Multilist Graph

Graph traversal

Breadth-First Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

bool visited[MAX_VERTEX_NUM];

void BFSTraverse(Graph G){
    Queue *Q;
    for(i = 0;i < G.vexnum;i++){
        visited[i] = false;
    }
    InitQueue(Q);
	for(i = 0;i < G.vexnum;i++){//Call BFS for each connected component
        if(!visited[i]){
            BFS(G,i);
        }
    }   
    DestroyQueue(Q);
}

void BFS(Graph G, int v){//Starting from vertex v, perform breadth-first traversal of G
    visit(v);
    visited[v] = TRUE;
    Enqueue(Q, v);
    while(!isEmpty(Q)){
        DeQueue(Q,v);
        for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ //Enqueue all unvisited adjacent vertices of v
            if(!visited[w]){
                visit(w);
                visited[w] = true;
                EnQueue(Q,w);
            }
        }
    }
}

If the graph is unweighted, BFS can be used to solve the single-source shortest path problem, mainly leveraging the property that breadth-first traversal visits vertices in order of increasing distance.

Depth-First Search

Recursive form

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
    for(v = 0;v<G.vexnum;v++)
        visited[v]=false;
        
    for(v = 0;v<G.vexnum;v++){
        if(!visited[v])
            DFS(G,v);
    }
}
void DFS(Graph G, int v){
    visit(v);
    visited[v] = true;
  	for(w = FirstNeighbor(G,v); w>=0 ; w = NextNeighbor(G,v,w)){
        if(!visited[w]){
            DFS(G,w);
        }
    }
}

Non-recursive form

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void DFS_Non_RC(AGraph &G, int v){
    int w;
    Stack *S;
    InitStack(S);
    for(i = 0;i<G.num;i++)
        visited[i] = false;

    Push(S,v);
    visited[v] = true;//Indicates already pushed onto the stack
    while(!isEmpty(S)){
        k = Pop(S);
        visit(k);
        for(w = FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)){
           if(!visited[w]){
               Push(S,w);
               visited[w] = true;
           } 
        }
        
    }
    DestroyStack(S);
}

Minimum spanning tree

Prim’s algorithm

Idea: Start from a point, each time selectthe edge with the smallest costadd the new vertex to the spanning tree

more suitable for：dense graphs(adjacency matrix)

Kruskal’s algorithm

Idea: Sort all edges of the graph by weight, select edges from smallest to largest, as long asno cycle is formedthen select

suitable for：sparse graphs

Using Union-FindAvoid forming cycles

Shortest path

Dijkstra’s algorithm

Single-source shortest path problem

Floyd’s algorithm

Shortest paths between all pairs of vertices

Topological sorting

Take the following problem as an example:

P207 Course schedule

https://even629.com/posts/207

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <vector>
#include <queue>

using std::vector;
using std::queue;

class Solution {
    public:
        bool canFinish(int numCourses, vector<vector<int> > &prerequisites)
        {
                // Build the graph
                int i;
                vector<vector<int> > graph(numCourses);
                vector<int> indegree(numCourses, 0); // Store the in-degree of each node
                vector<bool> pushed(numCourses, false);
                queue<int> que;

                for (vector<int> &vec : prerequisites) {
                        graph[vec[1]].push_back(vec[0]);
                        indegree[vec[0]]++;
                }

                // Topological sorting
                // Initialize by adding edges with in-degree 0
                for (i = 0; i < numCourses; i++) {
                        if (indegree[i] == 0) {
                                que.push(i);
                                pushed[i] = true;
                        }
                }

                while (!que.empty()) {
                        i = que.front();
                        que.pop();

                        // Each time find an edge with in-degree 0
                        for (int course : graph[i]) {
                                indegree[course]--;

                                if (!pushed[course] && indegree[course] == 0) {
                                        que.push(course);
                                        pushed[course] = true;
                                }
                        }
                }

                for (i = 0; i < numCourses; i++) {
                        if (!pushed[i])
                                return false;
                }

                return true;
        }
};