Difference between revisions of "TADM2E 5.12"
From Algorithm Wiki
EthanGamer (talk | contribs) (Blanked the page) |
(Undo revision 1145 by FuckyouMatt (talk)) |
||
| (4 intermediate revisions by 3 users not shown) | |||
| 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) | ||
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
