Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя MMM24

Looping through a tree
Автор MMM24, история, 9 лет назад, По-английски

Hi all. I have the following code

void f(int x)
{
  if(x<0||x>10000) return ;
  f(x-1);
  f(2*x);
}

When this code is executed it will start from left (x-1) untill he reach the last element and then go to the right and so on

How ever i want it to proceed from up to down like in the picture

Any helps. regards.

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

you can use BFS instead of DFS. It means you can have a queue that put sub-states of current state in it, and every time you have done with current state, you should pick a new state from the queue. (for more details, google it :) )

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks for your reply , BFS is great solution to this problem but i still want to know if there is a way to do it with DFS :)

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      also you can use depth controlled DFS, I mean you can use a factor depth in your function and prevent to go beyond this limit, so you can check all the possible states at desired level D from the root. By increasing this limit (D), you can search whole the graph using DFS but similar to BFS.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        i start to understand a bit , you mean add a parametre to the function that prevent it to go in one direction . Right ?? Can you provide a code ??

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          not exactly one direction, just one level!

          void DFS(int u, int depth, int current_level) {
	visit[u] = true;
	if (current_level == depth) {
		// we have reached the desired level
		return;
	}
	for (int v : adjacent[u]) {
		// go and check the adjacents of current node
		DFS(v, depth, current_level + 1);
	}
}

          so you can call DFS by increasing the value of depth. It gives you the advantage of BFS.

          → Ответить