确定有向图还是无向图是一棵树 [英] Determining whether or not a directed or undirected graph is a tree

问题描述

我想知道一种确定有向图或无向图是树的快速算法。

或从该顶点进行深度优先搜索。如果遇到已经访问过的顶点，则不是树。

如果完成了操作，并且有未开发的顶点，则不是树-图形为

否则，它是一棵树。

检查二进制文件树，另外检查每个顶点是否最多具有2个输出边。

对于无向图：

• 通过简单的深度优先搜索（从任何顶点开始）检查循环-如果未探索的边导致之前访问过的节点，则该图包含一个循环。 如果有一个循环，则不是




• 如果上述过程未处理某些顶点，则它不是树，因为它没有连接。




• 否则，它是一棵树。




• 要检查二叉树，如果图形具有多个顶点，请另外检查人l顶点具有1-3条边（父部1条，子部2条）。

  
  
  

  检查根，即一个顶点是否包含1-2条边是不需要，因为在无环连接的无向图中必须具有1-2个边的顶点。

  
  
  

  请注意，识别根不是一般的可能（在特殊情况下可能），因为在许多无向图中，如果要使其成为二叉树，则可以将多个节点设为根。

I would like to know of a fast algorithm to determine if a directed or undirected graph is a tree.

This post seems to deal with it, but it is not very clear; according to this link, if the graph is acyclic, then it is a tree. But if you consider the directed and undirected graphs below: in my opinion, only graphs 1 and 4 are trees. I suppose 3 is neither cyclic, nor a tree.

What needs to be checked to see if a directed or undirected graph is a tree or not, in an efficient way? And taking it one step ahead: if a tree exists then is it a binary tree or not?

解决方案

For a directed graph:

• Find the vertex with no incoming edges (if there is more than one or no such vertex, fail).

• Do a breadth-first or depth-first search from that vertex. If you encounter an already visited vertex, it's not a tree.

• If you're done and there are unexplored vertices, it's not a tree - the graph is not connected.

• Otherwise, it's a tree.

• To check for a binary tree, additionally check if each vertex has at most 2 outgoing edges.

For an undirected graph:

• Check for a cycle with a simple depth-first search (starting from any vertex) - "If an unexplored edge leads to a node visited before, then the graph contains a cycle." If there's a cycle, it's not a tree.

• If the above process leaves some vertices unexplored, it's not a tree, because it's not connected.

• Otherwise, it's a tree.

• To check for a binary tree, if the graph has more than one vertex, additionally check that all vertices have 1-3 edges (1 to the parent and 2 to the children).

  Checking for the root, i.e. whether one vertex contains 1-2 edges, is not necessary as there has to be vertices with 1-2 edges in an acyclic connected undirected graph.

  Note that identifying the root is not generically possible (it may be possible in special cases) as, in many undirected graphs, more than one of the nodes can be made the root if we were to make it a binary tree.

这篇关于确定有向图还是无向图是一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！