Databases
StackOverflow2013
Postsdbo
POSpanning tree out of graph using Breadth First Search?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSpanning tree out of graph using Breadth First Search?
    text
    copied!<p>I am trying to make a (spanning) tree that comes naturally from traversing a graph (undirected and connected) using Breadth First Search, but I am having difficulties modifying the algorithm such that it makes a tree. I am using Java. </p> <p>Here is my BFS algorithm. </p> <pre><code>public void traverse(Node node){ Queue queue= new Queue(); node.visited= true; //Maybe do something here? queue.enqueue(node); while (!queue.isEmpty()){ Node r= queue.dequeue(); for (int i= 0; i &lt; r.childen.size(); i++){ Node s= (Node)r.childen.get(i); if (s.visited == false){ //And do something here? s.visited= true; queue.enqueue(s); } } } } </code></pre> <p>My graph data structure is simply this (note it's undirected and connected) :</p> <p><code>public class Graph { Node mainNode; ...</code></p> <p>And the tree data structure is also simply this: </p> <p><code>public class Tree { Node root; ...</code></p> <p>My Node is like this: </p> <pre><code>public class Node&lt;T&gt; { T data; boolean visited= false; ArrayList&lt;Node&gt; childen= new ArrayList&lt;Node&gt;(); ... </code></pre> <p>I think my trouble comes from the fact that I can't simply add some <code>Node node</code> from the graph directly to my tree (because this <code>node</code> would have all its children already). Instead, I have to make a <code>new Node(node.data)</code> so that the added node in the tree doesn't point to all the adjacent nodes that the same node would point in the graph. </p> <p>So my question: how do I make a (spanning) tree out of graph while traversing the said graph using Breadth First Search? </p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload