public static IEnumerable<Node> DepthSearch(Node startNode) { var visited = new HashSet<Node>(); var stack = new Stack<Node>(); visited.Add(startNode); stack.Push(startNode); while (stack.Count != 0) { var node = stack.Pop(); yield return node; foreach (var nextNode in node.IncidentNodes.Where(n => !visited.Contains(n))) { visited.Add(nextNode); stack.Push(nextNode); } } }
1. Если V — количество вершин графа, а E — количество ребер графа, то оцените временную сложность обхода в глубину?
1 балл
O(V \times E)
O(V + E)
O(V)
O(V^2)
O(V^2 + E)
2. Оцените пространственную сложность обхода в глубину?
1 балл
O(V \times E)
O(V + E)
O(V)
O(V^2)
O(V^2 + E)
public static IEnumerable<Node> BreadthSearch(Node startNode) { var visited = new HashSet<Node>(); var queue = new Queue<Node>(); visited.Add(startNode); queue.Enqueue(startNode); while (queue.Count != 0) { var node = queue.Dequeue(); yield return node; foreach (var nextNode in node.IncidentNodes.Where(n => !visited.Contains(n))) { visited.Add(nextNode); queue.Enqueue(nextNode); } } }
3. Если V — количество вершин графа, а E — количество ребер графа, то оцените временную сложность обхода в ширину?
1 балл
O(V \times E)
O(V + E)
O(V)
O(V^2)
O(V^2 + E)
4. Оцените пространственную сложность обхода в ширину?
1 балл
O(V \times E)
O(V + E)
O(V)
O(V^2)
O(V^2 + E)
×
Практика, практика и еще раз практика!
Войдите
или
зарегистрируйтесь
, чтобы отвечать на тесты и решать задачи.