How to deveplop a custom traversal algorithm that traverses the graph depth-first and breadth-next?

Question

Questions

Hello, I'm new to DFS and BFS. Today a new question made me feel confused: the problem ask me to develop a custom traversal algorithm that traverses the graph depth-first and breadth-next. which means you have to do things like this: The traversal is depth-first until it reaches a leaf node. When it does, then the next node it chooses is the next child of the root where the traversal began. In the words, the choice is similar to breadth-first where the children of the root are picked in order.

My thoughts

If I have a graph like this:

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

I think the graph should be traversed like this: The graph

However

However, I don't know how to write the code because I don't know: 1. How to know if the traversal reaches a leaf-node? 2. Can I simply call BFS() and DFS() function to write the code?

I'll appreciate if you can help me!

Answer 1

1. If you solve graph problem, you should know edges of graph, if you know edges you can find node that no any edge go from it, that the leaf node.

2. No, i think not. BFS and DFS just traverse all your graph if you call them, if you don't do any changes ofcourse.

   I think you just need to construct own algorithm based on BFS and DFS. I can offer one. Here some code example written in C#, trying to do rhat described in your question, depth-first, breadth-next.

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;
}

Answer 2

Supposing you have the traditional bfs and 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)

We can just modify both of them.

• dfs has a boolean flag onleaf which basically abort its exploration
• bfs has a hook: dfs (itself!) which is called before bfs-exploring next node

#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)

---

below 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)