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)

Практика, практика и еще раз практика!

Войдите или зарегистрируйтесь, чтобы отвечать на тесты и решать задачи.