Wondershare EdrawMind
MindMap Gallery Data Structure Chapter 6 - Figure
- 17
Data Structure Chapter 6 - Figure
"Data Structure" Chapter 6 - Picture, this mind map organizes all the content involved, and can be used for preview or review.
Edited at 2022-11-23 16:07:27
- Avatar Character Relationship Chart
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
- Zootopia 2 Easter Egg
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
- Zootopia 2 Character Relationship Chart
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Data Structure Chapter 6 - Figure
- Avatar Character Relationship Chart
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
- Zootopia 2 Easter Egg
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
- Zootopia 2 Character Relationship Chart
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
- Recommended to you
- Outline
picture
Basic concepts of graphs
Definition of graph
G=(V,E)
Vertex set V(G): represents a finite non-empty set of vertices in graph G
Edge set E(G): represents the set of relationships (edges) between vertices in graph G
directed graph
Undirected graph
Simple graph, multiple graph
There are no duplicate edges
There is no edge from the vertex to itself
Complete graph (simple complete graph)
Undirected graph: There is an edge between any two vertices, |E|=n(n-1)/2
Directed graph: There are two arcs in opposite directions between any two vertices, |E|=n(n-1)
subplot
Suppose G=(V,E),G'=(V',E'), if V' and E' are subsets of V and E, then G' is a subgraph of G
If V(G)=V'(G'), then G' is the generated subgraph of G
Connectivity, connected graphs and connected components
Connected: In an undirected graph, if there is a path from vertex v to w, then v and w are said to be connected; if any two points in the graph G are connected, then G is called a connected graph.
Connected component: a maximal connected subgraph in an undirected graph (as opposed to an undirected graph with multiple connected components)
Strongly connected graph, strongly connected components
Strongly connected: In a directed graph, if there are paths between vertices v and w, v→w and w→v, then v and w are said to be strongly connected.
Every pair of vertices in a strongly connected component is reachable to each other
Spanning tree, spanning forest
Spanning tree: The spanning tree of a connected graph is a minimal connected subgraph that contains all the vertices in the graph (if the number of vertices in the graph is n, the spanning tree contains n-1 edges)
Cutting off an edge of the spanning tree will turn it into a disconnected graph
Adding an edge will form a loop in the graph
Spanning forest: In a non-connected graph, the spanning trees of connected components constitute the spanning forest of the non-connected graph.
Vertex degree, in-degree and out-degree
Undirected graph
The degree of vertex v refers to the number of edges attached to vertex v, denoted as TD(b)
The sum of degrees of all vertices of an undirected graph = number of edges * 2
directed graph
The degree of vertex v is divided into in-degree and out-degree
In-degree is the number of directed edges with v as the end point, recorded as ID(v)
Out-degree is the number of directed edges starting from vertex v, denoted as OD(v)
Sum of in-degrees = sum of out-degrees = number of edges
Bian's Quanhe.com
Dense graph, sparse graph
Paths, path lengths and loops
If a graph has n vertices and the number of edges > n-1, then the graph must have a cycle (loop)
Simple path, simple loop
Path/loop with non-repeating intermediate vertices
distance
directed tree
A directed graph in which the in-degree of one vertex is 0 and the in-degree of the other vertices is 1.
Storage and basic operations of graphs
adjacency matrix method
Use a one-dimensional array to store the vertex information in the graph, and use a two-dimensional array (adjacency matrix) to store the edge information in the graph.
weighted graph
Features
①The adjacency matrix of an undirected graph must be a symmetric matrix (and unique). Therefore, when actually storing the adjacency matrix, only the elements of the upper (or lower) triangular matrix are stored.
②For undirected graphs, the number of non-zero elements (or non-∞ elements) in the i-th row (or i-th column) of the adjacency matrix is exactly the number of vertices The degree of i is TD(v).
③For directed graphs, the number of non-zero elements (or non-∞ elements) in the i-th row of the adjacency matrix is exactly the out-degree OD(v) of vertex i; the number of non-zero elements (or non-∞ elements) in the i-th column The number is exactly the in-degree ID(v) of vertex i.
④ Using an adjacency matrix to store a graph, it is easy to determine whether there is an edge connecting any two vertices in the graph. However, to determine how many edges there are in the graph, each element must be detected by row and column, which is very time-consuming.
⑤ Dense graphs are suitable for storage representation using adjacency matrices.
⑥Suppose the adjacency matrix of graph G is A, and the element A"[i][j] of A" is equal to the number of paths with length n from vertex i to vertex j.
adjacency list method
Create a singly linked list for each vertex vi. The node in the i-th singly linked list represents the edge attached to vi. The linked list is called the edge list of vi (for a directed graph, it is called the outgoing edge list).
directed graph
Undirected graph
Features
cross linked list
A chain storage structure of a directed graph. There is an arc node corresponding to each arc in the graph and a vertex node corresponding to each vertex.
arc node
Tail domain (tailvex): indicates the position of the arc tail vertex in the graph
Head field (headvex): Indicates the position of the arc top point on the way
Chain domain (hlink): points to the next arc with the same arc head
Link domain (tlink): points to the next arc with the same arc tail
info field: related information pointing to the arc
vertex node
data field: stores vertex-related data information, such as vertex names
firstin: points to the first arc node with this vertex as the arc head
firstout: points to the first arc node with this vertex as the arc tail.
Features
In the cross-linked list, it is easy to find the arc with Vi as the tail and the arc with Vi as the head, so it is easy to find the out-degree and in-degree of the vertex. The cross-linked list representation of a graph is not unique, but a cross-linked list representation determines a graph.
Suitable for storing sparse matrices (which can be viewed as graphs represented by adjacency matrices)
adjacency multiple list
A chain storage structure of undirected graph
edge node
vertex node
Basic operations on graphs
Graph traversal
breadth first search
Basic idea
First visit the starting vertex v, then starting from v, visit each unvisited adjacent vertex w1, w2,..., wi of v in sequence, and then visit all unvisited vertices w1, w2,..., wi in sequence. Adjacent vertices; then starting from these visited vertices, visit all their unvisited adjacent vertices until all vertices in the graph have been visited. If there are still unvisited vertices in the graph at this time, select another unvisited vertex in the graph as the starting point, and repeat the above process until all vertices in the graph have been visited.
Implement code
Performance analysis
Space complexity: O(|V|)
time complexity
Adjacency list storage: each vertex needs to be searched once; when searching for the adjacencies of any vertex, each edge must be visited at least once
O(|V| |E|)
Adjacency matrix storage: finding each vertex requires O(|V|)
O(|V^2|)
BFS algorithm solves single source shortest path problem
breadth-first spanning tree
depth first search
Basic idea
First visit a starting vertex v in the graph, then start from v and visit any unvisited vertex w1 adjacent to v, then visit any unvisited vertex adjacent to w1...repeat the above process. . When it can no longer continue When accessing downward, return to the recently visited vertex in turn. If it has adjacent vertices that have not been visited, continue the above search process from that point until all vertices in the graph have been visited.
Implement code
Performance analysis
Space complexity: O(|V|)
time complexity
Adjacency list storage: each vertex needs to be searched once; when searching for the adjacencies of any vertex, each edge must be visited at least once
O(|V| |E|)
Adjacency matrix storage: finding each vertex requires O(|V|)
O(|V^2|)
Depth-first spanning trees and forests
Graph traversal and graph connectivity
The BFS and DFS algorithms of graphs can be used to determine the connectivity of graphs
For undirected graphs, BFS() or DFS() on a node can obtain its connected components;
For directed graphs, BFS() or DFS() can obtain strongly connected components, but cannot determine non-strongly connected components.
DFS algorithm can determine whether there is a loop in the graph
Application of diagrams
minimum spanning tree
Definition: The spanning tree with the smallest sum of edge weights among all spanning trees of a weighted connected undirected graph G; the minimum spanning tree is not necessarily unique, but the sum of weights is unique
Prim's algorithm
Basic idea
Each time the vertex closest to the existing vertex set is selected and added to the set until the vertex set is full.
The selected vertices should be outside the existing vertex set
algorithm process
Implement code
Time complexity: O(|V|^2)
It has nothing to do with |E|, so it is suitable for solving the minimum spanning tree of dense edge graphs.
Kruskal algorithm
Basic idea
Select appropriate edges in order of increasing weight to construct a minimum spanning tree
If the two end vertices of the edge are already connected (that is, a loop is formed after adding the edge), then discard the edge
algorithm process
Implement code
Time complexity: O(|E|log|E|)
Using a heap to store the set of edges, each edge selection only takes O(log|E|) time
Use union-find set to describe T
Kruskal's algorithm is suitable for graphs with sparse edges and many vertices.
shortest path
Dijkstra's algorithm for single source shortest path problem
Basic idea
Starting from the initial point, select the vertex closest to the current point set each time to join the point set.
Each time a new node is added, the distance between the external node and the vertex set and the position of the nearest node are updated.
algorithm process
1) Initialization: The initial value of set S is {0}, the initial value of dist [ ] is dist[i]=arcs [0][i],i=1,2,…,n-1.2) (arcs[i][j] is an element of the adjacency matrix, indicating the weight of the directed edge <i,j>)
2) Select vj from the vertex set V-S, satisfying dist[j]=Min{dist[i] | vi∈V-S}, v is the end point of the currently obtained shortest path starting from v0, let S=S ∪{j}
3) Modify the length of the shortest path from v0 to any vertex vk on the set V-S: If dist[j] arcs[j][k]< dist[k], update dist[k]=dist[j] ares [j][k]
4) Repeat operations 2)~3) n-1 times in total until all vertices are included in S.
nature
Based on greedy strategy
Time complexity: O(|V|^2)
Not suitable for graphs with negative weights
You can also use the single-source shortest path algorithm to solve the shortest path problem between vertices, and call Dijkstra's algorithm for each vertex, with a time complexity of O(|V|^3)
Floyd's algorithm for finding the shortest path between vertices
Basic idea
Starting from the adjacency matrix, loop 0~n-1 rounds. In the kth round, vk node is taken into consideration, and the shortest path between nodes i and j is found, and the sequence number of the intermediate result is not greater than k.
algorithm process
nature
Time complexity: O(|V|^3)
Applicable to graphs with negative weighted edges and weighted undirected graphs, but no cycles containing negative weighted edges are allowed.
Directed acyclic graph description expression
Directed acyclic graphs can be used to describe expressions containing common subexpressions; compared with binary trees, common subexpressions can be shared, thus saving storage space
topological sort
AOV network
If a DAG graph is used to represent a project, its vertices represent activities, and directed edges <Vi, Vj> are used to represent the relationship that activity Vi must precede activity Vj, then this directed graph is called a vertex-represented activity. The network is denoted as AOV network. In the AOV network, activity Vi is the direct predecessor of activity Vj, and activity Vj is the direct successor of activity Vi. This relationship between predecessor and successor is transitive, and any activity Vi cannot use itself as its own predecessor or successor.
AOV net and topological sorting
definition
Topological sorting is a sorting of the vertices of a directed acyclic graph such that if there is a path from vertex A to vertex B, then vertex B appears after vertex A in the sorting. Each AOV net has one or more topologically sorted sequences.
If the adjacency matrix of the graph is triangular, that is, there is no cycle in the graph, then there is a topological sorting, but it is not necessarily unique.
Algorithm for topological sorting of AOV network
① Select a vertex without a predecessor from the AOV network and output it.
② Delete the vertex and all directed edges starting from it from the network.
③Repeat ① and ② until the current AOV network is empty or there are no predecessor-less vertices in the current network. The latter case shows that there must be cycles in the directed graph.
algorithm process
Implement code
time complexity
Adjacency list: O(|V| |E|)
Adjacency: O(|V| |E|)
reverse topological sort
① Select a vertex with no successor (out-degree 0) from the AOV network and output it.
② Delete the vertex and all directed edges ending with it from the network.
③ Repeat ① and ② until the current AOV net is empty.
AOE net and critical path
AOE network
Similar to the AOV network, but the edges in AOE have weights. Vertices represent events, directed edges represent activities, and edge weights represent the cost of completing the activity.
Only after the event represented by a vertex occurs, the activities represented by the directed edges starting from the vertex can begin.
Only after the activities represented by each directed edge entering a vertex are completed, the event represented by the vertex can start.
Critical Path
definition
Activities in the AOE network can be carried out in parallel. The longest path from the source point (the only vertex with an in-degree of 0) to the sink (the only vertex with an out-degree of 0) is called the critical path, and the activities on it are called the critical path. activity, which determines the minimum time for project completion
There may be multiple critical paths, and only by accelerating activities on all critical paths at the same time can the construction period be shortened; there may also be a special critical activity called a "bridge" that is located on all critical paths and can speed up the cycle.
Parameter
The earliest occurrence time of event vk ve(k)
Refers to the longest path length from source point v1 to vertex vk, which determines the earliest time when activities starting from vk can start
Recursive
ve(source point)=0
ve(k)=Max{ve(j) Weight(vj,vk)}, vk is any successor of vj
The latest occurrence time v(k) of event vk
Refers to the latest time that the event must occur without delaying the completion of the entire project.
Recursive
vl(sinking point)=ve(sinking point)
vl(k)=Min{vl(j)-Weight(vk,vj)}, vk is any precursor of vj
The earliest start time e(i) of activity ai
Refers to the earliest occurrence time of the event represented by the starting point of the activity arc, that is, e(i)=ve(k)
The latest start time l(i) of activity ai
Refers to the difference between the latest occurrence time of the event represented by the end point of the activity arc and the time required for the activity, that is, l(i)=vl(i)-Weight(vk,vj)
The difference between the latest start time and the earliest start time of an activity ai is d(i)=l(i)-e(i)
Refers to the time margin for the completion of the activity, the time that can be delayed
Solving algorithm
1) Starting from the source point, let ve (source point) = 0, and find the earliest occurrence time ve() of the remaining vertices in topological order.
2) Starting from the sink point, let vl (sink point) = ve (sink point), and find the latest occurrence time vl () of the remaining vertices in reverse topological order.
3) Calculate the earliest starting time e() of all arcs based on the ve() value of each vertex
4) Calculate the latest start time l() of all arcs based on the ve() value of each vertex
5) Find the difference d() of all activities in the AOE network, and find out all activities with d()=0 that constitute the critical path.
Solving process