我在c ++中执行BFS算法来找到一个生成树,生成树的输出应该以预订的形式显示,但我在实现中有疑问,如果没有确切知道每个节点有多少个孩子?考虑树结构递归树的数据结构可以写成:
I'm doing an implementation of the BFS algorithm in c++ to find a spanning tree, the output for a spanning tree should be shown in preorder, but I have a doubt in the implementation, how I can build a tree if not exactly know how many children have each node?. Considering a tree structure recursive The data structure of the tree can be written as:
typedef struct node { int val; struct node *left, *right; }*tree; //tree has been typedefed as a node pointer.但是不要认为它的工作原理如上所述。
But do not think it works this implementation as mentioned before.
这是我的函数返回树的预订:
This is my function to return the tree in preorder:
void preorder(tree t) { if(t == NULL) return; printf("%d ", t->val); preorder(t->left); preorder(t->right); }我还想知道是否有任何方法来做节点的预订
I also wonder if there is any way to do the preorder of the nodes without using a tree structure.
推荐答案我在帖子中看到了两个具体问题:
I have seen two concrete questions in the posting:
要扩展第二点上的位:预先遍历树仅仅意味着每个节点在其子节点之前被处理。当您执行图搜索时,要遍历图的连接组件,只需访问每个节点一次,就可以有效地创建一个隐式树。也就是说,您的起始节点成为树的根节点。每当您访问节点时,您搜索未被访问的相邻节点,即未被标记的节点。如果存在这样的节点,则入射边缘变为树节点,并且您标记该节点。因为总是只有一个节点被主动地保持,所以需要记住未被处理的节点,然而在某些数据结构中,例如,堆栈或队列(而不是显式地使用堆栈,你可以做递归,隐式创建堆栈)。现在,如果你第一次看到一个节点,你会在它的子节点之前清楚地处理节点号,也就是说,你最终将节点号写入预订节点的顺序。
To expand a bit on the second point: a preorder walk of a tree just means that each node is processed prior to it child nodes. When you do a graph search you want to traverse through a connected component of a graph, visiting each node just once, you effectively create an implicit tree. That is, your start node become the root node of the tree. Whenever you visit a node you search for adjacent nodes which haven't been visited, i.e. which isn't marked. If there is such a node, the incident edge becomes a tree node and you mark the node. Since there is always only just one node being actively held you need to remember the nodes which aren't processed, yet, in some data structure, e.g. a stack or a queue (instead of using a stack explicitly you could do recursion which creates the stack implicitly). Now, if you emit the node number the first time you see a node you clearly process it prior to its children, i.e. you end up writing the node number the order of a preorder walk.
如果您不明白这一点,请抽出一张纸,绘制一张图表和一个伫列:
If you don't understand this, please whip out a sheet of paper and draw a graph and a queue:
- 队列只是不包含任何东西的矩形开始
现在选择一个节点成为搜索的开始节点,它与树的根节点相同。将其数字写入队列中的第一个空位置,并标记即填充节点。现在继续搜索:
Now choose a node to become the start node of your search which is the same as the root node of your tree. Write its number into the first empty position in the queue and mark i.e. fill the node. Now proceed with the search:
- 查看队列前面指示的节点,找到未填充的相邻节点:
- 将节点附加到队列的后面(即在矩形中最后一个节点的后面)
- 节点
- 使连接两个节点的线更粗:
现在,队列矩形包含由图表的广度优先搜索所暗示的生成树的预先遍历。生成树使用较粗的线条可见。该算法也将工作,如果你把队列的矩形作为一个堆栈,但它会是一个有点乱,因为你结束节点之间仍然待处理的节点:而不是看着第一个未命中的节点,你会看最后一个未命中的节点。
Now the queue rectangle contains a preorder walk of the spanning tree implied by a breadth first search of the graph. The spanning tree is visible using the thicker lines. The algorithm would also work if you treated the rectangle for the queue as a stack but it would be a bit messier because you end up with ticked off nodes between nodes still to be processed: instead of looking at the first unticked node you would look at the last unticked node.
当使用图形算法时,我发现它很有用的可视化的算法。虽然让计算机维持绘图是很好的,低技术的替代方法,在纸上绘制东西,并且可能通过一些标记的铅笔指示活动节点也工作,如果不是更好。
When working with graph algorithms I found it quite helpful to visualize the algorithm. Although it would be nice to have the computer maintain the drawing, the low-tech alternative of drawing things on paper and possibly indicating active nodes by a number of labeled pencils works as well if not better.
只需对代码进行注释:每当您读取任何输入时,请确保成功读取数据。 BTW,你的代码显然只是C而不是C ++代码:变长数组在C ++中不可用。在C ++中,你将使用 std :: vector< int> followOrder(vertexNumber)而不是 int followOrder [vertexNumber] 。有趣的是,代码不是C,因为它使用例如。 std :: queue< int> 。
Just a comment on the code: whenever you are reading any input, make sure that you successfully read the data. BTW, your code is clearly only C and not C++ code: variable length arrays are not available in C++. In C++ you would use std::vector<int> followOrder(vertexNumber) instead of int followOrder[vertexNumber]. Interestingly, the code isn't C either because it uses e.g. std::queue<int>.
更多推荐
如何使用算法BFS指示生成树的预订
发布评论