Как развить пользовательский алгоритм обхода, который пересекает график по глубине вначале и по ширине в следующем?

Question

Вопросы

Здравствуйте, я новичок в DFS и BFS. Сегодня новый вопрос привел меня в замешательство: проблема заставляет меня разработать собственный алгоритм обхода, который пересекает график в глубину-сначала и в ширину-следующий. , что означает, что вы должны сделать что-то вроде этого:сначала в глубину, пока не достигнет листового узла . Когда это происходит, то следующий узел, который он выбирает, является следующим потомком корня, с которого начался обход. Словом, выбор аналогичен ширине вначале, когда дети корня выбираются по порядку.

Мои мысли

Если у меня есть такой график:

[
 [1, 1, 2],
 [2, 3, 4], 
 [3, 5, 6], 
 [4],
 [5],
 [6],
 [7]
 ];

Я думаю, что график должен проходить так: График

Однако

Однако я не знаю, как написать код, потому что я не знаюне знаю: 1. Как узнать, достигает ли обход листа-узла? 2. Могу ли я просто вызвать функции BFS() и DFS() для написания кода?

Буду признателен, если вы поможете мне!

Answer 1

Предположим, у вас есть традиционные bfs и dfs

dfs(G, node, visited):
  if node in visited:
    return
  visited.mark(child)
  for children in node:
    dfs(G, child, visited)

bfs(G, queue, visited):
  node = queue.dequeue()
  if node in visited:
    return bfs(G, queue, visited)

  visited.mark(node)
  for children in node not in visited:
    queue.enqueue(child)

  # explore next node
  bfs(G, queue, visited)

Мы можем просто изменить их оба.

• dfs имеет логический флаг onleaf, которыйв основном прервать исследование
• bfs имеет хук: dfs (сам!), который вызывается перед исследованием bfs следующего узла

#dfs stops exploration if he found a leaf
dfs(G, node, visited):
  if node in visited:
    return
  visited.mark(child)
+  if node has no children
+    onleaf = true
+    return onleaf

  for children in node:
+    hasleaf = dfs(G, child, visited)
+    if hasleaf:
+      return true

bfs(G, queue, visited):
  node = queue.dequeue()
  if node in visited:
     return bfs(G, queue, visited)

  visited.mark(node)
  for children in node not in visited:
    queue.enqueue(child)

+   # explore next node
+   # current node has setted the next candidates, just dfs it
+   dfs(G, node, visited)
+   #process to explore the queue as usual
+   bfs(G, queue, visited)

---

ниже js

/* useless just to get some data and debugging info */
const makeTree = (d => {
  let id = 0
  const rec = (depth = 4) => {
    if (depth == 0) return {id: id++, children:[]}
    return node = {
      id: id++,
      children: Array(1 + Math.floor(Math.random()*5))
        .fill(0)
        .map(rec.bind(null, depth-1))
    }
  }
  return _ => ({ tree: rec(), id })
})()
const proxy = s => {
  const old = s.add
  s.add = function(node){
    console.log('visit ', node.id)
    return old.apply(this, arguments)
  }
  return s
}
/* ---------------end of useless ---------------------*/
let visited = proxy(new Set())

const dfs = node => {
  if (visited.has(node)) { return }
  visited.add(node)
  if (!node.children.length) { return true }
  return node.children.some(dfs)
}

const bfs = (queue) => {
  if(!queue.length) { return }
  const node = queue.shift()
  if (visited.has(node)) { return bfs(queue) }
  visited.add(node)
  queue.push(...node.children)
  dfs(node)
  bfs(queue)
}

const {tree, id} = makeTree()
bfs([tree])
console.log('explored', visited.size, 'expect', id)

Answer 2

1. Если вы решаете задачу графа, вы должны знать ребра графа, если вы знаете ребра, вы можете найти узел, от которого нет ребра, который является листовым узлом.

2. Нет, думаю, нет. BFS и DFS просто пересекают весь ваш граф, если вы вызываете их, если вы не вносите никаких изменений в курс.

   Я думаю, вам просто нужно построить собственный алгоритм на основе BFS и DFS. Я могу предложить один. Вот некоторый пример кода, написанный на C #, пытающийся сделать то, что описано в вашем вопросе: сначала глубина, затем ширина.

public static List<Node> DepthFirstBreathNext(Node startNode)
{
    var visitedNodes = new HashSet<Node>();
    var orderedVisited = new List<Node>();
    var depthStack = new Stack<Node>();
    var breadthQueue = new Queue<Node>();
    depthStack.Push(startNode);
    while (depthStack.Count > 0 || breadthQueue.Count > 0)
    {

        // Do depth-first while don't get to leaf
        while (depthStack.Count > 0)
        {
            var currentNode = depthStack.Pop();
            visitedNodes.Add(currentNode);
            orderedVisited.Add(currentNode);
            if (currentNode.PointTo == null || currentNode.PointTo.Where(x => !visitedNodes.Contains(x)).Count() == 0)
                break;

            // Push first node to the stack for depth-first
            depthStack.Push(currentNode.PointTo.Where(x => !visitedNodes.Contains(x)).First());

            // Push other nodes to the queue for breadth-next
            foreach (var node in currentNode.PointTo.Where(x => !visitedNodes.Contains(x)).Skip(1))
            {
                breadthQueue.Enqueue(node);
            }
        }

        // Do the breadth-next. Push to the stack first node from breadth queue.  
        if (breadthQueue.Count > 0)
        {
            while (visitedNodes.Contains(breadthQueue.Peek()))
            {
                breadthQueue.Dequeue();
            }

            if (breadthQueue.Count > 0)
            {
                depthStack.Push(breadthQueue.Dequeue());
            }
        }
    }

    return orderedVisited;
}