Wondershare EdrawMind
MindMap Gallery data structure(2)
- 11
data structure(2)
The three elements of data structure are: logical structure, physical structure (storage structure), and data operations. Welcome to take a look at data structure knowledge.
Edited at 2023-05-28 15:46:20
- One Hundred Years of Solitude Character Relationship Chart
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
- One Hundred Years of Solitude Character Relationship Chart
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
- Project Management Process Template
Project management is the process of applying specialized knowledge, skills, tools, and methods to project activities so that the project can achieve or exceed the set needs and expectations within the constraints of limited resources. This diagram provides a comprehensive overview of the 8 components of the project management process and can be used as a generic template for direct application.
data structure(2)
- One Hundred Years of Solitude Character Relationship Chart
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
- One Hundred Years of Solitude Character Relationship Chart
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
- Project Management Process Template
Project management is the process of applying specialized knowledge, skills, tools, and methods to project activities so that the project can achieve or exceed the set needs and expectations within the constraints of limited resources. This diagram provides a comprehensive overview of the 8 components of the project management process and can be used as a generic template for direct application.
- Recommended to you
- Outline
data structure
1.1 Basic concepts of data structure
data structure
basic concept
data
data element, data item
data objects, data structures
Data type, abstract data type (ADT)
Three elements
logical structure
Physical structure (storage structure)
Data operations
1.2.1 Basic concepts of algorithms
Basic concepts of algorithms
what is algorithm
program = data structure algorithm
Data structures are the information to be processed
Algorithms are steps for processing information
Five characteristics of algorithms
Characteristics that an algorithm must possess
Finiteness
Can be executed within a limited time
Algorithms are finite
Programs can be infinite
certainty
The same input will only produce the same output
feasibility
Algorithms can be implemented using existing basic operations
enter
Data thrown to the algorithm for processing
output
The result of algorithm processing
Characteristics of a “good” algorithm
Goals that should be pursued as much as possible when designing algorithms
correctness
Able to solve problems correctly
readability
Describe the algorithm so that others can understand it
Robustness
Algorithms can handle some abnormal situations
High efficiency and low storage requirements
That is, algorithm execution saves time and memory.
Low time complexity and low space complexity
1.2.2 Time complexity of the algorithm
time complexity
How to calculate
① Find a basic operation (the deepest loop)
② Analyze the relationship between the number of executions of the basic operation X and the problem size n x = f (n)
③The order of magnitude O(x) of x is the algorithm complexity
Commonly used techniques
Addition rule
multiplication rule
P6 in the book often refers to the order of powers
Three levels of complexity
Worst-case time complexity: consider the "worst" case of the input data
Average time complexity: consider the situation where all input data appear equally likely
Best Time Complexity: Consider the “best” case for the input data
space complexity
How to calculate
Ordinary program
①Find the variables related to the size of the space occupied and the size of the problem
②Analyze the relationship between occupied space x and problem size n x=f(n)
③The order of magnitude O(x) of x is the algorithm space complexity S(n)
recursive program
① Find the relationship between the depth of the recursive call x and the problem size n x = f (n)
②The order of magnitude O(x) of x is the algorithm space complexity S(n)
Note: Some algorithms require different storage space for each layer of functions, and the analysis methods are slightly different.
Commonly used techniques
Addition rule
multiplication rule
Simultaneous time complexity
2.1 Definition and basic operations of linear tables
linear table
definition
Characteristics worth paying attention to
Data elements are of the same type, limited, and ordered
important terms
Table length, empty table
Table header, table footer
precursor, successor
Bit order of data elements (starting from 1)
Basic operations
Creation, creation, deletion, modification and search (memory ideas applicable to all data structures)
Judge empty, judge long, print output
Other points worth noting
Understand when to pass in parameter reference "&"
Function naming should be readable
Storage/Physical Structure
Sequence table (sequential storage)
Definition (how to implement it in code)
Implementation of basic operations
Linked list (linked storage)
Single list
Definition (how to implement it in code)
Implementation of basic operations
Double linked list
circular linked list
static linked list
2.2.1 Definition of sequence table
Sequence table
storage structure
Data elements that are logically adjacent are also physically adjacent
Method to realize
static allocation
Implemented using "static array"
Once the size is determined, it cannot be changed
dynamic allocation
Implemented using "dynamic array"
L.data=(ElemType*)malloc(sizeof(ElemType)*size);
When the sequence table is full, malloc can be used to dynamically expand the maximum capacity of the sequence table.
It is necessary to copy the data elements to a new storage area and use the free function to release the original area.
Features
random access
Can find the i-th element in O(1) time
High storage density
Expanding capacity is inconvenient
Inserting and deleting data elements is inconvenient
2.2.2.1 Insertion and deletion of sequence table
Basic operations of sequence tables
insert
Listinsert(&L,i,e)
Insert element e into the i-th position of L
Elements after the insertion position must be moved back
time complexity
Best O(1), worst O(n), average O(n)
delete
ListDelete(&L,i,&e)
Delete the i-th element of L and return it with e
Elements after the deleted position must be moved forward
time complexity
Best O(1), worst O(n), average O(n)
Code points
Pay attention to the difference between bit order i and array subscript in the code
The algorithm must be robust and pay attention to the legality of i
When moving elements, start from the front element? Or start from the last element of the table?
Analyze the code and understand why some parameters need to be quoted with "&"
2.2.2.2 Searching the sequence table
Basic operations of sequence tables
Bitwise search
GetElem(L,i)
Get the value of the element at position i in table L
Use the array subscript to get the i-th element L.data[i-1]
time complexity
Best/worst/average time complexity is O(1)
Find by value
LocalElem(L,e)
Find the element whose first element value is equal to e in the sequence list L and return its bit order
Search starting from the first element and going backwards
time complexity
Best O(1): target element is at first position
Best O(n): target element is at the last position
Best O(n): target element has the same probability at every position
2.3.1 Definition of singly linked list
Single list
Use "chain storage" (storage structure) to realize "linear structure" (logical structure)
A node stores a data element
The sequence relationship between each node is represented by a pointer
Define a singly linked list using code
Two implementations
No leading node
Empty table judgment: L==NULL. Writing code is inconvenient
Leading node
Empty table judgment: L→next==NULL. Writing code is more convenient
Other points to note
Usage of typedef keyword
LinkList is equivalent to LNode* The former emphasizes that this is a linked list, and the latter emphasizes that this is a node. Use the right name in the right place to make the code more readable
2.3.2.1 Insertion and deletion of singly linked list
insert
Insert in bit order
Leading node
No leading node
Post-insert operation of specified node
Forward insertion operation of specified node
delete
Delete in bit order
Deletion of specified node
2.3.2.2 Search in singly linked list
Bitwise search
Note the comparison with the "sequence table"
A singly linked list does not have the characteristic of "random access" and can only be scanned sequentially.
Find by value
Find the length of singly linked list
key
The time complexity of the three basic operations is O(n)
How to write code logic that loops through each node
Pay attention to the processing of boundary conditions
2.3.2.3 Creation of singly linked list
Create a singly linked list using head insertion method
Create a singly linked list using tail insertion method
2.3.3 Double linked list
initialization
The priority.next of the head node all points to NULL.
Insert (rear insert)
Pay attention to the pointer modifications of newly inserted nodes, predecessor nodes, and successor nodes.
⚠️Boundary case: the newly inserted node is at the last position and requires special treatment
Delete(insert after)
Pay attention to the modification of the pointers of the predecessor node and successor node of the deleted node.
⚠️Boundary case: If the deleted node is the last data node, special processing is required
Traverse
Starting from a given node, the implementation of backward traversal and forward traversal (termination condition of the loop)
Linked lists do not have random access characteristics, and search operations can only be achieved through sequential traversal.
2.3.4 Circular linked list
Circular singly linked list
Empty table f
non-empty table
Circular doubly linked list
Empty table
non-empty table
code problem
2.3.5 Static linked list
2.3.6 Comparison between sequence list and linked list
3.1.1 Basic concepts of stack
stack
definition
A linear table with limited operations, which can only be inserted and deleted at the top of the stack
Features: Last in, first out (LIFO)
Terminology: top of stack, bottom of stack, empty stack
Basic operations
Create, sell
Add, delete (elements are pushed into and popped out of the stack, and can only be operated on the top of the stack)
Check (get the top element of the stack, but do not delete it)
Call it short
3.1.2 Sequential storage implementation of stack
sequence stack
Sequential storage is implemented using a static array, and the top pointer of the stack needs to be recorded.
Basic operations
Create, delete, modify and check
Both have O(1) time complexity
Two implementations
top=1 during initialization
push to stack
S.data［ S.top］=x;
pop
x=S.data［S.top--］;
Get the top element of the stack
x=S.data［S.top］;
What are the conditions for stack empty/stack full?
top=0 during initialization
push to stack
S.data［S.top］=x;
pop
x=S.data［--S.top］;
Get the top element of the stack
x=S.data［S.top-1］;
What are the conditions for stack empty/stack full?
shared stack
The two stacks share the same memory space, and the two stacks grow from both sides to the middle.
initialization
The top pointer of stack No. 0 is initially top0=-1; the top pointer of stack No.1 is initially TOP1=MaxSize;
Stack full condition
top0 1==top1
3.1.3 Chain storage implementation of stack
chain stack
Stack implemented using chained storage
Two implementation methods
Leading node
No leading node (recommended)
Important basic operations
Creation (initialization)
Increase (push)
Delete (pop)
Check (get the top element of the stack)
How to judge empty and full
3.2.1 Basic concepts of queue
definition
A linear table with limited operations, which can only be inserted at the end of the queue and deleted at the head of the queue.
Features: first in, first out
Terms: queue head, queue tail, empty queue, queue head element, queue tail element
Basic operations
Create, sell
Adding and deleting (entry and exit can only be done at the specified end)
Check (get the head element, but do not delete it)
Call it short
3.2.2 Sequential implementation of queues
realize ideas
Use a static array to store data elements and set the front/rear pointer
Circular queue: Use modular operation (remainder) to logically turn the storage space into a "ring"
Q.rear=(Q.rear 1)%MaxSize
Important test points
How to initialize, join, and dequeue
How to judge empty and full
How to calculate the length of a queue
analysis of idea
Determine the pointing of front and rear pointers
①rear points to the position after the last element of the queue
②rear points to the element at the end of the queue
Methods to determine whether a short or full decision is made
a. Sacrifice a storage unit
b. Increase the size variable to record the queue length
c. Add tag=0/1 to mark the latest operation as dequeue/enqueue
…
3.2.3 Chain implementation of queue
queue
Implementing queues using chained storage
Leading node
No leading node
Basic operations
Creation (initialization)
Add (join the team)
Note that the first element is enqueued
Delete (dequeue)
Note that the last element is dequeued
Check (get the head element)
Call it short
Sentence full? nonexistent
3.2.4 Double-ended queue
Queue variants
deque
A queue that allows two segments to be inserted and deleted at both ends.
Input restricted deque
A queue that allows deletions from both ends and insertions from one end
Output restricted deque
A queue that allows insertion from both ends and deletion from the other end
Test point: Judgment of the legality of the output sequence
A valid output sequence on the stack must be valid on the double-ended queue.
3.3.1 Application of stack in bracket matching
Use stack to implement bracket matching
Scan all characters in sequence, and when encountering a left bracket, push it onto the stack. When a right parenthesis is encountered, the top element of the stack is popped to check whether it matches.
Match failure situation
1 left bracket single
2 right bracket single
3 Left and right brackets do not match
3.3.2.1 Application of stack in expression evaluation (Part 1)
Expression evaluation problem
concept
Operator, operand, limiter (DIY concept: left operand, right operand)
three expressions
infix expression
The operator is in the middle of the operands
Postfix expression (reverse Polish)
The operator comes after the operand
Prefix expression (Polish)
The operator precedes the operands
⚠️Suffix expression test points
Convert infix to suffix
① Determine the order of operations of operators according to the "left priority" principle
②According to the order determined in ①, sequence each operator and its two adjacent operands. Combine according to the rules of "left operand, right operand, operator"
Convert suffix to infix
Scanning from left to right, each time an operator is encountered, 〈left operand right operand operator〉 Becomes in the form of (left operand operator right operand)
calculate
Scan from left to right, and when an operand is encountered, it is pushed onto the stack. When an operator is encountered, the two top elements of the stack are popped out and pushed onto the stack after operation. (Note: The "right operand" pops up first)
prefix expression
Convert infix to prefix
① Determine the order of operations of operators according to the "right priority" principle
②According to the order determined in ①, sequence each operator and its two adjacent operands. Combine according to the rules of 〈operator left operand right operand〉
calculate
Scan from right to left, and when an operand is encountered, it is pushed onto the stack. When an operator is encountered, the two top elements of the stack are popped out and pushed onto the stack after operation. (Note: The first thing that pops up is the "left operand")
3.3.2.2 Application of stack in expression evaluation
Using stack to implement infix to postfix expression
Initialize a stack to save operators whose order of operations cannot yet be determined.
Each element is processed from left to right until the end. You may encounter three situations
①The operand is encountered. Add suffix expression directly
② Encountered a boundary symbol. When "(" is encountered, it is pushed directly onto the stack; when ")" is encountered, the operators in the stack are popped out in turn and added. Postfix expression until "(" pops up. Note: "(" does not join the postfix expression
③Encounter operator. Pop all operators on the stack that have a priority higher than or equal to the current operator in sequence. And add a suffix expression, and stop if it encounters "(" or the stack is empty. Then push the current operator onto the stack
After all characters are processed according to the above method, the remaining operators in the stack are popped out one by one, and the suffix expression is added.
Use stack to implement calculation of postfix expressions
①Scan the next element from left to right until all elements are processed
②If the operand is scanned, push it onto the stack and return to ①; otherwise, execute ③
③If the operator is scanned, the two top elements of the stack are popped up, the corresponding operation is performed, and the operation result is pushed back to the top of the stack, returning to ①
Use stack to implement calculation of infix expressions
Initialize two stacks, the operand stack and the operator stack
If the operand is scanned, push it into the operand stack
If an operator or delimiter is scanned, it is pushed onto the operator stack according to the same logic of "infix to suffix" (Operators will also be popped during this period. Whenever an operator is popped up, the top elements of the two operand stacks need to be popped up and the corresponding Operation, the operation result is pushed back to the operand stack)
3.3.3 Application of stack in recursion
Characteristics of function calls: The last called function is executed first (LIFO)
When a function is called, a "function call stack" needs to be used to store
call return address
Arguments
local variables
When called recursively, the function call stack can be called the "recursive work stack" Each time a recursion is entered, the information required for the recursive call is pushed onto the top of the stack. Each time a level of recursion is exited, the corresponding information is popped from the top of the stack.
3.4 Compressed storage of special matrices
Symmetric matrix
Features: Any element in the opponent's array has a(i,j)=a(i,j)
Compression: only store the main diagonal and lower triangle (or the main diagonal and upper triangle)
triangular matrix
Features: The upper triangular area is all constants (lower triangular matrix); or the lower triangular area is all constants (upper triangular matrix)
Compression: Store non-constant areas sequentially according to row-majority/column-majority rules, and store the constant c in the last position
Tridiagonal matrix (banded matrix)
Features: When |i-j|>1, there is a(i,j)=0(1≤i,j≤n)
Compression: Store striped regions sequentially according to row-major/column-major rules
sparse matrix
The number of non-zero elements is less than the number of zero elements
Compression: only store non-zero elements
Sequential storage: sequential storage of triples <row, column, value>
Linked storage: cross linked list method
4.1.1 Definition and basic operations of string
string
definition
A string is a finite sequence of zero or more characters.
Terms: string length, empty string, space string, substring, main string, character position in the main string, substring position in the main string
String vs linear table
String data objects are limited to character sets
Most of the basic operations on strings use "substring" as the operation object.
Basic operations
index(S, T), positioning operation, find the position of string T in the main string S
StrCompare(S,T): comparison operation. If S>T, the return value is>0; if S=T, the return value=0; If S<T, the return value<0;
other…
Character set encoding
Each character corresponds to a binary number in the computer. Comparing the size of characters is actually comparing the size of binary numbers.
4.1.2 String storage structure
sequential storage
static array
dynamic array
malloc free
chain storage
Each node can store multiple characters, and the positions without characters are filled with "#" or '/0'
Adopted by royal teaching materials —static array
Implementation of basic operations
Find substring: bool SubString (SString&Sub, SString S, int pos, int len)
String comparison: int StringCompare(SString S, SString T)
Find the position of the string in the main string: int index (SString S, SString T)
4.2.1 Naive pattern matching algorithm
Algorithmic thinking
Main string length n, pattern string length m
Compare all substrings of length m in the main string with the pattern string
Find the first substring that matches the pattern string and return the starting position of the substring
If no substrings match, zero is returned
Worst time complexity = O (nm)
4.2.2KMP algorithm
5.1.1 and 5.1.2 Tree definitions and basic terminology
basic concept
Node, edge, root node, leaf node, branch node, subtree
basic terminology
relationship between nodes
Parent node (parent node), child node
Ancestor node, descendant node
brother node, cousin node
Paths between nodes—can only go from top to bottom
Path length—how many edges pass along the path
Nodes, attributes of the tree
The level (depth) of the node, the height of the node
tree depth (height)
degree of node
The number of branches of the node
degree of tree
The maximum degree of each node in the tree
Ordered tree vs unordered tree
From a logical point of view, whether the subtrees are in order and whether their positions are interchangeable
forest
A forest consists of M (M>0) disjoint trees.
5.1.3 Properties of trees
Test point one
Number of nodes = total degree 1
Test point two
tree of degree m
There is at least one node with degree=m
Must be a non-empty tree
m-ary tree
Allow the degree of all nodes to be <m
Can be an empty tree
Test point three
How many nodes does a tree of degree m have at most i-th level?
Test point four
How many nodes does an m binary tree with height h have at most?
Test point five
How many nodes does an m-ary tree with height h have?
How many nodes does a tree with height h and degree m have?
Test point six
What is the minimum height of an m-ary tree with n nodes?
5.2.1.1 Definition and basic terminology of binary tree
Binary tree
basic concept
Empty binary tree
The degree of any node ≤ 2
It is an ordered tree. The left subtree and right subtree cannot be reversed.
Thinking: Binary tree vs ordered tree of degree 2
special binary tree
full binary tree
A binary tree with height h and 2×h-1 nodes.
complete binary tree
On the basis of a full binary tree, several nodes with higher numbers can be removed
Binary sorting tree
Left subtree key＜Root node key＜Right subtree key
balanced binary tree
The depth difference between the left and right subtrees does not exceed 1
5.2.1.2 Properties of binary trees
5.2.2 Storage structure of binary tree
5.3.1.1 First-in-last order traversal of binary trees
Binary tree traversal
three methods
preorder traversal
root, left and right
inorder traversal
left, right, root
Postorder traversal
left, right, root
Traverse algorithm expression tree
Prefix expression obtained by preorder traversal
Infix expression of inorder traversal (without parentheses)
Postfix expression obtained by postorder traversal
Test point: Find the traversal sequence
Layer-by-layer expansion method of branch nodes
Passing through your world
Preface—passing by during first visit
Middle sequence—passed by during the second visit
Postscript—Passing by during my third visit
5.3.1.2 Level traversal of binary trees
The idea of tree level traversal
①Initialize an auxiliary queue
②Root node joins the queue
③If the queue is not empty, the head node of the team joins the queue, visits the node, and inserts its left and right children into the queue.
④Repeat ③ until the queue is empty
5.3.1.3 Constructing a binary tree from a traversal sequence
Preorder and inorder traversal of sequence
Post-order and in-order traversal sequence
Level order in-order traversal sequence
There must be an intermediate sequence
5.3.2.1 Concept of clue binary tree
clue binary tree
Function: It is convenient to start from a specified node and find its predecessor and successor; it is convenient to traverse
storage structure
On the basis of ordinary binary tree nodes, two flags itag and rtag are added
When itag==1, it means ichild points to the predecessor; when itag==0, it means ichild points to the left child.
When rtag==1, it means rchild points to the successor; when rtag==0, it means ichild points to the right child.
Three clues binary tree
In-order clue binary tree
"Clue" based on in-order traversal sequence
preorder clue binary tree
"Clue" based on pre-order traversal sequence
postorder clue binary tree
"Clueing" based on post-order traversal sequence
several concepts
clue
Pointers to predecessors/successors are called clues
Predecessor in sequence/successor in sequence; predecessor in sequence/successor in sequence; predecessor in sequence/successor in subsequent sequence
Hand brush drawing clue binary tree
① Determine the clue binary tree type—inorder, preorder, or postorder?
②According to the corresponding traversal rules, determine the access sequence of each node and write the number
③Connect n 1 empty chain domains to the predecessor and successor
5.3.2.2 Threading of binary trees
Mid-sequence threading
Get the in-order clue binary tree
preorder cueing
Get preorder clue binary tree
Follow-up clues
Get post-order clue binary tree
core
Modification of the in-order/pre-order/post-order traversal algorithm. When a node is accessed, the node is connected. Clues to precursor nodes
Use a pointer pre to record the predecessor node of the currently accessed node.
Easy to make mistakes
Processing of rchild and rtag of the last node
In pre-order threading, pay attention to dealing with the circle problem. When itag==0, the left subtree can be pre-order threaded.
5.3.2.3 Find predecessor and successor in clue binary tree
If itag/rtag==0
You can push it out yourself
5.4.1 Tree storage structure
Tree and forest storage structures
parent representation
Node data is stored sequentially, and the subscript of the parent node in the array is stored in the node.
Advantages: Convenient to find parent nodes; Disadvantages: Inconvenient to find children
child representation
Node data is stored sequentially, and the child linked list head pointer is stored in the node (sequential chained storage)
Advantages: Convenient to find children; Disadvantages: Inconvenient to find parent nodes
child brother representation
Use a binary linked list to store nodes—left child, right brother
When used to store a forest, the root node of each tree in the forest is regarded as a peer relationship.
From a storage perspective, the shape is similar to a binary tree.
5.4.2 Conversion of trees, forests and binary trees
key
Essence: Use child sibling representation to store trees or forests, similar in form to binary trees
When storing a forest using child sibling representation, the root node of each tree in the forest is treated as a sibling relationship of the same level.
Tree, forest to binary tree
Process each node in sequence according to "level order"
The method of processing a node is: if the node currently processed has children, all children The node is "stringed into candied haws with the right pointer", and the first child is hung at the current node in the binary tree under the left pointer
Binary tree to tree, forest
Restore the children of each node in "level order"
How to restore the children of a node: In a binary tree, if the node currently being processed has a left child , remove the left child and "a whole string of right pointer candied haws", and hang them below the current node in order.
5.4.3 Tree and forest traversal
Tree
Root traversal first
back root traversal
forest
preorder traversal
inorder traversal
Binary tree
preorder traversal
inorder traversal
Chapter 6 Picture
6.1 Basic concepts of graphs
6.1.1 Basic concepts of graphs
Definition: G=(V,E), vertex set V, edge set E
Undirected graph (undirected edge/edge), directed graph (directed edge/arc)
Degree, out-degree, in-degree of vertices (undirected graph? directed graph?)
Edge rights, weighted pictures/nets
point-to-point relationship
path, loop, simple path, simple loop
path length
Point-to-point distance (shortest path)
Connectivity of undirected graph vertices, connected graph
Connectivity of directed graph vertices, connected graph
Part of the picture
subplot
Connected components—maximally connected subgraphs
Strongly connected component—maximum strongly connected subgraph
Spanning tree of a connected undirected graph—a minimal connected subgraph that contains all vertices
Spanning forest of unconnected undirected graph—spanning tree of each connected component
Several special forms of pictures
complete graph
Dense graph, sparse graph
tree, forest, directional tree
Common test points
For an undirected graph G with n vertices
The sum of the degrees of all vertices = 2｜E｜
If G is a connected graph, then there are at least n-1 edges (trees), if |E|>n-1, then there must be a loop
If G is a disconnected graph, it may have at most one edge
Undirected complete graphs share edges
For a directed graph G with n vertices
The sum of the degrees of all vertices = 2｜E｜
If G is a connected graph, there are at least n edges (trees) forming a cycle.
The sum of out-degrees of all vertices = the sum of in-degrees = |E|
Directed complete graphs share edges
6.2 Picture storage and basic operations
adjacency matrix
The sequential storage implemented by arrays has high space complexity and is not suitable for storing sparse graphs.
adjacency list
cross linked list
Store directed graph
adjacency multiple list
Store undirected graph
6.3 Graph traversal
6.3.1 Breadth-first traversal of graphs (BFS)
Similar to tree-level traversal (breadth-first traversal)
Algorithm points
Requires an auxiliary queue
How to find other vertices adjacent to a node
The visited array prevents repeated visits
How to deal with disconnected graphs
the complexity
Space complexity: O(|V|)—auxiliary queue
time complexity
Time to visit a node ➕Time to visit all edges
Adjacency matrix: O(|V|^2)
Adjacency list: (｜V｜ |E｜)
breadth-first spanning tree
tree determined by breadth-first traversal
The graph representation stored in the adjacency list is not unique, and the traversal sequence and spanning tree are not unique either.
Traversing a non-connected graph generates a breadth-first forest
Depth-first traversal of graphs (DFS)
Algorithm points
Recursively explore unvisited adjacent points in depth (similar to the implementation of root-first traversal of trees)
How to find other vertices adjacent to a node
The visited array prevents repeated visits
How to deal with disconnected graphs
Complexity analysis
Space complexity: O|V|—from the recursive work stack
time complexity
Time to visit a node ➕Time to visit all edges
Adjacency matrix: O(|V|^2)
Adjacency list: O (|V| |E|)
depth first spanning tree
tree determined by depth-first traversal
The graph representation stored in the adjacency list is not unique, and the depth-first traversal sequence does not generate a unique number.
Depth-first traversal of a disconnected graph can generate a depth-first forest.
Graph traversal and graph connectivity
Undirected graph
Number of DFS/BFS function calls = number of connected components
directed graph
If there is a path from the starting vertex to other vertices, you only need to call the DFS/BFS function once
For strongly connected graphs, the DFS/BFS function only needs to be called once from any vertex.
6.4 Application of diagrams
6.4.1 Minimum spanning tree
Prim's algorithm (Prim)
Build a spanning tree starting from a certain vertex; Each time, the new vertex with the minimum cost is included in the spanning tree. until all vertices are included
Kruskal algorithm (Kruskal)
Select an edge with the smallest weight each time so that the Both ends are connected (the ones that are already connected are not selected) Until all nodes are connected
6.4.2 Shortest path problem
single source shortest path
BFS algorithm (unweighted graph)
Dijkstra's algorithm (weighted graph, unweighted graph)
Not suitable for weighted graphs with negative weights
The shortest path between vertices
Floyd algorithm (weighted graph, unweighted graph)
Unable to solve graphs with "negative weight cycles", which may not have shortest paths
subtopic