Difference between revisions of "TADM2E 5.22"

From Algorithm Wiki
Jump to: navigation, search
(Undo revision 870 by Bkarpov96 (talk))
(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)