|
|
| Line 1: |
Line 1: |
| − | <pre>Algorithm:
| |
| − | BFS of each vertex v ∈ V, O(|V| * (|V| + |E|))
| |
| − | Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)
| |
| | | | |
| − | Extensions:
| |
| − | BFS stops at a depth of 2
| |
| − | - Depth 1-adjacent v in the original graph
| |
| − | - Depth 2-adjacent v in the graph square
| |
| − | BFS uses the vertex statuses unopened, open, and processed
| |
| − | - Open and processed vertexes are not added to the queue again
| |
| − |
| |
| − | Time complexity of the algorithm O (|V| * (|V| + |E|)) = O((|V|)^2 + |V * E|)) = O(|V * E|)
| |
| − | - The number of edges does not grow slower than the number of vertexes
| |
| − | - In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added
| |
| − | - In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma
| |
| − | - - For a complete directed graph |E| = n * (n - 1) edges
| |
| − | - - For a complete not directed graph |E| = n * (n - 1) / 2 edges</pre>
| |
| − | --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 07:48, 30 June 2020 (UTC)
| |
