Difference between revisions of "TADM2E 5.12"

Latest revision as of 12:09, 2 August 2020

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

--Bkarpov96 (talk) 07:48, 30 June 2020 (UTC)