The maximal connected subgraph in an undirected graph is called a connected component

If a graph has n vertices and the number of edges is less than n-1, then the graph must be a disconnected graph.

If G is a strongly connected graph, it has at least n edges (forming a cycle)

The maximal strongly connected subgraph in a directed graph is called the strongly connected component of the directed graph.

Undirected graph O(|V| 2|E|)

Directed graph O(|V|2|E|)

Requires an auxiliary queue

How to find other vertices adjacent to a vertex; the visit array prevents repeated visits

How to deal with disconnected graphs

Space complexity O(|V|)-auxiliary queue

time complexity

The graph representation method stored in the adjacency list is not unique, nor is the traversal sequence or spanning tree unique.

Traversing a disconnected graph can generate a breadth-first forest

Recursively explore unvisited adjacent points in depth, how to find other adjacent vertices from one vertex; the visit array prevents repeated visits

How to deal with disconnected graphs

Space complexity O(|V|) - from the recursive work stack

time complexity

Same as breadth-first spanning tree

Number of DFS/BFS function calls = number of connected components

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, you only need to call the DFS/BFS function once from any vertex.

There may be multiple minimum spanning trees, but the sum of edge weights is always unique and smallest.

The number of edges of the minimum spanning tree = the number of vertices - 1; if one is cut off, it will be disconnected, and if one is added, a loop will appear.

If a connected graph is itself a tree, then its minimum spanning tree is itself

Only connected graphs have spanning trees, and unconnected graphs have spanning forests.

As long as an undirected connected graph has no edges with equal weights, its minimum spanning tree is unique because the search process using different algorithms is unique.

Prim algorithm (Prim)

Kruskal algorithm (Kruskal)

BFS algorithm (unweighted graph)

dijkstra algorithm (weighted graph, unweighted graph)

floyd algorithm (weighted graph, unweighted graph)

You can also use dijkstra's algorithm to find the shortest path between all vertices, just repeat |V| times, and the total time complexity is also O(|V|^3)

① Arrange each operand in a row without duplication

② Mark the order in which each operator takes effect (it doesn’t matter if the order is slightly different)

Add operators in order, pay attention to "layering"

Check whether operators at the same level can be combined layer by layer from bottom to top

The vertex represents the activity and the directed edge <Vi,Vj> represents that the activity Vi must be performed before Vj

The AOV network must be a DAG graph and cannot have cycles.

Select a vertex with no predecessor (in-degree 0) 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

① Select a node with no successor (out-degree 0) from the AOV network and output it

Remove the vertex and all directed edges ending with it from the network

Repeat ① and ② until the current AOV net is empty or there are no predecessor-less vertices in the current net. (Indicates there is a loop)

If you imitate the idea of ​​​​topological sorting to implement reverse topological sorting, pay attention to using the storage structure of the adjacency matrix. If you use the adjacency list, because if you delete a vertex, you will also delete the edge pointing to the vertex. The entire table must be traversed every time, which takes a long time. Very high complexity

Topological sorting and reverse topological sorting sequences may not be unique

If there is a cycle in the graph, there is no topological sorting sequence/inverse topological sorting sequence.

For a general graph, if its adjacency matrix is ​​a triangular matrix (there is no cycle), then there is a topological sequence; vice versa, it is not necessarily true.

If a directed graph has an ordered topological sorting sequence, then its adjacency matrix must be a triangular matrix

In a weighted directed graph, events are represented by vertices, activities are represented by directed edges, and the cost of completing the activity is represented by the weight on the edge.

Related concepts

① Find the earliest occurrence time of all events ve()

② Find the latest occurrence time vl() of all events

③Find the earliest occurrence time e( ) of all activities

④ Find the latest occurrence time l( ) of all activities

⑤Find the time margin of all activities d( )=l( )-e( )

① Find ve(k) in sequence according to the topological sorting sequence: ve(source point)=0 ve(k)=MAX{ve(j) Weight(vj,vk)}, vi is the predecessor of vk ② Arrange according to the reverse topological sequence to find vl(k) vl(sink)=ve(sink) vl(k)=Min{vl(j)-Weight(vk,vj)}, vj is any successor of vk

If the time required for key activities increases, the duration of the entire project will increase

Shortening the time of key activities can shorten the construction period of the entire project

When shortened to a certain extent, critical activities may become non-critical activities

There may be multiple critical paths. Only increasing the speed of key activities on one critical path will not shorten the construction period of the entire project. Only by speeding up those key activities included on all critical paths can the purpose of shortening the construction period be achieved.