Difference between revisions of "TADM2E 5.22"
From Algorithm Wiki
(Undo revision 883 | Why are u doing this? What's the point? It's wiki for learning book) |
|||
| Line 1: | Line 1: | ||
| − | + | <pre> | |
| + | Working with the list of edges of an undirected graph G | ||
| + | Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m) | ||
| + | - Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it | ||
| + | Initialize the queue Q | ||
| + | Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B | ||
| + | - The presence of a vertex in the queue is noted in the array C, which consists of bool flags | ||
| + | Loop until the queue Q is empty: # O(n) iterations | ||
| + | - Extract vertex V from Q # V has degree 2 => V located between vertexes U and W | ||
| + | - Delete the edge UV, B[U] -= 1 | ||
| + | - Delete the edge VW, B[W] -= 1 | ||
| + | - Delete vertex V, C[V] = False | ||
| + | - If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix | ||
| + | - If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1) | ||
| + | - If W's degree is 2 and W is not in queue Q, add W to Q | ||
| + | </pre>--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 08:17, 7 July 2020 (UTC) | ||
Revision as of 08:13, 23 July 2020
Working with the list of edges of an undirected graph G Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m) - Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it Initialize the queue Q Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B - The presence of a vertex in the queue is noted in the array C, which consists of bool flags Loop until the queue Q is empty: # O(n) iterations - Extract vertex V from Q # V has degree 2 => V located between vertexes U and W - Delete the edge UV, B[U] -= 1 - Delete the edge VW, B[W] -= 1 - Delete vertex V, C[V] = False - If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix - If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1) - If W's degree is 2 and W is not in queue Q, add W to Q--Bkarpov96 (talk) 08:17, 7 July 2020 (UTC)
