数据结构树和图有什么区别? [英] What's the difference between the data structure Tree and Graph?

问题描述

从学术上来说，Tree和Graph的数据结构有什么本质区别?那么基于树的搜索和基于图的搜索呢?

Academically speaking, what's the essential difference between the data structure Tree and Graph? And how about the tree based search and Graph based search?

推荐答案

树只是图的一种受限形式.

A Tree is just a restricted form of a Graph.

树有方向(父/子关系)并且不包含循环.它们属于有向无环图(或 DAG)的范畴.所以树是有限制的 DAG，一个孩子只能有一个父母.

Trees have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.

需要指出的重要一点是，树不是递归数据结构.由于上述限制，它们不能作为递归数据结构来实现.但是也可以使用任何通常不是递归的 DAG 实现.我首选的 Tree 实现是集中式地图表示，并且是非递归的.

One thing that is important to point out, Trees aren't a recursive data structure. They can not be implemented as a recursive data structure because of the above restrictions. But any DAG implementation, which are generally not recursive, can also be used. My preferred Tree implementation is a centralized map representation and is non recursive.

图通常搜索广度优先或深度优先.这同样适用于树.

Graphs are generally searched breadth first or depth first. The same applies to Tree.

这篇关于数据结构树和图有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！