CODEWITHSUNDEEP
treebinary-search-treetraversalbreadth-first-searchtree-traversal
Mohdestic
Mohdestic

Reputation: 9

BFS traversal on multi-way trees?

I've seen samples, codes and references on bfs, however, all of them seems to focus on traversing through binary trees. I want to know if bfs traversal is possible for multi-way trees, if so where can I find coding references for it?

Upvotes: 0

Views: 696

Answers (3)

trincot
trincot

Reputation: 350202

BFS is indeed a traversal that is not specific for binary trees, but can be used on any graph. Wikipedia has an entry on Breadth-first search, and it even offers pseudo code that is intended to work with any graph.

Input: A graph G and a starting vertex root of G

Output: Goal state. The parent links trace the shortest path back to root

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as discovered
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as discovered then
11                  label w as discovered
12                  Q.enqueue(w)

Upvotes: 0

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1529

if you clearly understand how BFS works, it doesn't matter what kind of tree (or graph more specifically) you are dealing with, you can always find a way.

if you are really not clear with how to do BFS in multy-nodes tree, here is my pseudocode for you:

     Queue queue; // a de-queue typed data-structure.
     queue.add(root); // root of the tree.

     while -> queue is not empty() :  // traversed untill queue become empty

          tempNode := queue.peek();   // process the peeked item from queue
              queue.pop();

          process -> tempNode.item;

          while -> tempNode.childnode is not null:
                   queue.add(tempNode.childnode)
                   tempNode := tempNode.childnode;

          end of while;

     end of while;

Upvotes: 1

Zartant
Zartant

Reputation: 107

Indeed, I searched too, and bfs aren't focus in multi-way trees. But, references on bfs with graph exists. Because multi-way trees are a subset of graphs, you may find your happiness there.

Upvotes: 0

Related Questions