|
|
| Line 1: |
Line 1: |
| − | (a) Compare every possible set of three vertices and test if there is an edge between the three.
| |
| | | | |
| − | (b) One may be tempted to use DFS to find cycle of length 3, by maintaining an array parent[I] and check any backedge u-v whether grandparent of u is equal to v. However this is incorrect, consider the graph
| |
| − |
| |
| − | A - B - C - D - A (square)
| |
| − |
| |
| − | D - E - F - G - D (another square, connected to the first one through D)
| |
| − |
| |
| − | A - G (edge that closes the triangle A - D - G).
| |
| − |
| |
| − |
| |
| − | DFS would produce:
| |
| − |
| |
| − | A -> B - > C -> D (grandParent of D is B) -> A (nothing to do, back up the recursion to D and move to the next edge) -> E -> F -> G (grandparent of G is E)
| |
| − |
| |
| − | At this point we find a cycle when considering the edge G - D, but the grandparent of D isn't connected to G. So we continue and consider A, and then the recursion ends and we process back every node till A, and consider the last edge: A -G. Since A isn't connected to the grandfather of G, we don't find the triangle.
| |
| − |
| |
| − | Some possible solutions can be found in : http :// i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_t.pdf
| |
| − |
| |
| − | ----
| |
| − | Alternative solution
| |
| − |
| |
| − | <pre>
| |
| − | 1. O(|V|^3)
| |
| − | - If only adjacency lists are available, convert adjacency lists to the adjacency matrix
| |
| − | - If an adjacency matrix is available, traverse the matrix O(|V|^2) get a vertex U and an adjacent M, traverse the M row O(|V|) and check the vertices
| |
| − | for adjacency with U O(1)
| |
| − |
| |
| − | 2. O(|V|*|Е|), |V| <= |E|
| |
| − | - Data preparation
| |
| − | - - Let's analyze the case with the largest upper bound => assume that |V| = |E|
| |
| − | - - If an adjacency matrix is available, create additional adjacency lists O(|V|^2)
| |
| − | - - If adjacency lists are given, create an additional adjacency matrix O(|V| + |E|) = O(2 * |V|) by assumption ~ O(|V|)
| |
| − | - - At this stage, we have adjacency lists and an adjacency matrix, and each element of the adjacency lists also stores its coordinates from the adjacency matrix
| |
| − |
| |
| − | - Algorithm
| |
| − | - - Traverse adjacency lists O(|V| + |E|) vertex U is the owner of the current list, vertex M is a list item
| |
| − | - - - Traversing a list owned by M O(|V|) vertex M is the owner of the list, vertex C is a list item
| |
| − | - - - - Checking C for adjacency with U O(1), since the coordinates of the vertices are known => row U and column C are known
| |
| − | - - Time complexity O(|V| + |E|) * O(|V|) * O(1) ~ O(|V|) * O(|V|) = O(|V|^2) ~ O(|V| * |E|), by assumption |V| = |E|
| |
| − | </pre>
| |
| − | --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 10:16, 5 July 2020 (UTC)
| |
