使用DFS创建生成树 [英] Create Spanning Tree With DFS

问题描述

在已连接和未定向的给定图G = (V,E)上运行深度优先搜索(DFS)算法可提供生成树.在图上运行DFS时，当我们到达其度数大于1的顶点时，即-有多个与之相连的边，我们随机选择一条边继续.我想知道选择边缘(或顶点)继续的选项是否实际上允许使用DFS创建给定图的每个生成树?

Running the Depth First Search (DFS) algorithm over a given graph G = (V,E) which is connected and undirected provides a spanning tree. While running DFS on the graph, when we arrive to a vertex which it's degree is greater than 1 , i.e - there is more than one edge connected to it , we randomly choose an edge to continue with. I'd like to know if the option to choose an edge (or a vertex) to continue with actually allows as to create every spanning tree of a given graph using DFS?

推荐答案

由于您在注释中提到给定生成树，因此您需要一些DFS输出同一棵树，这应该不是问题.

Since you mentioned in the comments that given a spanning tree you want some DFS that outputs the same tree, This shouldn't be a problem.

假设您具有所需的生成树和邻接表形式的图形，并且具有edge_exists(u，v)方法，该方法根据给定生成树中是否存在边缘来返回true或false.

Suppose you have the required spanning tree and the graph in the form of an adjacency list and have a method edge_exists(u,v) which returns true or false depending on whether the edge is present or not in the given spanning tree.

explore(node):
   visited[node] = 1;
   for v in node.neighbors:
       if edge_exists(node, v) && !visited[v]:
           v.p = node
           explore(v)

顺便说一句，我不认为您需要进行访问计数，因为您有一棵生成树，因此edge_exisits会为您做大致相同的事情

BTW i don't think you need to do a visited count since you have a spanning tree, so edge_exisits will do roughly the same for you

通过编程输出生成树，我的意思是，给定一个图形输出所有生成树.我不确定该怎么做.

By programmatically outputting the spanning tree, I meant, given a graph output all the spanning trees. I am not sure how to do this.

这篇关于使用DFS创建生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！