Chapter 5: Figure
This is the 19th day of my participation in the August Wenwen Challenge.More challenges in August
Mind mapping
Basic concepts of graphs
-
Definition: A tree is a finite set of N (N≥0) nodes. When N=0, it is called an empty tree, which is a special case. In any non-empty tree: 1) there is and only one specific node called the root. 2) When N>1, the other nodes can be divided into m (m>0) finite sets T1, T2… Tm, where each set is itself a tree and is called a subtree of the root node.
-
Graph G consists of vertex set V and edge set E, denoted as G=(V, E).
- V(G) represents a finite non-empty set of vertices in graph G. Use | V | for the vertices of a graph G number, also known as the order of graph G
- E(G) represents the set of relations (edges) between vertices in graph G. Expressed in | E | article edges in the graph G.
-
-
classification
-
Directed graph
-
Finite set of directed edges (arcs)
- An arc is an ordered pair of vertices
- <v,w>
- V is arc tail, w is arc head
- V is adjacent to W or W is adjacent to V
-
-
Undirected graph
-
A finite set of undirected edges
- An edge is an unordered pair of vertices
- (v, w)
- = (v, w) (w, v)
- W and V are adjacent to each other
-
-
-
A simple figure
- 1. There is no edge from vertex to itself
- 2. The same edge does not appear twice
-
Multiple figure
- If there is more than one edge between two nodes in graph G, the vertices are allowed to relate to themselves through the same edge
-
Complete graph
-
Undirected complete graph
- If there’s an edge between any two vertices
-
Directed complete graph
- If there are two arcs in opposite directions between any two vertices
-
-
subgraph
-
Connected graph: Any two vertices in a graph are connected
-
Connected component: A maximally connected subgraph of an undirected graph
-
connected
- There’s A path from vertex A to vertex B
-
great
- 1. There are enough vertices
- 2. The maximally connected subgraph contains all the edges that are attached to these vertices
-
Conclusion 1: If a graph has n vertices and less than n-1 edges, then the graph must be disconnected.
-
Summary: The method of finding connected components: start with a vertex as a subgraph, then add vertices and edges connected to the subgraph one by one until all connected vertices are added to the subgraph
-
-
Strongly connected: Vertex V to vertex W and vertex W to vertex V have paths
-
Strongly connected graph: Any pair of vertices in a graph are strongly connected
-
Spanning tree of a connected graph: a minimal connected subgraph that contains all n vertices in the graph but only n-1 edges
- Conclusion 2: Removing an edge from a spanning tree becomes an unconnected graph, and adding an edge creates a loop.
-
Degree: The number of edges with this vertex as an endpoint
-
The degree of vertex V in an undirected graph refers to the number of edges attached to the vertex, denoted as TD(V).
-
The degree of vertex V in a directed graph is divided into out degree and in degree
- The entry degree (ID) is the number of directed edges terminating at vertex V
- The output degree (OD) is the number of directed edges starting from vertex V
-
-
Simple paths and simple loops: Paths whose vertices do not repeat themselves are called simple paths. For a loop, a loop in which vertices do not occur repeatedly except for the first and last vertices is called a simple loop
-
Weights and nets: The number of values assigned to each edge in a graph. This value is called the weight of the edge. A weighted graph is also called a net
-
Path and path length: the path between vertices P and q refers to the sequence of vertices saved, p,a, B,c,d… Q. The number on the path is the length of the path
-
Loop: A path whose first and last vertices are the same is called a loop or loop
-
Distance: The length of the shortest path from vertex u to v. If there is no path, it is infinite
The storage structure of the graph
-
Adjacency matrix (sequential storage)
-
Adjacency list (chain storage)
- Cross linked list (directed graph)
- Adjacency multiple list (undirected graph)
Graph traversal
-
Depth-first traversal
-
Depth-first Search (DFS): Depth-first Search is similar to the tree-first traversal algorithm
- Space complexity: as the DFS is a recursive algorithm, recursive is need a stack to assist in the work, the most needed all vertices in the graph into the stack, so the time complexity is O (| V |)
- Time complexity: 1) the adjacency list: traversal process is the main operation of vertex traverse its adjacent points, because by visiting side table to find the adjacent points, so the time complexity is O (| E |), visit the vertices for O (| V |), so the total time complexity is O (+ | | V | E |) 2) adjacency matrix: Search for each vertex adjacency point time complexity is O (| V |), to find every vertex, so the total time complexity is O (2) | | V
-
-
Breadth-first traversal
-
Breadth First Search (BFS): Breadth First Search is similar to the sequence traversal algorithm of tree
- Space complexity: BFS need with the aid of a queue, n vertices are need a team, so the worst case n vertices in the queue, so you need to O (| V |) space complexity.
- Time complexity: 1) the adjacency list: each vertex team once, the time complexity is O (| V |), for each vertex, the search for its adjacent points, you need to access all the vertices of the boundary, so the time complexity is O (| E |). So the total time complexity is O (+ | | V | E |) 2) adjacency matrix: each vertex team once, the time complexity is O (| V |), for each vertex, the search for its adjacent points, need to traverse through the matrix of a line, so the time complexity is O (| V |), so the total time complexity is O (2) | | V
-
The application of figure
-
Minimum spanning tree
-
Prlm
-
① Select the first starting vertex v0 from the graph as the first vertex of the spanning tree, and then select the edge with the least weight from this vertex to the other vertices. And then I’m going to add another vertex v of this edge and this edge to the spanning tree.
-
② For the remaining vertices, check whether the weights of these vertices and vertex V are smaller than the corresponding weights of these vertices in the Lowcost array. If they are smaller, update the Lowcost array with smaller weights.
-
③ Continue to select the edge with the lowest weight from the updated Lowcost array that is not in the spanning tree and add it to the spanning tree.
-
④ Repeat ②③ until all vertices have been added to the spanning tree.
-
Summary:
- Double loop, n-1 for the outer loop, n for the two parallel loops for the inner loop. Therefore, the time complexity of Primm algorithm is O(n2) and the time complexity is only related to N, so it is suitable for dense graph
-
-
Kruskal
-
Arrange the edges in the graph in ascending order of weight, then scan from the smallest edge, set up a set of edges to record, if the edge merge does not form a loop, merge the edge into the current spanning tree. Until all the edges are tested.
-
Summary:
- Summary: Kruskal algorithm operation is divided into the weight sorting part of the opposite edge and a single for loop, they are parallel relationship, because the sorting time is larger than the single loop, so the kruskal algorithm time is mainly spent on sorting. Sorting is related to the number of edges in the graph, so it is suitable for sparse graphs
-
-
-
The shortest path
-
Dijkstra
-
The shortest path from one source point to the remaining vertices
- The algorithm sets a set S to record the vertices of the shortest paths obtained, which can be realized by an array S [], initialized to 0. When S [vi]=1, the vertex VI is put into S, and the source point v0 is put into S initially. In addition, two auxiliary arrays are also set in the construction process: dist[] : records the current shortest path length from source point V0 to other vertices, dist[I] initial value is arcsv0. Path [] : path[I] represents the precursor node of the shortest path from source point to vertex I. At the end of the algorithm, the shortest path from source point v0 to vertex vi can be traced back according to its value.
-
-
Assuming that starting from vertex 0, that is, vertex 0 is the source point, set S initially contains only vertex 0, the adjacency matrix Arcs represents the weighted directed graph, arcSi represents the weight of directed edges < I, j>, if there is no directed edges < I, j>, then ArcSi is ∞. The steps of Dijkstra algorithm are as follows: 1) initialization: set S is initialized as {0}, dist[I]=arcs0, I =1, 2… , n – 1. 2) Find the minimum dist[j] in dist[] and add vertex j to set S, that is, modify S [vj]=1. 3) Modify the shortest path length reachable from v0 to any vertex vk of set V-S: if dist[j] + arcsj< dist[k], let dist[k]=dist[j] + arcsj. In addition, update path[k]=j(if there is a new path to get vertex k shorter) 4) repeat 2) ~ 3) n-1 times until all vertices are contained in S. * Freudian * Shortest path from all vertices to all vertices * Algorithm idea: recursively produces A sequence of n-order square matrices A(−1), A(0),… , A (k),… , A(n−1) where A(k) I represents the length of the path from vertex vi to vertex vj, and k represents the operation step to circumvent the KTH vertex. Initially, for any two vertices vi and vj, if there is an edge between them, the weight of the edge is used as the shortest path length between them. If there is no directed edge between them, infinity is taken as the shortest path length between them. Try to add vertex k(k= 0,1… , n-1) as the middle vertex. If the length of the path obtained after adding intermediate vertices decreases compared with the original path, the new path replaces the original path * unweighted graph * path with the least number of edges between two points * weighted graph * path with the minimum sum of edge weights between two points
-
A topological sort
-
AOV
- If we treat each link as a Vertex in a graph, such a directed graph is called AOV network (Activity On Vertex), in which the Vertex represents the Activity and the arc represents the priority relationship between the activities.
-
Topological sorting is the process of constructing topological sequence of a directed graph. There are two results: if all the vertices of the graph are output, it means that it is an AOV network without loops; If all vertices are not output, it indicates that there is a loop in this graph, not AOV network.
-
Topological sorting algorithm: select a vertex output with 0 degree of entry from AOV network, then delete this vertex, and delete the arc with this vertex as the arc tail. Repeat this step until you output all vertices in the graph, or no vertices with zero degree of entry can be found.
-
-
The critical path
- AOE(Activity On Edge): in a weighted digraph that represents a project, events are represented by vertices, activities are represented by directed edges, and the duration of activities is represented by weights of edges. This kind of digraph where edges represent activities is called AOE net.